Una afirmación fundacional informal que sostiene que toda función que pueda ser calculada por un procedimiento finito y mecánico (un algoritmo efectivo) puede ser calculada por una máquina de Turing; identifica la noción intuitiva de computabilidad algorítmica con la computabilidad por Turing.

Principio

Que un único modelo formal (máquinas de Turing, equivalente al cálculo lambda, funciones recursivas, etc.) captura el concepto informal de computación efectiva.

Demostración

Ejemplo concreto: cualquier algoritmo escrito en un lenguaje de programación moderno puede traducirse a un procedimiento equivalente de máquina de Turing que, dada una codificación de las entradas, reproduce el mismo comportamiento de salida; la equivalencia se muestra construyendo un simulador de la semántica del lenguaje en una máquina de Turing universal.

Aplicación incorrecta

Afirmar que la tesis de Church–Turing es un teorema matemático sobre todos los procesos físicos, o usarla para establecer límites de tiempo o espacio (complejidad) en lugar de tratarlos como problemas de computabilidad; o negar a priori la posibilidad de hipercomputación sin evidencia empírica.

Consecuencia

Proporciona una base aceptada para la teoría de la computabilidad y para clasificar problemas como decidibles o indecidibles; justifica el uso de máquinas de Turing (u otros modelos equivalentes) como canónicos para discutir lo que es computable en principio.

Inversión

La inversión sería afirmar la existencia de un procedimiento efectivo, descrito intuitivamente, que ninguna máquina de Turing pudiera implementar — es decir, un algoritmo realizable fuera de la computabilidad de Turing.

Límite

Es una tesis, no un teorema formal: trata sobre qué se considera un algoritmo efectivo y no aborda límites de recursos (tiempo/espacio), cómputo probabilístico o aproximado, ni la realizabilidad física; las extensiones que abordan límites físicos son distintas y dependen de evidencia empírica.

Tensión semántica

Tensión entre 'computable en principio' (equivalencia teórica con máquinas de Turing) y 'computable en la práctica' (cómputo con restricciones de recursos, físico o aproximado), y entre una afirmación descriptiva y una afirmación normativa/empírica sobre sistemas físicos.

Síntesis

La tesis de Church–Turing sostiene que la noción informal de algoritmo efectivo está capturada por la computabilidad de Turing: organiza la teoría de la computabilidad al reunir los procedimientos algorítmicos intuitivos bajo el modelo formal de la máquina de Turing, dejando abiertas las preguntas sobre recursos y realización física.