Turing Complete
La completitud de Turing significa que un sistema de cómputo puede simular una máquina de Turing y computar toda función computable — el estándar del poder de cómputo de propósito general.
Propósito
Juzgar el techo de poder de cómputo de un lenguaje/sistema y comprender los límites de la computabilidad.
Mecanismo
Requiere: ramificación condicional + bucles/recursión arbitrarios + memoria de lectura-escritura. La mayoría de los lenguajes son Turing-completos. HTML+CSS (disputado), SQL (CTEs recursivos) y regex (referencias hacia atrás) están en el borde. El problema de la parada es indecidible.
Casos de uso
- Teoría de la computación
- Poder de los lenguajes
- Computabilidad