Tesis de Church-Turing

En teoria de la computabilidad, la tesis de Church-Turing formula hipotèticament l'equivalència entre els conceptes de funció computable i màquina de Turing, que expressat en llenguage corrent vindria a ser "tot algoritme és equivalent a una màquina de Turing". No és una teorema matemàtica, és una afirmació formalment indemostrable que, no obstant, té una acceptació pràcticament universal.

Introducció

En la década de 1930, un dels problemes més estudiats pels matemàtics era l'Entscheidungsproblem propost per David Hilbert: donada una proposició en un sistema formal, ¿existix un algoritme tal que puga decidir si la proposició és certa (i per tant és una teorema del sistema) o pel contrari és falsa? En 1936 Alonzo Church i Alan Turing varen provar, de forma independent, l'impossibilitat de l'existència de tal algoritme, usant el càlcul lambda en el cas de Church i la màquina de Turing en el cas de Turing. Posteriorment el concepte inicial de dita "màquina" (que no té existència física, realment és una descripció formal) va ser ampliada de diversos modos:

• màquines de Turing en més d'una cinta,
• màquines de Turing en cintes n-dimensionals,
• màquines de Turing en un número llimitat d'estats i símbols,
• màquines de Turing provabilistes,
• màquines de Turing no determinista.

Els llenguages formals que són acceptats per una màquina de Turing són tots aquells que poden ser generats per una gramàtica formal. Per un atre costat, les funcions que poden ser computades en el càlcul Lambda de Church són exactament aquelles que poden ser computades en una màquina de Turing. Estos tres formalisme, les màquines de Turing, els llenguages formals i el càlcul Lambda han segut desenrollats de forma independent i no obstant s'ha provat que són equivalents; esta notable coincidència sembla indicar que la tesis de Church-Turing és certa, sent la noció d'algoritme o procediment efectiu de còmput equivalent a la noció de còmput en una màquina de Turing.

Entre els llenguages formals que són acceptats per una màquina de Turing es poden citar:

• autómates finitos en dos piles;
• autómates finitos en dos contadors;
• la gramàtica formal;
• el sistema Post;
• el càlcul Lambda;
• funcions recursivas parcials;
• autómates celulars: com el jugue de la vida de Conway o l'autómata celular en una dimensió, dos estats, tres celes per veí i la regla 110;
• computadores quàntiques.

A on els tres últims eixemples utilisen una Definició llaugerament distinta d'acceptació de llenguage puix accepten una cadena si existix tan sol un còmput que l'accepta o la majoria l'accepta i llavors és equivalent a màquina de Turing.

¿Per qué és una tesis?

Encara que s'assumix com a certa, la tesis de Church-Turing no pot ser provada ya que no es posseïxen els mijos necessaris, per això és una tesis. Això degut a que “procediment efectiu” i “algoritme” no són conceptes dins de cap teoria matemàtica i no són definibles fàcilment. L'evidència de la seua veritat és abundant pero no definitiva. Precisament la tesis de Church establix que la definició d'algoritme o procediment efectiu és una màquina de Turing.

S'ha acordat que un procediment efectiu o algoritme consistix en un número finito i precís de passos descrit en un número finito de símbols que podria ser també eixecutat per un ser humà. En general, l'eixecució d'un algoritme no requerix de major inteligència que la necessària per a entendre i seguir les instruccions (inclús només seguir).

Eixemples de métodos efectius o algoritmes abunden, per eixemple la suma, resta, multiplicació o divisió són algoritmes d'operacions aritmètiques. l'algoritme de Euclides per a obtindre el màxim comú divisor de dos número natural és un atre eixemple. No obstant, res d'açò ha segut una definició formal puix no és clar qué significa “instrucció precisa” o quin és el tipo d'inteligència necessària per a seguir les instruccions. Per esta mateixa raó, l'idea abstracta d'una màquina que funciona com a paràmetro per a decidir quàn alguna cosa és un algoritme o procediment efectiu és de gran valor. Açò és una màquina de Turing.

Vore també

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

Bibliografia

• Turing, Alan, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Séries 2, 42 (1936), pp 230-265.
• Church, A. 1932. A set of Postulates for the Foundation of Logic. Annals of Mathematics, second séries, 33, 346-366.
  • 1936a. An Unsolvable 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.
  • 1937a. Review of Turing 1936. Journal of Symbolic Logic, 2, 42-43.
  • 1937b. Review of Post 1936. 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. Ámsterdam: North-Holland.
  • 1967. Mathematical Logic. New York: Wiley.

• Gödel, K., 1934, On Undecidable 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 Undecidable, New York: Raven.