ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto [...] a questo punto possibile, per es., la dimostrazione dei teoremidi indecidibilità e diincompletezzadiGödel. Va osservato comunque che sono stati trovati vari esempi di proposizioni vere (dette proposizioni combinatorie indecidibili) della teoria ...
Leggi Tutto
Fondamenti della matematica e teoria algoritmica dell'informazione
Gregory J. Chaitin
Ciò che possiamo dimostrare intorno ai fondamenti della matematica usando i suoi stessi metodi costituisce la metamatematica, [...] ora la storia della materia, iniziando con un pregevole pezzo d'antiquariato: il primo teoremadiincompletezza, enunciato e dimostrato da Kurt Gödel nel 1931.
Fissiamo la nostra teoria assiomatica formale come sopra descritto e chiediamoci se la ...
Leggi Tutto
TEORIE FORMALIZZATE
Aldo Marruccelli
. Una t. deduttiva T è un insieme di enunciati espressi in un determinato linguaggio (ordinario o simbolico) suscettibile di interpretazioni su opportuni insiemi [...] completa" ?).
Questi e altri problemi sono affrontati dalla logica matematica, che soprattutto mediante il teorema d'incompletezza sintattica di K. Gödel e i suoi corollari, sancisce in modo definitivo quali sono le limitazioni connesse con la ...
Leggi Tutto
incompletezza
incompletézza s. f. [der. di incompleto]. – Condizione di ciò che è incompleto: i. di una serie, di un elenco, di una reazione chimica; non sono in grado di giudicare, per i. dei dati (o per i. d’informazione). In logica matematica,...
godeliano
‹ġö-› agg. – Relativo al matematico Kurt Gödel (1906-1978) e alla sua opera: teoremi g., o prove di Gödel, le dimostrazioni, da lui formulate, dell’incompletezza di qualsiasi assiomatizzazione della teoria dei numeri, dell’impossibilità...