Diferencia entre revisiones de «Turing completo»

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 [[computadora 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.

 

 

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.