GUÍA 31-08-26 Teoría de la Computación

NE111 · lunes 31/08/2026 · 16:00-17:15 · Sesión 7

La tesis de Church-Turing

EL ENUNCIADO

Todo lo que es efectivamente calculable por un procedimiento mecánico puede calcularse con una máquina de Turing.

POR QUÉ ES UNA TESIS Y NO UN TEOREMA

No se puede demostrar, porque «efectivamente calculable» es una noción intuitiva, no matemática. La tesis afirma que la definición formal capta correctamente la idea informal. Es una afirmación sobre la adecuación del modelo, y podría en principio refutarse exhibiendo un procedimiento mecánico que ninguna MT pueda simular. Nadie lo ha logrado en noventa años.

LA EVIDENCIA

Varios investigadores formalizaron la computabilidad por caminos independientes y todos los formalismos resultaron equivalentes entre sí.

• Máquinas de Turing — Turing, 1936.
• Cálculo lambda — Church, 1936.
• Funciones recursivas generales — Gödel y Kleene.
• Algoritmos de Markov, máquinas de registros, autómatas celulares.
• Todos los lenguajes de programación de propósito general.

Que enfoques tan distintos converjan en la misma clase de funciones es la razón por la que la tesis se acepta universalmente.

TURING-COMPLETITUD

Un sistema es Turing-completo si puede simular una máquina de Turing. Todos los lenguajes de programación reales lo son, y por eso ninguno puede computar más que otro. Las diferencias entre ellos son de expresividad, comodidad y eficiencia, nunca de poder.

CONSECUENCIAS QUE CONVIENE TENER CLARAS

• Si algo no se puede hacer con una MT, no se puede hacer con ningún lenguaje ni con ninguna computadora, presente o futura.
• Las limitaciones que veremos en el próximo bloque no son de la tecnología: son del concepto mismo de cómputo.
• Una computadora cuántica no viola la tesis: computa lo mismo, potencialmente más rápido en ciertos problemas.

SISTEMAS TURING-COMPLETOS INESPERADOS

El sistema de plantillas de C++, las hojas de cálculo con referencias, algunos juegos y el propio conjunto de reglas de ciertos autómatas celulares resultaron Turing-completos sin que sus diseñadores lo pretendieran. La consecuencia práctica: en cualquiera de esos sistemas es indecidible saber si un programa termina.

EJERCICIO

Argumentar por qué un lenguaje sin ciclos ni recursión no es Turing-completo, y qué se gana con esa limitación.