La seconda rivoluzione scientifica: matematica e logica. Teoria della ricorsivita
Piergiorgio Odifreddi
Teoria della ricorsività
La teoria della ricorsività affronta lo studio delle funzioni con lo [...] da un computer. L'insolubilità del problema della fermata dimostra che esistono insiemiricorsivamenteenumerabili ma non ricorsivi. Poiché per ogni insiemericorsivamenteenumerabile esiste un programma x che si ferma sull'argomento z se e solo ...
Leggi Tutto
m-completo
m-complèto 〈èmme-〉 [agg. Comp. del simb. m e completo] [ALG] Insieme m.: tipo particolare di insiemericorsivamenteenumerabile: v. Gödel, teorema di: III 57 d. ...
Leggi Tutto
creativo
creativo [Der. del lat. creare "relativo al creare"] [ALG] Insieme c.: tipo di insiemericorsivamenteenumerabile: v. Gödel, teorema di: III 57 d. ...
Leggi Tutto
enumerabileenumeràbile [agg. Der. del lat. numerus "numero"] [ALG] Insieme e.: insieme per cui esiste un procedimento effettivo per stabilire una corrispondenza biunivoca tra i suoi elementi e i numeri [...] naturali. ◆ [ALG] [INF] Insiemericorsivamente e.: v. automi, teoria degli: I 332 c. ...
Leggi Tutto
ricorsivamentericorsivaménte [Der. di ricorsivo "in maniera ricorsiva"] [ALG] Insieme r. enumerabile: v. Gödel, teorema di: III 57 b. ◆ [ALG] Nozione non r. enumerabile: v. Gödel, teorema di: III 54 [...] f ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] o decidibile) se è ricorsivamenteenumerabile e anche il suo complementare lo è. In modo equivalente, L è computabile se è riconosciuto da una macchina di Turing che si ferma sempre. Un tipico linguaggio indecidibile è l'insieme delle coppie (⟨M⟩, x ...
Leggi Tutto
Computazione, teoria della
Fabrizio Luccio
La necessità del calcolo, pur riconosciuta dall'uomo in tutte le epoche storiche, ha condotto solo in tempi relativamente recenti a una sistemazione teorica [...] ′α∣−*xsy con s∈F, x,y∈Π*}. I linguaggi (o insiemi) accettati dalle MT si dicono ricorsivamenteenumerabili. Per la MT G abbiamo L(G)={aibici, i≥0}, quindi questo linguaggio è ricorsivamenteenumerabile.
Ricordiamo che una MT M si arresta per tutte le ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. I teoremi di incompletezza di Godel
Carlo Cellucci
I teoremi di incompletezza di Gödel
Nei giorni 5-7 settembre 1930 ebbe luogo a Königsberg [...] . Ma per (a)-A = {n∣T⊬¬ψn(n)}={n∣T⊦ψn(n)}, dunque −A è ricorsivamenteenumerabile. Poiché sia A sia −A sono ricorsivamenteenumerabili, A è un insiemericorsivo. Perciò esiste un j tale che ψj(a) rappresenta A in T, cioè per ogni n:
b) se n ...
Leggi Tutto
teoremi di indecidibilità
Silvio Bozzi
In logica matematica, risultati che affermano che una data teoria formalizzata T non è decidibile, vale a dire non ammette un algoritmo in grado di stabilire in [...] generato si immerge in un gruppo finitamente presentato se, e soltanto se, l’insieme delle relazioni del gruppo è ricorsivamenteenumerabile, rendendo così esplicita l’analogia con i problemi di assiomatizzabilità e decidibilità per teorie ...
Leggi Tutto