Tesi di Church-Turing
Da Wikipedia, l'enciclopedia libera.
Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: "se un problema è intuitivamente calcolabile, allora esisterà una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo (cioè di calcolarlo)." Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.
Indice |
[modifica] Funzioni ricorsive parziali
La classe di funzioni calcolabili con un formalismo come la macchina di Turing coincide alla classe di funzioni calcolabili la macchina RAM o la macchina RASP. Inoltre tale classe coincide con la classe di funzioni calcolabili da vari formalisimi (pascal, C, ...). L'indipendenza dai formalismi rende questa classe di funzioni come funzioni ricorsive parziali.
Quanto affermato dalla tesi di Church-Turing vale ovviamente anche per tutti i modelli di calcolo equivalenti alle Macchine di Turing, per cui ad esempio una formulazione equivalente della tesi è dire che funzioni ricorsive e funzioni calcolabili sono la stessa cosa.
La tesi di Church-Turing è ormai universalmente accettata, ma non può essere dimostrata.
[modifica] Tesi di Church-Turing estesa
Dato un programma risolvibile con un formalismo e con complessità logaritmica limitato da un polinomio, ossia Tπ = O(nk), compilando il programma in un altro formalismo si può notare che la complessità non cambia.
[modifica] Modelli di calcolo equivalenti
- Si veda l'articolo principale Turing equivalenza
I più noti modelli di calcolo Turing equivalenti, che computano le stesse funzioni di una Macchina di Turing sono:
- le funzioni ricorsive
- il modello di Kleene basato sulle equazioni funzionali,
- il lambda calcolo di Church
- la logica combinatoria
- gli algoritmi normali di Markov
- i sistemi combinatori di Post
- le macchine a registri elementari
Anche i più comuni linguaggi di programmazione, sia imperativi che funzionali sono Turing equivalenti. In particolare un linguaggio è Turing equivalente quando è in grado di compilare sé stesso.
Esempi di modelli di calcolo che sono meno potenti di una MdT sono le espressioni regolari, gli automi a stati finiti e le macchine che terminano sempre.
Concludendo possiamo affermare che non esiste un formalismo più potente della macchina di Turing in termini computazionali. Quindi tutto ciò che non è calcolabile dalla TM non può essere calcolato da qualche altro formalismo.
[modifica] Storia
La tesi di Church-Turing prende il nome dai matematici Alonzo Church e Alan Turing, che la introdussero tra gli anni trenta e gli anni quaranta. Il lavoro dei due sull'argomento prese avvio per risolvere il famoso Entscheidungsproblem, o problema di decisione sollevato da David Hilbert. In sostanza, Hilbert si chiedeva se potesse esistere un algoritmo che potesse decidere circa la verità o la falsità di qualsiasi enunciato matematico. Church e Turing si preoccuparono, per affrontare il problema, di definire rigorosamente il concetto di algoritmo. Indipendentemente, e per mezzo di strade molto diverse, essi arrivarono agli stessi risultati. Church nel 1936 pubblicò un trattato nel quale definiva il lambda calcolo, e nello stesso anno, ma qualche mese dopo, Turing pubblicò un saggio nel quale introduceva il concetto di macchina di Turing, del quale poi si servì per dare risposta all'Entscheidungsproblem. I due matematici giunsero alla conclusione che i sistemi di calcolo automatico (ed altri che continuavano a venire alla luce, come quello proposto dall'americano Emil Post) che avevano proposto erano equivalenti sotto il punto di vista della potenza computazionale. Ne consegue che ognuno di questi strumenti incarna, in realtà, il concetto stesso di algoritmo.
[modifica] Bibliografia
- Giorgio Ausiello, Fabrizio d’Amore, Giorgio Gambosi; FrancoAngeli Editore: Linguaggi, Modelli, Complessità (2003) (ISBN 88-464-4470-1)
- Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0471095850
