Tesi de Church-Turing

La Tesi de Church-Turing, simplificant, es pot enunciar així:

"Tot algorisme o procediment efectiu és Turing-computable".

Hi ha moltes versions similars (no necessàriament equivalents) de la tesi de Church-Turing.

En general, en aquest text ens referirem a aquesta tesi com la tesi de Church-Turing o la tesi de Church, indistintament.

Tot i que originalment la tesi que Alonzo Church formulés diu:

Tesi de Church: "(Church-Turing) A function of positive integers is effectively calculable només si recursive."

La traducció seria: Una funció d'enters positius és efectivament calculable només si és recursiva.

I ja que hi ha una varietat de formulacions de la tesi de Church-Turing, usarem, en general, una formulació simple i acceptada com aquesta tesi, que s'obté a partir de les revisions conjuntes entre Alonzo Church i Alan M. Turing dels seus respectius treballs:

Versió de la Tesi de Church-Turing més utilitzada: Tot algorisme o procediment efectiu és Turing-computable.

Una altra versió simplificada de l'anterior és: Tot el que és computable és Turing-computable.

La versió de la tesi més usada estableix que les màquines de Turing realment capturen la noció del que és un algorisme o un procediment efectiu dut a terme per un humà o per una màquina.

Models equivalents a la màquina de Turing MT són: màquines de Turing amb una cinta infinita cap a una direcció, màquines de Turing amb una cinta infinita cap a les dues direccions, màquines de Turing amb múltiples cintes, màquines de Turing amb múltiples piles, màquines d'enumeració, entre d'altres.

Exemples que la tesi de Church-Turing sembla veritable són molts, des del fet que tot algorisme és computable fins al fet que fins i tot models teòrics que semblen molt més poderosos (i ho són però en altres sentits de complexitat), com ho és la computació quàntica, són reduïbles finalment a màquines de Turing. Tal com s'ha vist fins ara, els diferents intents directes o indirectes de crear models diferents a una màquina de Turing, tots són equivalents a màquines de Turing (o de menor poder computacional).

Els llenguatges que són acceptats per una màquina de Turing són exactament aquells generats per totes les gramàtiques formals. El càlcul lambda, per exemple, és una forma de definir funcions. Les funcions que poden ser computades amb el càlcul Lambda són exactament les que poden ser computades amb màquines de Turing. Aquests tres tipus, les màquines de Turing, les gramàtiques o llenguatges formals i el càlcul Lambda són molt diferents i van ser desenvolupats de manera aliena un de l'altre, però, són equivalents, ja que tenen el mateix poder per resoldre problemes. Això generalment es pren com a evidència a favor de la tesi de Church-Turing.

