Macchina di Turing

Da Wikipedia, l'enciclopedia libera.

Nota disambigua – La macchina di Turing non va confusa con il test di Turing, esperimento concettuale ideato da Turing come una delle prime proposte di definizione del concetto di intelligenza artificiale.

Una visualizzazione della macchina di Turing

Una macchina di Turing (termine spesso abbreviato con MdT) è una macchina formale, cioè un sistema formale che può descriversi come un meccanismo ideale, ma in linea di principio realizzabile concretamente, che può trovarsi in stati ben determinati, opera su stringhe in base a regole ben precise e costituisce un modello di calcolo. Essa ha la particolarità di essere retta da regole di natura molto semplice, ovvero di potersi descrivere come costituita da meccanismi elementari molto semplici; inoltre è possibile presentare a livello sintetico le sue evoluzioni mediante descrizioni meccanicistiche piuttosto intuitive. D'altra parte essa ha la portata computazionale (potere computazionale) che si presume essere la massima: si dimostra infatti che essa è equivalente, ossia in grado di effettuare le stesse elaborazioni di tutti gli altri modelli di calcolo di più ampia portata. Tra questi modelli di calcolo ricordiamo le funzioni ricorsive di Jacques Herbrand e Kurt Gödel, il lambda calcolo di Alonzo Church e Stephen Kleene, la logica combinatoria di Moses Schönfinkel e Haskell Curry, gli algoritmi di Markov, i sistemi di Thue, i sistemi di Post, le macchine di Hao Wang e le macchine a registri elementari o RAM astratte di Marvin Minsky. Di conseguenza si è consolidata la convinzione che per ogni problema calcolabile esista una MdT in grado di risolverlo: questa è la cosiddetta congettura di Church-Turing, la quale postula in sostanza che per ogni funzione calcolabile esista una macchina di Turing equivalente, ossia che l'insieme delle funzioni calcolabili coincida con quello delle funzioni ricorsive.

La MdT come modello di calcolo è stato introdotta nel 1936 da Alan Turing per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica.

Per le sue caratteristiche, il modello della MdT è un efficace strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi. Per definire in modo formalmente preciso la nozione di algoritmo oggi preferenzialmente si sceglie di ricondurlo alle elaborazioni effettuabili con macchine di Turing.

[modifica] Definizione

Della MdT vengono considerate molteplici varianti ("models") che si dimostrano avere la stessa portata. Qui partiamo da una variante piuttosto semplice che possiamo chiamare macchina di Turing deterministica a un nastro e con istruzioni a cinque campi. Altre varianti sono presentate più avanti.

[modifica] Introduzione informale

La macchina può agire sopra un nastro che si presenta come una sequenza di caselle nelle quali possono essere registrati simboli di un ben determinato alfabeto finito; essa è dotata di una testina di lettura e scrittura (I/O) con cui è in grado di effettuare operazioni di lettura e scrittura su una casella del nastro. La macchina si evolve nel tempo e ad ogni istante si può trovare in uno stato interno ben determinato facente parte di un insieme finito di stati. Inizialmente sul nastro viene posta una stringa che rappresenta i dati che caratterizzano il problema che viene sottoposto alla macchina. La macchina è dotata anche di un repertorio finito di istruzioni che determinano la sua evoluzione in conseguenza dei dati iniziali. L'evoluzione si sviluppa per passi successivi che corrispondono a una sequenza discreta di istanti successivi. Le proprietà precedenti sono comuni a molte macchine formali (automa a stati finiti, automa a pila, ...). Caratteristica delle MdT è quella di disporre di un nastro potenzialmente infinito, cioè estendibile quanto si vuole qualora questo si renda necessario.

Ogni passo dell'evoluzione viene determinato dallo stato attuale s nel quale la macchina si trova e dal carattere c che la testina di I/O trova sulla casella del nastro su cui è posizionata e si concretizza nell'eventuale modifica del contenuto della casella, nell'eventuale spostamento della testina di una posizione verso destra o verso sinistra e nell'eventuale cambiamento dello stato. Quali azioni vengono effettuate ad ogni passo viene determinato dalla istruzione, che supponiamo unica, che ha come prime due componenti s e c; le altre tre componenti dell'istruzione forniscono nell'ordine il nuovo stato, il nuovo carattere e una richiesta di spostamento verso sinistra, nullo o verso destra.

Una evoluzione della macchina consiste in una sequenza di sue possibili configurazioni, ogni configurazione essendo costituita dallo stato interno attuale, dal contenuto del nastro (una stringa di lunghezza finita) e dalla posizione sul nastro della testina di I/O. Nei casi più semplici l'evoluzione ad un certo punto si arresta in quanto non si trova nessuna istruzione in grado di farla proseguire. Si può avere un arresto in una configurazione "utile" dal punto di vista del problema che si vuole risolvere; in tal caso quello che si trova registrato sul nastro all'atto dell'arresto rappresenta il risultato dell'elaborazione. Si può avere però anche un arresto "inutile" che va considerato come una conclusione erronea dell'elaborazione. Va subito detto che può anche accadere che un'evoluzione non abbia mai fine (Vedi la successiva sezione e Problema dell'arresto).

[modifica] Impostazione formale

Si definisce macchina di Turing deterministica a un nastro e istruzioni a cinque campi, termine che abbreviamo con MdT1n5i, una macchina formale della seguente forma:

$T = \langle S,s_0,F,A,\beta,\delta \rangle \quad \mbox{dove}$

S è un insieme finito detto insieme degli stati della macchina;

$s 0$ è un elemento di S detto stato iniziale della T;

$F$ è un sottoinsieme di S detto insieme degli stati finali' della T;

$A$ è un alfabeto finito detto alfabeto del nastro della T

$β$ è un carattere dell'alfabeto A detto segno di casella vuota del nastro della T

$\delta ~:~ S \times A \mapsto S \times A \times \{-1,0,+1\}$ è detta funzione di transizione della macchina.

Se $\delta(s,a)=\langle b,t,m\rangle$ , la corrispondente quintupla $\langle s,a,b,t,m\rangle$ può considerarsi come l'istruzione che viene eseguita quando la macchina si trova nello stato s e la testina di I/O legge a sulla casella sulla quale è posizionata; essa comporta la scrittura del carattere b, la transizione allo stato t e:

quando m = -1 lo spostamento della testina di una posizione a sinistra,
quando m = 0 nessuno spostamento della testina,
quando m = +1 lo spostamento della testina di una posizione a destra.

[modifica] Ampiezza della portata e congettura di Church-Turing

L'ampiezza della portata della MdT viene constatata con discorsi che dovrebbero essere molto estesi, ma che fortunatamente possono anche essere abbreviati con considerazioni piuttosto intuitive. Innanzi tutto si individuano MdT relativamente semplici che effettuano le operazioni aritmetiche di base e schemi di composizione di queste macchine che garantiscono la possibilità di calcolare tutte le funzioni concernenti numeri naturali corrispondenti a espressioni ottenute combinando come si vuole le suddette operazioni. Inoltre si individuano versioni della MdT più ricche di prestazioni e di risorse le quali consentono di descrivere più agevolmente le elaborazioni via via più complesse e che riguardano entità discrete dei generi via via più vari (numeri razionali, grafi, stringhe, espressioni simboliche di varia natura, ...), ma tutte riconducibili a numeri naturali; le elaborazioni e le entità dei tipi più vari devono essere prese in considerazione per sostenere la congettura di Church-Turing. Proseguendo in questa direzione si introducono MdT dotate di memorie come sequenze di nastri, memorie bidimensionali e tridimensionali assimilabili ai dischi e alle pile di dischi e che sono dotate di istruzioni in grado di organizzare combinazioni di operazioni assimilabili ai richiami di sottoprogrammi disponibili nei linguaggi di programmazione in uso effettivo. Queste estensioni portano a disporre di macchine formali che in linea di principio si possono ricondurre alla MdT introdotta inizialmente, ma per le quali l'ampiezza della portata si può descrivere abbastanza agevolmente, anche per il fatto di potersi avvalere dei risultati che esse in precedenza hanno permesso di conseguire. Tra queste macchine formali vanno considerati anche gli attuali elaboratori elettronici programmabili con linguaggi di programmazione dei vari livelli, fino a quelli in grado di effettuare calcoli simbolici ed elaborazioni parallele; tali sistemi informatici in linea di principio si possono considerare varianti estremamente articolate della macchina di Turing. A questo punto si deve anche aggiungere che della MdT risulta opportuno anche considerare varianti non deterministiche, macchine formali che sono in grado di portare avanti contemporaneamente diverse elaborazioni, in numero illimitato. Anche queste macchine formali, a prima vista lontane da modelli di meccanismi concretamente realizzabili, possono considerarsi idealizzazioni di sistemi di computer che operano in parallelo, sistemi che la odierna tecnologia consente di realizzare abbastanza comunemente (i cosiddetti cluster).

Facendo riferimento agli strumenti di crescente portata prospettati, si procede a constatare che con la macchina di Turing in linea di principio si riescono a simulare le elaborazioni effettuabili mediante tutte le macchine formali che si sono conosciute e tutte le elaborazioni che si vanno continuamente eseguendo con gli odierni computers. Queste elaborazioni si possono chiamare Turing eseguibili. Esse dunque comprendono non solo tutte le elaborazioni su numeri interi, ma anche quelle del calcolo approssimato riguardanti approssimazioni finite di numeri reali (eventualmente ottenibili con sistemi per il calcolo parallelo fino a quelli per il grid computing), le elaborazioni eseguibili con i sistemi per la dimostrazione automatica di teoremi e le stesse dimostrazioni matematiche che sono state condotte nel corso della sua storia, diciamo a partire da Euclide.

Tutte queste considerazioni rendono ragionevole sostenere la congettura di Church-Turing.

Lo sviluppo precedente ha anche il merito di mostrare una certa sostanziale unitarietà delle elaborazioni che sanno eseguire operatori umani o materiali (meccanici o, più aggiornatamente, elettronici), cioè agli sviluppi algoritmici. Questa unitarietà ha l'importante conseguenza di aprire la strada a un sistematico riutilizzo degli strumenti e delle esperienze computazionali, riutilizzo che può realizzarsi sia sul piano dello studio delle realizzazioni precedenti, sia mediante programmi scritti in un linguaggio nuovo che richiamano effettivamente procedure scritte in un linguaggio precedentemente sperimentato. Accade però che quando si precisano le accennate equivalenze fra sistemi computazionali di costituzione differente, risulta evidente che sistemi diversi hanno efficienze molto diverse. Un calcolo che un odierno computer esegue in pochi secondi, ad un meccanismo dotato di dispositivi operativi estremamente semplici come la MdT sopra definita richiederebbe un numero enorme di passi. Quindi insieme alla unitarietà e alla riutilizzabilità delle procedure algoritmiche, risulta evidente la necessità di organizzare le conoscenze sopra gli algoritmi tenendo ben conto delle preoccupazioni sulla complessità computazionale.

[modifica] Il problema dell'arresto e la sua indecidibilità

In talune circostanze può essere utile considerare una MdT che presenta un'evoluzione illimitata (infatti si considerano infinite le risorse di spazio e tempo a disposizione della macchina). Ad esempio interessa far procedere "illimitatamente" (cioè "quanto risulta utile") una MdT che genera gli elementi di una successione di oggetti (ad es. i successivi numeri primi, o i successivi numeri di Mersenne, o le successive cifre decimali di un numero irrazionale come pi greco). In altri casi invece un'evoluzione illimitata di una MdT è considerata un insuccesso. Quando si vuole che una MdT ricerchi in un insieme numerabile un elemento con determinate caratteristiche ed essa procede nella ricerca senza fornire alcuna indicazione, ci si trova in una situazione decisamente insoddisfacente: non si sa se interrompere un'elaborazione inutile oppure attendere ancora un risultato che potrebbe essere fornito dopo un ulteriore lavoro in tempi accettabili.

È dunque importante poter stabilire se una MdT, o un altro sistema formale equivalente ("lambda-calcolo" di Church, ad es.), quando le si sottopone una stringa (di dati) si arresti o meno. Questo è detto Problema dell'arresto della macchina di Turing. Si trovano casi nei quali si dimostra o si verifica che si ha l'arresto, casi per i quali si dimostra che l'evoluzione non si arresta ma potrebbe procedere quanto si vuole e casi per i quali non si sa dare risposta.

Sembra ragionevole cercare un procedimento generale per decidere uno di questi problemi. Dato che le MdT si rivelano in grado di risolvere tutti i problemi che si sanno risolvere con gli altri procedimenti noti, è sensato chiedersi se esiste una macchina di Turing in grado di decidere per una qualsiasi coppia (M,d) costituita da una MdT M e da una stringa di dati d se, quando si fornisce d a M, questa si evolve fino ad arrestarsi o meno. Questa richiesta è resa ancor più significativa dall'esistenza, dimostrata dallo stesso Turing, di una cosiddetta macchina di Turing universale, macchina in grado di simulare qualsiasi evoluzione di qualsiasi MdT (anche le evoluzioni di sé stessa!). Ebbene Turing ha dimostrato che la macchina di Turing universale non è in grado di decidere in ogni caso il problema dell'arresto. Quindi nessuna macchina di Turing può farlo. Questo risultato negativo si esprime dicendo che il problema dell'arresto è Turing-indecidibile. Se si accetta la congettura di Church-Turing sulla portata della macchina di Turing, si conclude che il problema dell'arresto della macchina di Turing è indecidibile.

Questo risultato negativo costituisce un limite per tutti i meccanismi computazionali; esso costituisce un risultato limitativo di grande importanza generale e per lo studio degli algoritmi. L'importanza generale dipende dal fatto che ogni procedimento dimostrativo automatico si trova equivalente a una computazione che può effettuarsi con una macchina di Turing. Va posto in rilievo che la Turing-indecidibilità del problema dell'arresto si dimostra equivalente al teorema di incompletezza di Gödel, il primo fondamentale risultato limitativo per la matematica. Si trova inoltre nello studio degli algoritmi e della loro complessità che dalla indecidibilità dell'arresto si deducono abbastanza agevolmente molti altri risultati limitativi.

[modifica] Varianti della macchina di Turing

In questo paragrafo le maggiori varianti della MdT definita in precedenza vengono presentate in termini discorsivi, lasciando ad articoli specifici le considerazioni più precise e complete.

[modifica] Macchina di Turing multinastro

La MdT con più nastri differisce dalla classica sostanzialmente per il tipo della funzione di transizione; questa nel caso dei 3 nastri ha la forma

$\delta ~:~ S \times A \times A \times A \mapsto$

$S \times A \times \{-1,0,+1\}\times A \times \{-1,0,+1\}\times A \times \{-1,0,+1\}$ .

Questa funzione fa dipendere la transizione da quanto viene letto sulle caselle su cui si trovano le testine relative ai diversi nastri e stabilisce quali caratteri devono essere modificati sui vari nastri e come si devono eventualmente spostare le testine.

È abbastanza evidente come questa macchina sia più semplice da usare della classica. Ad es. con essa si possono agevolmente copiare stringhe da un nastro all'altro e con porzioni di nastro si possono rendere disponibili sequenze di memorie indirizzabili abbastanza agevolmente. Con una macchina a tre nastri si può implementare molto facilmente una operazione aritmetica come la somma di due numeri espressi mediante cifre decimali. Similmente e con gli opportuni accorgimenti e con l'uso di altri opportuni registri, lo si può intuire, si riescono a implementare altre operazioni aritmetiche o su entità discrete.

Per dimostrare che una macchina a più nastri P ha la stessa portata di quelle ad un solo nastro si tratta di individuare una di queste, denotiamola M che consente di simularne le evoluzioni. Questa simulazione viene effettuata simulando su un solo nastro della M i molti nastri della P. Si possono avere configurazioni della M che simulano configurazioni della P utilizzando scritture particolari che separano le aree nelle quali sono riprodotti i diversi nastri della P e segnalano le posizioni sulle quali si trovano le varie testine di I/O. A ciascun passo della P si fa corrispondere una serie di passi della M con i quali si sistemano i vari nastri e le posizioni dele relative testine. Si può capire come con un gran numero si spostamenti e di cambiamenti di stato si possono simulare le mosse della P.

[modifica] Macchina di Turing con memoria bidimensionale

Consente di simulare abbastanza facilmente macchine a più nastri e di effettuare elaborazioni grafiche. Ulteriori varianti possono servirsi di memorie tridimensionali e simili.

[modifica] Macchina di Turing non deterministica

La macchina di Turing non deterministica si distingue da quella deterministica definita in precedenza per il fatto che, in presenza di un determinato stato e di un determinato carattere letto, essa permette più transizioni.

[modifica] Definizione

Una macchina di Turing non deterministica T, con grado di nondeterminismo n, è così definita:

$T = \langle S,s_0,F,A,\beta,n,\delta \rangle \quad$

dove le sole differenze rispetto alla definizione iniziale riguardano la presenza dell'intero n e il genere della funzione di transizione:

$\delta ~:~ S \times A \mapsto (S \times A \times \{-1,0,+1\})^k ~\mbox{ dove }~ k=1,2,...,n$

Le sue configurazioni consistono quindi di insiemi finiti di configurazioni deterministiche, la cui cardinalità potrebbe crescere illimitatamente con il procedere di una evoluzione.

Le computazioni che essa è in grado di svolgere sono descrivibili come insiemi di computazioni sviluppati da repliche della MdT deterministica, repliche che potrebbero rendersi necessarie ad ogni passo dell'evoluzione. Si osserva che questa richiesta oggi non dovrebbe affatto stupire, in quanto realizzabile con le tecniche dei computer collegati in rete ed effettivamente realizzata nella prassi delle elaborazioni distribuite.

[modifica] Equivalenza con la MdT classica

Dato che ogni macchina deterministica si può considerare una particolare macchina nondeterministica, si tratta di dimostrare che con una macchina deterministica M si riesce a simulare il comportamento di una macchina non deterministica N. Più precisamente supponiamo che N sia una macchina ad un nastro e che la M sia una macchina che dispone di una memoria bidimensionale, memoria assimilabile alla disponibilità di più nastri il cui numero sia aumentabile. La macchina M riesce a simulare con ciascuno dei suoi stati gli stati multipli della macchina N e con i suoi molti nastri i singoli nastri replicati della N. Ad ogni passo della N la M fa corrispondere una serie di passi con i quali fa evolvere i diversi nastri che rappresenta nella sua memoria bidimensionale e, in corrispondenza a una transizione non deterministica di molteplicità k, replica il nastro interessato trasformandolo nei k nastri richiesti.

In questo modo si vede come la macchina M possa simulare la N. Si osserva che alcuni singoli passi della macchina non deterministica richiedono un gran numero di passi e di appositi stati della deterministica.

[modifica] Macchine di Turing semplificate

Le macchine di Turing possono essere ulteriormente semplificate, senza perdita di portata computazionale. Le semplificazioni possibili sono (non attuabili contemporaneamente):

nastro illimitato solo in una direzione;
alfabeto di soli due caratteri, uno dei quali il simbolo blank;
solo due stati.

La dimostrazione dell'equivalenza con la macchina definita inizialmente con quelle con le caratteristiche 2 e 3 costituiscono il teorema di Shannon.

Un ulteriore modello semplificato di MdT è quello di avere tre MdT che compiono operazioni elementari (scrittura del carattere 1, scrittura del simbolo blank, spostamento della testina a destra, spostamento a sinistra, nessuna operazione) e ottenere da queste una nuova MdT tramite composizione per diramazione.

[modifica] Macchina di Turing universale

Per approfondire, vedi la voce Macchina di Turing universale.

La Macchina di Turing universale è quella che calcola la funzione u, che a sua volta è in grado di simulare il comportamento di qualunque macchina di Turing. La funzione u prende in input una codifica della macchina M che si vuole eseguire (ovvero un numero che una volta decodificato fornisce il codice di M) e una codifica dei parametri inziali ad M.

[modifica] Come nacque la macchina di Turing

Nel 1936 venne pubblicato un articolo di Alan Mathison Turing intitolato On computable numbers, with an application to the Entscheidungsproblem, in cui l'autore risolveva negativamente l'Entscheidungsproblem o problema della decidibilità lanciato nel 1928 da David Hilbert e Wilhelm Ackermann.
La questione era stata posta da Hilbert nei seguenti termini: esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso?
I vantaggi derivanti dal possedere un tale metodo sono enormi e meritano tutta l'enfasi che Hilbert e molti altri al suo seguito, diedero alla questione: un tale algoritmo sarebbe in grado di risolvere tutti i problemi matematici e, molto di più, sarebbe possibile ridurre ogni ragionamento umano a mero calcolo meccanizzabile. Una prima forte risposta la diede il matematico boemo Gödel in occasione della conferenza sull'epistemologia delle scienze esatte di Könisberg (1931), in cui espresse per la prima volta pubblicamente le idee racchiuse nel suo più celebre lavoro sull'incompletezza dei sistemi formali coerenti (primo teorema di incompletezza); Gödel dimostrò che la semplice coerenza di un sistema formale non può garantire che ciò che in esso viene dimostrato sia vero oppure falso. Il sogno di Hilbert stava già sfumando quando Turing pubblicò il suo articolo, in cui dimostrò l'insolubilità dell'entscheidungsproblem.

"Un giovane sconosciuto di nome Alan Turing risolse il quesito quasi per gioco. Con una macchina immaginaria." (si veda [1]).

La soluzione proposta da Turing consiste nell'utilizzo di un modello matematico capace di simulare il processo di calcolo umano, scomponendolo nei suoi passi ultimi.
La macchina è formata da una testina di lettura e scrittura con cui è in grado di leggere e scrivere su un nastro potenzialmente infinito partizionato, in maniera discreta, in caselle. Ad ogni istante di tempo t₁, la macchina si trova in uno stato interno s₁ ben determinato, risultato dell'elaborazione compiuta sui dati letti.

Lo stato interno, o configurazione, di un sistema è la condizione in cui si trovano le componenti della macchina ad un determinato istante di tempo t. Le componenti da considerare sono:

il numero della cella osservata
il suo contenuto
l'istruzione da eseguire

Tra tutti i possibili stati, si distinguono:

una configurazione iniziale, per t=t₀ (prima dell'esecuzione del programma)
una configurazione finale, per t=t_n (al termine dell'esecuzione del programma)
delle configurazioni intermedie, per t=t_i (prima dell'esecuzione dell'istruzione o_i)

Implementare un algoritmo in questo contesto significa effettuare una delle quattro operazioni elementari

spostarsi di una casella a destra
spostarsi di una casella a sinistra
scrivere un simbolo preso da un insieme di simboli a sua disposizione su una casella
cancellare un simbolo già scritto sulla casella che sta osservando

oppure fermarsi.
Eseguire un'operazione o₁, tra gli istanti di tempo t₁ e t₂, vuol dire passare dallo stato interno s₁ al s₂. Più formalmente questo si esprime in simboli come: {s₁,a₁,o₁,s₂} da leggersi come: nello stato interno s₁ la macchina osserva il simbolo a₁, esegue l'operazione o₁ e si ritrova nello stato interno s₂.
Turing poté dimostrare che un tale strumento, dalle caratteristiche così rigidamente definite, è in grado di svolgere un qualsiasi calcolo, ma non si fermò qui; egli capì che la calcolabilità era parente stretta della dimostrabilità e dunque, così come Gödel aveva distrutto i sogni di gloria dei Principia Mathematica di Russell e Whitehead, così le sue macchine potevano definitivamente chiudere la questione dell'Entscheidungsproblem.

[modifica] Bibliografia

[modifica] Libri

J. Hopcroft, J. Ullman (1979): Introduction to Automata Theory, Languages and Computation, Addison-Wesley ISBN 020102988X
Douglas Hofstadter (1979): Gödel, Escher, Bach: Un'Eterna Ghirlanda Brillante
- Versione italiana (1990) Godel, Escher, Bach: un'eterna ghirlanda brillante, Adelphi ISBN 8845907554
Arto Salomaa (1985): Computation and automata, Cambridge University Press ISBN 0521302455
Ivor Grattan-Guiness (2000): The search for Mathematical Roots, 1870-1940, Princeton University Press ISBN 069105858X
Martin Davis (2003): Il calcolatore universale. Da Leibniz a Turing, Adelphi ISBN 8845917924

[modifica] Articoli

Alan Turing (1936): On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc., 42 pp. 230-265 Accessibile anche in linea

[modifica] Voci correlate

Macchina di Turing universale
Teoria della informazione algoritmica di Gregory Chaitin
Informatica quantistica
Filosofia della matematica

[modifica] Collegamenti esterni

Turing Machine in MathWorld
Turing Machine nella Stanford Encyclopedia of Philosophy

[modifica] Appunti e dispense

Dispense di logica e fondamenti della matematica: [2]
Nonsolomatematica
Settimana della cultura

[modifica] Simulatori

Scritto in Delphi 7.0 qui Versione semplice (Funziona anche su linux con wine)
Scritto in Delphi 7.0 qui Versione che utilizza la descrizione lineare (Funziona anche su linux con wine)
Scritto in Python qui
Scritto in Java: l'applet e il codice
Simulatore con il gioco Life di Conway

Teoria degli automi: linguaggi formali e grammatiche formali
gerarchia di Chomsky	Grammatiche	Linguaggi	automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Sensibile al contesto	Sensibile al contesto	Lineare-limitato
Tipo-2	Libero dal contesto	Libero dal contesto	Automa a pila
Tipo-3	Lineare (o Regolare)	Lineare (o Regolare)	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica

Categoria: Teoria della computazione

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Macchina di Turing

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Definizione

[modifica] Introduzione informale

[modifica] Impostazione formale

[modifica] Ampiezza della portata e congettura di Church-Turing

[modifica] Il problema dell'arresto e la sua indecidibilità

[modifica] Varianti della macchina di Turing

[modifica] Macchina di Turing multinastro

[modifica] Macchina di Turing con memoria bidimensionale

[modifica] Macchina di Turing non deterministica

[modifica] Definizione

[modifica] Equivalenza con la MdT classica

[modifica] Macchine di Turing semplificate

[modifica] Macchina di Turing universale

[modifica] Come nacque la macchina di Turing

[modifica] Bibliografia

[modifica] Libri

[modifica] Articoli

[modifica] Voci correlate

[modifica] Collegamenti esterni

[modifica] Appunti e dispense

[modifica] Simulatori

Views

Navigazione

comunità

Ricerca

Altre lingue