b"\n_START_ARTICLE_\nTesi di Church-Turing\n_START_PARAGRAPH_\nNella teoria della calcolabilit\xc3\xa0 la tesi di Church-Turing \xc3\xa8 un'ipotesi che afferma: \xc2\xabse un problema \xc3\xa8 umanamente calcolabile, allora esister\xc3\xa0 una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo (cio\xc3\xa8 di calcolarlo)\xc2\xbb. Pi\xc3\xb9 formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.\n_START_SECTION_\nStoria\n_START_PARAGRAPH_\nLa 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._NEWLINE_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\xc3\xa0 o la falsit\xc3\xa0 di qualsiasi enunciato matematico._NEWLINE_Church e Turing si preoccuparono, per affrontare il problema, di definire rigorosamente il concetto di algoritmo._NEWLINE_Indipendentemente, e per mezzo di strade molto diverse, essi arrivarono agli stessi risultati. Church nel 1936 pubblic\xc3\xb2 un trattato nel quale definiva il lambda calcolo, e nello stesso anno, ma qualche mese dopo, Turing pubblic\xc3\xb2 un saggio nel quale introduceva il concetto di macchina di Turing, del quale poi si serv\xc3\xac per dare risposta all'Entscheidungsproblem._NEWLINE_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. _NEWLINE_Ne consegue che ognuno di questi strumenti incarna, in realt\xc3\xa0, il concetto stesso di algoritmo.\n_START_SECTION_\nFunzioni ricorsive parziali\n_START_PARAGRAPH_\nLa 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. _NEWLINE_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 \xc3\xa8 dire che funzioni ricorsive e funzioni calcolabili sono la stessa cosa._NEWLINE_La tesi di Church-Turing \xc3\xa8 ormai universalmente accettata, ma non pu\xc3\xb2 essere dimostrata.\n_START_SECTION_\nTesi di Church-Turing estesa\n_START_PARAGRAPH_\nDato un programma risolvibile con un formalismo e con complessit\xc3\xa0 limitata da un polinomio, ossia , compilando il programma in un altro formalismo si pu\xc3\xb2 notare che la complessit\xc3\xa0 non cambia."