Els ordinadors electròniques o digitals comuns són també equivalents o reduïbles a màquines de Turing, si tinguessin disponible un nombre il limitat de memòria (és a dir que per la memòria encara una màquina de Turing és rigorosament més poderosa encara que en la pràctica pot pensar que a l'ordinador se li pot proveir indefinidament de memòria).

D'això es dedueix també que tot el que es fa sobre les computadores electròniques actuals és equivalent (en el sentit descrit) a una màquina de Turing, per exemple, tots els llenguatges de programació, les tècniques de computació evolutiva: algorismes genètics, programació genètica o estratègies evolutives, i fins i tot les xarxes neuronals implementades en ordinadors digitals.

Altres màquines equivalents a una màquina de Turing inclouen: màquines de Turing amb més d'una cinta, màquines de Turing amb cintes n-dimensionals, màquines de Turing amb un nombre limitat d'estats i símbols, autòmats finits amb dues piles, autòmats finits amb dos comptadors, gramàtica formal, sistema Post, càlcul Lambda, funcions recursives parcials, autòmats cel·lulars (el joc de la vida de Conway o l'autòmat cel·lular amb una dimensió, dos estats, tres cel per veí i la regla 110), màquines de Turing probabilistes, màquines de Turing no deterministes i computadores quàntiques (els tres últims exemples utilitzen una Definició lleugerament diferent d'acceptació de llenguatge, ja que accepten una cadena si hi ha tan sols un còmput que l'accepta o la majoria l'accepta i aleshores és equivalent a màquina de Turing).

Tot i que s'assumeix com a certa, la tesi de Church-Turing no pot ser provada, per això és una tesi. Això degut al fet que "procediment efectiu" i "algorisme" no són conceptes dins de cap teoria matemàtica i no són definibles fàcilment. L'evidència de la seva veritat és abundant però no definitiva. Precisament la tesi de Church estableix que la definició d'algorisme o procediment efectiu és una màquina de Turing.

Serà de particular interès d'aquest text explorar models per als quals aquesta tesi no és veritable, amb la intenció d'estudiar i analitzar les implicacions possibles en la lògica i l'aritmètica.

S'ha acordat que un procediment efectiu o algorisme consisteix en un nombre finit i precís de passos descrit en un nombre finit de símbols que podria ser també executat per un ésser humà. En general, l'execució d'un algorisme no requereix més intel·ligència que la necessària per entendre i seguir les instruccions (fins i tot només seguir).

Exemples de mètodes efectius o algorismes abunden, per exemple la suma, resta, multiplicació o divisió són algorismes d'operacions aritmètiques. L'algorisme d'Euclides per obtenir el màxim comú divisor de dos nombres naturals és un altre exemple. Tanmateix, res d'això ha estat una definició formal, ja que no és clar què significa "instrucció precisa" o quin és el tipus d'intel·ligència necessària per seguir les instruccions. Per aquesta mateixa raó, la idea abstracta d'una màquina que funciona com a paràmetre per decidir quan alguna cosa és un algorisme o procediment efectiu és de gran valor, això és una màquina de Turing.

De fet, la tesi de Church-Turing ha estat tan reeixida que la majoria la suposa veritable. Els termes derivats d'ella, com a mètode efectiu i computable són comunament utilitzats, quan en realitat computable fa a Turing-computable, en el salt entre un i altre hi ha la tesi de Church, i entre molts altres conceptes i termes comunament utilitzats en la teoria de la computabilitat o funcions recursives.

La tesi de Church-Turing té a més profundes implicacions. Quan la tesi és aplicada a la física té diversos significats: que l'univers és una màquina de Turing i per tant no és possible construir físicament una màquina amb més poder computacional o que computi funcions no recursives (la capacitat de còmput que pot contenir l'univers està acoblat al tipus d'univers en què vivim). A això se l'ha anomenat tesi de Church-Turing forta. Una altra possible interpretació és que l'univers no és una màquina de Turing, és a dir, les lleis de l'univers no són computables però això no afecta la possibilitat de crear una màquina més poderosa que una màquina de Turing (univers desacoblat al poder computacional dels dispositius que conté). Una altra possibilitat és que l'univers sigui una hipercomputadora i llavors sigui possible la construcció de màquines més poderoses que les màquines de Turing usant com a entrada els resultats d'aquesta súper ordinador: l'univers o la natura. Per a això possiblement n'hi hauria prou que l'univers fos continu i fes ús d'aquesta continuïtat (una altra pregunta és com és de densa la seva continuïtat).

Recentment s'han proposat models teòrics que pretenen refutar la tesi de Church, per exemple el de les ARNN, que ha estat el més seriós. No obstant això no mostren l'efectivitat necessària, encara, per refutar amb arguments sòlids la tesi de Church. És clar que és més "fàcil" provar la falsedat de la tesi que la veritat d'aquesta. N'hi ha prou amb exposar un mètode efectiu o algorisme que no sigui Turing-computable. Això no és tan fàcil però és més "fàcil" de provar la veritat de la tesi, ja que sembla impossible negar la possibilitat lògica que sigui falsa. Hi ha una tesi relativitzada de Church-Turing que depèn dels graus de Turing definits per màquines de Turing amb oracles. Els oracles són mitjans formals que suposen que se li facilita certa informació a la màquina de Turing per a resoldre algun problema, això defineix una jerarquia que s'ha estudiat tant en la teoria de la computabilitat com en la Teoria de la Complexitat.

• Encyclopedia of Philosophy^{[Enllaç no actiu]}
• Turing, Alan, On computable numbers, with an application to the Entscheidungsproblem , Proceedings of the London Mathematical Society, Series 2, 42 (1936), p. 230-265.
• Church, A. 1932. A set of postulat for the Foundation of Logic . Annals of Mathematics, second sèries, 33, 346-366.
  • 1936. An Unsolved Problem of Elementary Number Theory . American Journal of Mathematics, 58, 345-363.
  • 1936b. A Note on the Entscheidungsproblem . Journal of Symbolic Logic, 1, 40-41.
  • 1937. Review of Turing 1.936 . Journal of Symbolic Logic, 2, 42-43.
  • 1937b. Review of Post 1.936 . Journal of Symbolic Logic, 2, 43.
  • 1941. The calculi of Lambda-Conversion . Princeton: Princeton University Press.

• Kleene, S.C. 1935. A Theory of Positive integers in Formal Logic , American Journal of Mathematics, 57, 153-173, 219-244.
  • 1936. Lambda-definability and Recursiveness . Duke Mathematical Journal, 2, 340-353.
  • 1952. Introduction to metamathematics . Amsterdam: North-Holland.
  • 1967. Mathematical Logic . Nova York: Wiley.

• Gödel, K., 1934, On Undecided Propositions of Formal Mathematical Systems , lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecided, New York: Raven.

• Màquina de Turing
• Temps polinòmic
• Complexitat computacional

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Tesi de Church-Turing