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.

Funzioni ricorsive parziali[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Turing equivalenza.

I più noti modelli di calcolo Turing equivalenti, che computano le stesse funzioni di una Macchina di Turing sono:

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 è 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 qualche altro formalismo a noi noto.

Storia[modifica | modifica wikitesto]

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.

Bibliografia[modifica | modifica wikitesto]

  • 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
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica