Funciones computables y la tesis de Church-Turing

Las funciones computables son aquellas que un procedimiento mecánico puede evaluar, y la tesis de Church-Turing identifica esta noción informal con varios modelos matemáticos precisos que definen la misma clase.

Definition

Una función es computable si alguna máquina de Turing, o equivalentemente alguna definición recursiva parcial, produce su salida en cada entrada donde está definida; la tesis de Church-Turing afirma que esta clase matemáticamente precisa coincide con la clase intuitiva de funciones efectivamente calculables.

Scope

Este tema abarca las máquinas de Turing, las funciones recursivas parciales construidas a partir de funciones básicas mediante composición, recursión primitiva y minimización, el cálculo lambda y las máquinas de registros, las pruebas de que estos modelos son equivalentes, las máquinas universales y la tesis de Church-Turing de que capturan toda computación efectiva.

Core questions

• ¿Qué es una máquina de Turing y cómo define una computación?
• ¿Cómo se generan las funciones recursivas parciales a partir de operaciones básicas?
• ¿Por qué todos los modelos razonables de computación definen las mismas funciones?
• ¿Cuál es el estado y la importancia de la tesis de Church-Turing?

Key theories

Modelo de máquina de Turing

Una máquina de Turing es un dispositivo de estados finitos que opera sobre una cinta ilimitada, y las funciones que calcula formalizan la noción de algoritmo en términos de manipulación elemental de símbolos.

Equivalencia de modelos

Las máquinas de Turing, las funciones recursivas parciales, el cálculo lambda y las máquinas de registros calculan exactamente la misma clase de funciones, lo que demuestra la robustez de la noción de computabilidad.

Máquina universal y enumeración

Existe una máquina de Turing universal que simula cualquier máquina dado su código, por lo que las funciones computables pueden enumerarse eficazmente y tratarse como datos, la base de los resultados de autorreferencia.

Clinical relevance

La noción de función computable es el fundamento de la informática teórica: la máquina universal prefigura el ordenador de programa almacenado, la equivalencia de modelos justifica una única definición robusta de algoritmo, y el marco proporciona el entorno preciso en el que se estudian la indecidibilidad y la complejidad.

History

En 1936, Church definió la calculabilidad efectiva mediante el cálculo lambda y Turing mediante sus máquinas, y las dos nociones pronto se demostraron equivalentes a las funciones recursivas de Kleene. La tesis de Church-Turing resultante se convirtió en la definición aceptada de algoritmo, y la máquina universal de Turing se convirtió en un ancestro conceptual del ordenador de propósito general.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

¿Algunas funciones no son computables?

Sí. Debido a que los programas pueden enumerarse pero las funciones no, un argumento de conteo muestra que la mayoría de las funciones no son computables, y ejemplos específicos como la función de parada son demostrablemente incomputables. La computabilidad es una restricción genuina sobre qué funciones pueden evaluar los algoritmos.

¿La tesis de Church-Turing limita lo que las computadoras pueden hacer?

Afirma que ningún modelo de computación efectiva extiende la clase de funciones computables más allá de las máquinas de Turing. Un hardware más rápido o arquitecturas diferentes cambian la eficiencia, no el límite de lo que es computable en principio, por lo que la tesis establece un límite absoluto a la resolubilidad algorítmica.