Nella teoria della calcolabilità la tesi di Church-Turing è un ipotesi che intuitivamente dice che se un problema si può calcolare, 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.

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.

Modelli di calcolo equivalenti

---

Si veda l'articolo principale Turing equivalenza

I più noti modelli di calcolo Turing equivalenti, che hanno cioè la stessa potenza di calcolo 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.

Storia

---

La tesi di Church-Turing prende il nome dai matematici Alonzo Church e Alan Turing, che la introdussero tra gli anni 30 e gli anni 40. 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.

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

Computazioni | Teoria della computazione

Church-Turing-These | Church–Turing thesis | Tesis de Church-Turing | Thèse de Church-Turing | תזת צ'רץ'-טיורינג | 처치-튜링 명제 | Tese de Church-Turing | Тезис Чёрча — Тьюринга | 邱奇-图灵论题