Turing completo para niños

En el mundo de las computadoras y los lenguajes de programación, un sistema se llama Turing completo si tiene la misma capacidad para resolver problemas que una máquina de Turing universal. Imagina que una máquina de Turing universal es como el "cerebro" más potente que se puede diseñar para calcular. Si un sistema es Turing completo, significa que puede hacer cualquier cálculo que esa máquina teórica podría hacer.

Aunque las máquinas de Turing universales son solo una idea (necesitarían memoria ilimitada y nunca fallarían), usamos el término "Turing completo" para hablar de computadoras o lenguajes de programación reales que, si tuvieran memoria infinita y fueran perfectos, podrían hacer cualquier cálculo. La primera máquina que se acercó a esto fue la Z3 de Konrad Zuse en 1941, que funcionaba con programas. Más tarde, en 1998, se demostró que era universal. Hoy en día, casi todas las computadoras que usamos son Turing completas.

La idea de la completitud de Turing es muy importante. Significa que cualquier diseño de computadora, por muy avanzado que sea (incluso las computadoras cuánticas), puede ser simulado por una máquina de Turing universal. Así, una máquina que es Turing completa puede, en teoría, realizar cualquier cálculo que cualquier otra computadora sea capaz de hacer. Esto no significa que sea fácil escribir un programa para ella o que el cálculo sea rápido, solo que es posible.

¿Qué es la Completitud de Turing?

La completitud de Turing se refiere a la capacidad de un sistema para simular una máquina de Turing universal. Esta máquina es un modelo teórico de computadora que puede realizar cualquier cálculo que sea posible. Si un lenguaje de programación o una computadora es Turing completo, significa que puede resolver cualquier problema que pueda ser resuelto por un algoritmo.

¿Por qué es importante la Completitud de Turing?

La importancia de la completitud de Turing radica en que nos asegura que un sistema tiene el poder computacional máximo. Si un lenguaje o una máquina es Turing completa, no hay un problema que otra computadora pueda resolver y esta no. Esto es fundamental para el diseño de computadoras y lenguajes de programación modernos.

Ejemplos de Sistemas Turing Completos e Incompletos

Muchos sistemas que parecen sencillos pueden ser Turing completos. Por ejemplo, el lenguaje de macros de Excel es Turing completo. Esto significa que puedes crear programas muy complejos con él.

¿Qué significa "Turing Incompleto"?

Un sistema es "Turing incompleto" si no puede realizar todos los cálculos que una máquina de Turing universal sí puede. Un ejemplo son las hojas de cálculo sin la capacidad de hacer "ciclos" o "bucles" (repetir una serie de pasos). Aunque puedes hacer muchas operaciones interesantes, no puedes hacer cálculos que requieran repeticiones infinitas o muy complejas. Otros ejemplos son las expresiones regulares o algunos lenguajes de script sencillos.

El Problema de la Parada

Un resultado importante en la teoría de la computabilidad es que, en general, es imposible saber si un programa escrito en un lenguaje Turing completo se detendrá alguna vez o si seguirá ejecutándose para siempre. Para evitar que los programas se queden "colgados", a veces se diseñan sistemas que los detienen después de un tiempo fijo. Sin embargo, estos sistemas ya no son estrictamente Turing completos.

El cálculo lambda sin tipos es Turing completo. Pero algunas versiones del cálculo lambda con tipos no lo son. La ventaja de los sistemas con tipos es que pueden representar muchos programas comunes y, al mismo tiempo, ayudar a encontrar errores en ellos.

Véase también

En inglés: Turing complete Facts for Kids

• Tesis de Church-Turing
• Teoría de la información algorítmica
• El libro de Stephen Wolfram Un nuevo tipo de ciencia
• Algoritmo cuántico
• Hipergrafo
• Realidad simulada
• Universo holográfico