Diferencia entre revisiones de «Turing completo»
Contenido eliminado Contenido añadido
m robot Añadido: ia:Turing complete |
Sin resumen de edición |
||
Línea 1:
En la teoría de [[computadora]]s reales e imaginarias, de los [[lenguaje de programación|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|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 confiables. La primera de esas máquinas apareció en [[1941]]: la [[Z3]] de [[Konrad Zuse]] y que era controlada por programas. Su universalidad, sin embargo, fue [http://www.zib.de/zuse/Inhalt/Kommentare/Html/0684/universal2.html demostrada] mucho después por [
La completitud de Turing es significativa pues, cada diseño plausible de un dispositivo de computación, por más avanzado que sea, (aún las [[computación cuántica|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). Observe, 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.
| |||