La tesis de Church-Turing

La tesis de Church-Turing afirma que toda función computable por cualquier procedimiento efectivo es computable por una máquina de Turing, equiparando la idea informal de un algoritmo con un modelo matemático preciso.

Definition

La tesis de Church-Turing es la afirmación de que las funciones intuitivamente computables son exactamente las funciones computables por una máquina de Turing, o equivalentemente por el cálculo lambda o las funciones recursivas generales; es una tesis en lugar de un teorema porque la noción intuitiva no está definida formalmente.

Scope

Este tema abarca el enunciado de la tesis, la evidencia convergente de modelos propuestos de forma independiente, la distinción entre la tesis original sobre la computabilidad efectiva y variantes físicas o de complejidad más fuertes, y el papel de la tesis como puente entre la intuición y la prueba formal en la teoría de la computabilidad.

Core questions

• ¿Qué significa identificar la noción informal de algoritmo con un modelo formal?
• ¿Por qué la convergencia de modelos independientes se toma como una fuerte evidencia de la tesis?
• ¿Es la tesis un teorema matemático, una definición o una afirmación empírica?
• ¿Cómo las versiones físicas y de complejidad van más allá del enunciado original?

Key theories

Convergencia de modelos de computación

Se demostró que las máquinas de Turing, el cálculo lambda de Church y las funciones recursivas de Gödel y Herbrand definen exactamente la misma clase de funciones, y este acuerdo independiente es la principal evidencia ofrecida para la tesis.

Estatus como tesis, no como teorema

Debido a que la noción intuitiva de procedimiento efectivo no está formalizada, la afirmación no puede ser probada; se acepta como una identificación fundamental que permite que los argumentos algorítmicos informales sustituyan a las construcciones formales de máquinas de Turing.

Clinical relevance

La tesis autoriza la práctica cotidiana de describir algoritmos en pseudocódigo de alto nivel en lugar de como máquinas de Turing, ya que se asume que cualquier noción razonable de procedimiento efectivo es Turing-equivalente; también enmarca los debates sobre si los dispositivos físicos o cuánticos podrían alguna vez computar más allá de lo Turing-computable.

History

En 1936, Church propuso identificar la calculabilidad efectiva con la definibilidad lambda, y Turing argumentó independientemente a favor de su modelo de máquina, después de lo cual Turing, Kleene y otros demostraron que estas y las funciones recursivas eran equivalentes. Gödel, inicialmente escéptico, llegó a considerar el análisis de Turing como concluyente, y la afirmación combinada se conoció como la tesis de Church-Turing.

Debates

¿Puede la computación física superar el límite de Turing?

La tesis original se refiere a procedimientos efectivos, pero versiones físicas más fuertes afirman que ningún dispositivo físicamente realizable puede computar funciones no Turing-computables. Las propuestas de hipercomputación y las implicaciones de la mecánica cuántica mantienen esta afirmación extendida en disputa, incluso cuando la tesis clásica permanece esencialmente incontestada.

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

¿Por qué se llama tesis en lugar de teorema?

Conecta un modelo formal con la idea informal de un procedimiento efectivo, y esa idea informal no tiene una definición matemática sobre la cual probar cosas. La fuerte evidencia es que cada intento independiente de formalizar la computación ha producido la misma clase de funciones, pero este apoyo es conceptual en lugar de una prueba.

¿Las computadoras cuánticas refutan la tesis de Church-Turing?

No. Las computadoras cuánticas pueden resolver algunos problemas más rápido, pero computan exactamente la misma clase de funciones que las máquinas de Turing, por lo que la tesis original sobre lo que es computable se mantiene. En cambio, se refieren a la versión más fuerte de la teoría de la complejidad que se ocupa de la eficiencia en lugar de la computabilidad.