En la teoría de computadoras reales y virtuales, 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 de Turing universal. En otras palabras, el sistema y la máquina universal de Turing pueden emularse entre sí.
Aun 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.[1] En ese sentido laxo, todas las computadoras modernas son también Turing completas.
La completitud de Turing es significativa, pues, cada diseño verosímil 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 (ver Tesis de Church-Turing). 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.
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 serían aún más poderosos que la máquina universal de Turing.
Ejemplos
Muchos sistemas aparentemente simples resultan ser Turing completos. Ejemplos de sistemas de menor poder computacional 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. Otros ejemplos de lenguajes Turing incompletos son las expresiones regulares, o el lenguaje script de tipo pila que incorporan algunas cadenas de bloques como la de Bitcoin. 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.
turing, completo, para, otros, usos, este, término, véase, turing, desambiguación, teoría, computadoras, reales, virtuales, lenguajes, programación, otros, sistemas, lógicos, sistema, aquel, tiene, poder, computacional, equivalente, máquina, turing, universal,. Para otros usos de este termino vease Turing desambiguacion En la teoria de computadoras reales y virtuales de los lenguajes de programacion y de otros sistemas logicos un sistema Turing completo es aquel que tiene un poder computacional equivalente a la maquina de Turing universal En otras palabras el sistema y la maquina universal de Turing pueden emularse entre si Aun cuando es fisicamente imposible que existan estas maquinas debido a que requieren de almacenamiento ilimitado y probabilidad cero de falla de forma coloquial la completitud de Turing se atribuye a maquinas fisicas o lenguajes de programacion que podrian ser universales si tuvieran almacenamiento infinito y fueran absolutamente fiables La primera de esas maquinas aparecio en 1941 la Z3 de Konrad Zuse que era controlada por programas Su universalidad sin embargo fue demostrada mucho despues por Raul Rojas en 1998 1 En ese sentido laxo todas las computadoras modernas son tambien Turing completas La completitud de Turing es significativa pues cada diseno verosimil de un dispositivo de computacion por mas avanzado que sea aun las computadoras cuanticas pueden ser emuladas por una maquina universal de Turing Asi una maquina que pueda actuar como una maquina universal de Turing puede en principio hacer cualquier calculo que cualquier otra computadora es capaz de hacer ver Tesis de Church Turing Observese sin embargo que no dice nada sobre el esfuerzo de escribir un programa para la maquina o sobre el tiempo que puede tomar el calculo Esta la hipotesis de que el Universo es Turing completo ver implicaciones filosoficas en la Tesis de Church Turing y en Fisica digital Ver el articulo en Teoria de la computabilidad para una larga lista de sistemas que son Turing completos asi como varios sistemas que son menos poderosos y varios sistemas teoricos que serian aun mas poderosos que la maquina universal de Turing Ejemplos EditarMuchos sistemas aparentemente simples resultan ser Turing completos Ejemplos de sistemas de menor poder computacional podrian ser las series de formulas matematicas en una hoja de calculo sin ciclos Mientras que es posible hacer varias operaciones interesantes en ese sistema este falla en ser Turing completo ya que es imposible hacer ciclos El lenguaje de macros de Excel sin embargo es Turing completo Otros ejemplos de lenguajes Turing incompletos son las expresiones regulares o el lenguaje script de tipo pila que incorporan algunas cadenas de bloques como la de Bitcoin Una lista de lenguajes Turing completos esta bajo el rubro de teoria de la computabilidad Un importante resultado de la teoria de la computabilidad es que en general es imposible saber si un programa escrito en un lenguaje Turing completo se continuara ejecutando indefinidamente o se detendra en un periodo finito de tiempo Un metodo para prevenir que suceda lo primero es hacer que los programas se detengan despues de un periodo fijo de tiempo Estrictamente esos sistemas no son Turing completos El calculo lambda sin tipo es Turing completo pero muchos calculos 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 tipicos mientras se detectan sus errores Vease tambien EditarTesis de Church Turing Teoria de la informacion algoritmica El libro de Stephen Wolfram Un nuevo tipo de ciencia Algoritmo cuanticoReferencias Editar Link a paper en ingles Datos Q197970Obtenido de https es wikipedia org w index php title Turing completo amp oldid 120646778, wikipedia, wiki, leyendo, leer, libro, biblioteca,
