Teoría de la computabilidad

VEB Robotron Elektronik Dresden.

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con la llamada máquina de Turing. La teoría de la computabilidad se interesa por cuatro preguntas:

  • ¿Qué problemas puede resolver una máquina de Turing?
  • ¿Qué otros formalismos equivalen a las máquinas de Turing?
  • ¿Qué problemas requieren máquinas más poderosas?
  • ¿Qué problemas requieren máquinas menos poderosas?

La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.

Conjuntos computables y no computables

La teoría de la recursión se originó en la década de 1930, con el trabajo de Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene y Emil Post.[1]

Los resultados fundamentales que obtuvieron los investigadores estabilizaron el concepto de función computable como la manera correcta de formalizar la idea sobre cálculos efectivos.

Estos resultados llevaron a Stephen Kleene (1952) a acuñar dos nombres, "Tesis de Church" (Kleene 1952:300) y "Tesis de Turing" (Kleene 1952:376). Hoy en día ambos se consideran como una única hipótesis, la Tesis de Church-Turing, la cual establece que cualquier función que sea computable por un cierto algoritmo es una función computable. Aunque en un principio era algo un tanto escéptico, alrededor del año 1946, Gödel defendió esta tesis:

" Tarksi ha subrayado en su lectura (y creo justamente) la gran importancia del concepto de recursividad general (o computabilidad de Turing). En mi opinión esta importancia se debe en gran medida al hecho de que con este concepto, por fin se ha conseguido darle una noción absoluta a una interesante noción epistemológica, es decir, una que no depende del formalismo elegido.*"(Gödel 1946 en Davis 1965:84).[2]

Con una definición sobre cálculos efectivos aparecieron las primeras pruebas de que hay ciertos problemas en las matemáticas que no pueden ser decididos de una manera eficaz. Church (1936p, 1936f) y Turing (1936), inspirados por las técnicas usadas por Gödel (1931) para probar sus teoremas sobre la incompletitud, demostraron por separado que no es posible decidir el Entscheidungsproblem de una manera eficaz. Este resultado demostró que no existe un procedimiento algorítmico que pueda decidir de manera correcta si ciertas proposiciones matemáticas son verdaderas o no.

Muchos problemas en las matemáticas han sido demostrados ser indecidibles una vez se establecieron estos primeros ejemplos. En 1947, Markov y Post publicaron por separado sus trabajos mostrando que el problema de las palabras para los semigrupos no puede ser decidido de una manera eficaz. Ampliando este resultado, Pyotr Novikov y William Boone demostraron independientemente en la década de 1950 que el problema de las palabras para los semigrupos no se puede resolver de una manera efectiva: no hay ningún procedimiento eficaz que, dada una palabra en un grupo, decida si el elemento representado por la palabra es el elemento identidad del grupo. En 1970, Yuri Matiyasevich demostró (usando los resultados de Julia Robinson) el Teorema de Matiyasevich, el cual implica que el décimo problema de Hilbert no tiene una solución eficaz; este problema preguntaba si había o no un procedimiento mediante el cual se pudiera decidir si una ecuación diofántica sobre los números enteros tiene una solución entera. La lista de problemas indecidibles contiene ejemplos adicionales sobre problemas sin soluciones computables.

El estudio sobre qué construcciones matemáticas pueden ser llevadas a cabo de una forma eficaz se denomina a veces matemática recursiva; El Handbook of Recursive Mathematics (Ershov et al. 1998) cubre muchos de los resultados conocidos en este campo.

Other Languages
srpskohrvatski / српскохрватски: Teorija izračunljivosti (računarstvo)
Simple English: Computability theory