Turing completo

Turing completo
Para otros usos de este término, véase Turing (desambiguación).

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


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • 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 (llamada así por… …   Enciclopedia Universal

  • Turing (desambiguación) — Turing puede referirse a: Alan Turing. Fue un matemático, informático teórico, criptógrafo y filósofo inglés. Es considerado uno de los padres de la Ciencia de la computación siendo el precursor de la informática moderna. Test de Turing. Es una… …   Wikipedia Español

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • P-completo — En teoría de la complejidad computacional, la clase de complejidad P completo es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas. Un problema de… …   Wikipedia Español

  • Historia del hardware — La máquina analítica de Charles Babbage, en el Science Museum de Londres. El hardware ha sido un componente importante del proceso de cálculo y almacenamiento de datos desde que se volvió útil para que los valores numéricos fueran procesados y… …   Wikipedia Español

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Brainfuck — Saltar a navegación, búsqueda Brainfuck Paradigma: Esotérico Apareció en: 1993 Diseñado por: Urban Müller Implementaciones: Múltiples Influido por: Máquina de Turing …   Wikipedia Español

  • Juego de la vida — Animación del juego de la vida de Conway El juego de la vida es el mejor ejemplo de un autómata celular, diseñado por el matemático británico John Horton Conway en 1970. Hizo su primera aparición pública en el número de octubre de 1970 de la… …   Wikipedia Español

  • Z3 — Para otros usos de este término, véase Z3 (desambiguación). Réplica del Zuse Z3 exhibida en el Museo Alemán en Múnich. La computadora Z3, creada por Konrad Zuse en 1941, fue la primera máquina programable y completamente automática,… …   Wikipedia Español

  • Ook! — (con el signo de exclamación) es un lenguaje de programación esotérico Turing completo. Este lenguaje es una parodia de Brainfuck, del que toma su conjunto completo de comandos (ver tabla). Deriva su completitud Turing de esta relación. Según su… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”