Turing completo

En la teoría de computadoras reales e imaginarias, de los lenguajes de programación y de otros sistemas lógicos, un sistema Turing completo es aquel que tiene un poder computacional equivalente a la máquina universal de Turing. En otras palabras, el sistema y la máquina universal de Turing pueden emularse entre sí.

Aún cuando es físicamente imposible que existan estas máquinas debido a que requieren de almacenamiento ilimitado y probabilidad cero de falla, de forma coloquial la completitud de Turing se atribuye a máquinas físicas o lenguajes de programación que podrían ser universales si tuvieran almacenamiento infinito y fueran absolutamente fiables. La primera de esas máquinas apareció en 1941: la Z3 de Konrad Zuse, que era controlada por programas. Su universalidad, sin embargo, fue demostrada mucho después por Raúl Rojas en 1998. En ese sentido laxo, todas las computadoras modernas son también Turing completas.

La completitud de Turing es significativa, pues, cada diseño plausible de un dispositivo de computación, por más avanzado que sea (aun las computadoras cuánticas), pueden ser emuladas por una máquina universal de Turing. Así, una máquina que pueda actuar como una máquina universal de Turing puede, en principio, hacer cualquier cálculo que cualquier otra computadora es capaz de hacer (en otras palabras, es programable). Obsérvese, sin embargo, que no dice nada sobre el esfuerzo de escribir un programa para la máquina o sobre el tiempo que puede tomar el cálculo.

Está la hipótesis de que el Universo es Turing completo (ver implicaciones filosóficas en la Tesis de Church-Turing y en Física digital).

Ver el artículo en Teoría de la computabilidad para una larga lista de sistemas que son Turing completos, así como varios sistemas que son menos poderosos, y varios sistemas teóricos que son aún más poderosos que la máquina universal de Turing.

Ejemplos

Es difícil encontrar ejemplos de lenguajes no Turing completos, ya que esos lenguajes son muy limitados. Un ejemplo podrían ser las series de fórmulas matemáticas en una hoja de cálculo sin ciclos. Mientras que es posible hacer varias operaciones interesantes en ese sistema, éste falla en ser Turing completo ya que es imposible hacer ciclos. El lenguaje de macros de Excel, sin embargo, es Turing completo. Otro famoso ejemplo son las expresiones regulares contenidas en lenguajes como perl. Una lista de lenguajes Turing completos está bajo el rubro de teoría de la computabilidad.

Un importante resultado de la teoría de la computabilidad es que, en general, es imposible saber si un programa escrito en un lenguaje Turing completo se continuará ejecutando indefinidamente o se detendrá en un periodo finito de tiempo. Un método para prevenir que suceda lo primero es hacer que los programas se detengan después de un periodo fijo de tiempo. Estrictamente, esos sistemas no son Turing completos.

El cálculo lambda sin tipo es Turing completo, pero muchos cálculos lambda con tipo, incluyendo el Sistema F no lo son. El valor de los sistemas con tipo se basa en su habilidad de representar muchos de los programas de computadora "típicos" mientras se detectan sus errores.

Véase también

• 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