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. [...] sui gruppi context-free.
Il quarto e ultimo livello della gerarchia è costituito dalla classe dei linguaggi ricorsivamenteenumerabili. Essa viene introdotta mediante le macchine di Turing. Definiremo anche la corrispondente classe di funzioni ...
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 [...] accettate dalla MT Mi di pari indice.
Teorema 11. Il linguaggio Ld={αi tali che αi∉L(Mi), i=0,1,…} non è ricorsivamenteenumerabile.
Il teorema si dimostra notando che se esistesse una MT Mj tale che Ld=L(Mj), la definizione di Ld condurrebbe alla ...
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 insieme ricorsivo. Perciò esiste un j tale che ψj(a) rappresenta A in T, cioè per ogni n:
b) se n ...
Leggi Tutto
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 insiemi ricorsivamenteenumerabili ma non ricorsivi. Poiché per ogni insieme ricorsivamenteenumerabile esiste un programma x che si ferma sull'argomento z se e solo se ...
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 [...] 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. Su un altro ...
Leggi Tutto
m-completo
m-complèto 〈èmme-〉 [agg. Comp. del simb. m e completo] [ALG] Insieme m.: tipo particolare di insieme ricorsivamenteenumerabile: v. Gödel, teorema di: III 57 d. ...
Leggi Tutto
creativo
creativo [Der. del lat. creare "relativo al creare"] [ALG] Insieme c.: tipo di insieme ricorsivamenteenumerabile: 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] Insieme ricorsivamente 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
esclusione
escluṡióne s. f. [dal lat. exclusio -onis, der. di excludĕre «escludere»]. – 1. L’atto, il fatto di escludere o di essere escluso: e. da un’assemblea, dagli esami; e. dal diritto di voto (in determinati casi contemplati dalla legge);...