Propiedad de un sistema computacional que indica que puede simular cualquier máquina programable de propósito general y, por tanto, realizar cualquier cálculo que dicha máquina ideal pueda hacer, dadas tiempo y memoria no acotados.

Principio

Universalidad por simulación: si un sistema puede emular las transiciones de estado de una máquina programable ideal, alcanza la misma clase de comportamientos computables bajo recursos idealizados.

Demostración

Un lenguaje imperativo mínimo con ramificación condicional y almacenamiento entero no acotado puede simular una máquina universal y es por tanto Turing-completo; el autómata celular Regla 110 es un ejemplo constructivo habitual.

Aplicación incorrecta

Igualar completitud de Turing con usabilidad práctica, eficiencia, decidibilidad o terminación garantizada es erróneo; la completitud solo trata de la universalidad de representación bajo recursos idealizados.

Consecuencia

Cuando un sistema es Turing-completo, se puede codificar en él cualquier procedimiento algorítmico, pero entonces también se aplican a sus programas los resultados clásicos de indecidibilidad y no terminación.

Inversión

Un sistema no Turing-completo carece de la capacidad de simular cálculos universales arbitrarios y por tanto no puede expresar todo proceso algorítmico, aunque puede ser decidible o más predecible.

Límite

Depende de idealizaciones como memoria no acotada y control de estado preciso; modelos con memoria finita, flujo de control restringido o primitivas no programables quedan fuera de esta propiedad.

Tensión semántica

Difiere de nociones informales de expresividad o conveniencia: un lenguaje puede ser expresivo para usuarios sin ser Turing-completo, y viceversa; la completitud es una propiedad formal de simulación, no una medida de usabilidad.

Síntesis

La completitud de Turing clasifica sistemas por su capacidad de emular una máquina programable universal bajo recursos idealizados, implicando tanto poder representacional máximo como la aparición de fenómenos de indecidibilidad.