Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] J. Cannon. Un gruppo si dice automatico se si può rappresentare come un insieme R di parole su un alfabeto A, in modo che per ogni a∈ macchina di Turing si dice ricorsivamenteenumerabile; se è ricorsivamenteenumerabile anche il suo complementare, il ...
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
ricorsivita
ricorsività in logica, caratteristica di un procedimento che riduce la complessità di un problema riportandolo a problemi via via più semplici cui il procedimento stesso viene applicato. [...] , mentre non è ugualmente decidibile la sua non appartenenza all’insieme, allora l’insieme è detto semidecidibile, o ricorsivamenteenumerabile. Ogni insieme decidibile è semidecidibile, ma non viceversa. Mediante la tecnica della gödelizzazione ...
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