insieme ricorsivamenteenumerabile
insieme ricorsivamenteenumerabile insieme tale che, dato un elemento a, è possibile stabilire, in un numero finito di passi, se esso gli appartenga. Se tuttavia l’elemento [...] procedura algoritmica che genera tutti e soli gli elementi dell’insieme. Bisogna distinguere la nozione di insieme ricorsivamenteenumerabile dalla nozione di insieme numerabile: un insieme è numerabile se può essere posto in corrispondenza biunivoca ...
Leggi Tutto
enumerabileenumerabile termine che si riferisce a un insieme di cui sia possibile elencare tutti gli elementi in un dato ordine. Tale insieme deve quindi essere finito o numerabile, ma ciò non è sufficiente. [...] formali, un insieme è enumerabile se risulta essere l’immagine di una funzione calcolabile. L’aggettivo è utilizzato anche nel contesto della decidibilità dell’appartenenza di un elemento a un insieme infinito (→ insieme ricorsivamenteenumerabile). ...
Leggi Tutto
INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] in grado di decidere per il sì o per il no; e ancora è provata l'esistenza di linguaggi ricorsivamenteenumerabili non ricorsivi. Quest'ultima asserzione costituisce una forma astratta del teorema di Gödel che stabilisce che ogni sistema assiomatico ...
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. [...] 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
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 [...] finale, ma è importante osservare che può anche non fermarsi mai. Un linguaggio L riconosciuto da una macchina di Turing si dice ricorsivamenteenumerabile; se è ricorsivamenteenumerabile anche il suo complementare, il linguaggio prende il nome di ...
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
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. [...] possono essere identificati con un insieme di numeri naturali; perciò ha senso parlare di sistemi formali ricorsivamenteenumerabili e ricorsivi. Mentre il requisito dell’enumerabilità è per lo più inglobato nella definizione stessa di sistema ...
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
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);...