Tesi di Church-Turing

Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: «Se un problema è umanamente calcolabile, allora esisterà una macchina di Turing 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.

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 (e 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.

Funzioni ricorsive parziali

La classe di funzioni calcolabili con un formalismo come la macchina di Turing coincide con la classe di funzioni calcolabili dalla macchina RAM o dalla macchina RASP. Inoltre tale classe coincide con la classe di funzioni calcolabili da vari formalismi (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.

Tesi di Church-Turing estesa

Dato un programma risolvibile con un formalismo e con complessità limitata da un polinomio, ossia $T_{\pi }=O(n^{k})$, compilando il programma in un altro formalismo si può notare che la complessità non cambia.

Modelli di calcolo equivalenti

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;
• il calcolo dei predicati (si veda in proposito il teorema di completezza di Godel e il teorema di Church).

Anche i più comuni linguaggi di programmazione, sia imperativi sia 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 macchina di Turing sono le espressioni regolari, gli automi a stati finiti e le macchine che terminano sempre.

Concludendo possiamo affermare che non è noto alcun formalismo più potente della macchina di Turing in termini computazionali. Quindi tutto ciò che non è calcolabile dalla TM non può essere calcolato da nessun altro formalismo a noi noto.

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 0-471-09585-0

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla tesi di Church-Turing

Collegamenti esterni

• Church, tesi di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) the Church-Turing thesis, su Stanford Encyclopedia of Philosophy.
• (EN) Eric W. Weisstein, Church-Turing Thesis, su MathWorld, Wolfram Research.

Controllo di autorità	GND (DE) 4444529-5 · BNF (FR) cb162445653 (data)