La máquina de Turing fue descrita por primera vez por Alan Turing en el año 1936. Fue inventada principalmente para investigar la computabilidad de un problema determinado. Acepta gramática de tipo 0, que es un lenguaje recursivamente enumerable. La máquina de Turing tiene una cinta de longitud infinita donde podemos realizar operaciones de lectura y escritura. Las celdas infinitas de la máquina de Turing pueden contener símbolos de entrada y espacios en blanco. Tiene un puntero de cabeza que puede moverse en cualquier dirección, apunta a la celda donde se lee la entrada.
Universal Turning Machine estimula una máquina de torneado. Universal Turing Machine puede considerarse como un subconjunto de todas las máquinas de Turing, puede igualar o superar a otras máquinas de Turing, incluida ella misma. Universal Turing Machine es como una máquina de Turing única que tiene una solución para todos los problemas que es computable. Contiene una descripción de Turning Machine como entrada junto con una string de entrada, ejecuta Turning Machine en la entrada y devuelve un resultado.
La diferencia entre Turing Machine y Universal Turing Machine es la siguiente:
|
Máquina de Turing |
Máquina de Turing Universal |
|
| 1. | Es un modelo matemático de computación que manipula símbolos en la cinta de acuerdo con las reglas definidas | Universal Turing Machine es como una única máquina de Turing que tiene una solución para todos los problemas que es computable |
| 2. | Un programa se puede comparar con una máquina de Turing | La máquina de Turing programable se llama máquina de Turing universal |
| 3. | El almacenamiento temporal de la máquina de Turing es la cinta. Las celdas infinitas de la máquina de Turing pueden contener símbolos de entrada y espacios en blanco. | Universal Turing Machine contiene la descripción de Turning Machine como entrada junto con una string de entrada, ejecuta Turning Machine en la entrada y devuelve el resultado. |
| 4. | Las máquinas de Turing nos ayudan a comprender las limitaciones fundamentales del poder de cálculo mecánico | Aunque se desarrolló por razones teóricas, ayudó en el desarrollo de computadoras con programas almacenados. |
| 5. | Una máquina de Turing es un modelo formal de una computadora con un programa fijo | Universal Turing Machine proporciona una solución a problemas que son computables |
| 6. | No minimiza la complejidad del espacio. | Minimiza la complejidad del espacio |
| 7, | La función de transición que realiza Turing Machine se define como: δ XT -> QXTX {L,R}, donde δ es la función de transición | La función de transición es Q × T → Q × T × {L, R}, donde Q es un conjunto finito de estados, T es la cinta del alfabeto |
| 8. | Desde el punto de vista de la teoría de conjuntos, todas las máquinas de Turing forman un conjunto de todos los dispositivos que aceptan gramática de tipo 0 | Universal Turing Machine es un subconjunto de todas las Turning Machines |
Publicación traducida automáticamente
Artículo escrito por aniruddharouth y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA