En la teoría de la computación , una máquina de Turing universal (a veces abreviada como MTU ) es una máquina de Turing capaz de simular las evoluciones de cualquier máquina de Turing. Esta máquina fue propuesta por Turing en su obra fundamental de 1936 y le permitió dar una respuesta negativa al problema de la decidibilidad, el llamado “ Entscheidungsproblem ”, planteado por David Hilbert en 1928 . [1]
De esta máquina, además de máquinas de Turing capaces de realizar elaboraciones particulares, se pueden identificar diferentes versiones caracterizadas por la disponibilidad de diferentes recursos. Los intérpretes modernos juegan el papel teorizado por el teorema de la existencia de la máquina de Turing universal.
Aquí nos referimos a la versión determinista con una cinta y con instrucciones de 5 campos que identificamos simplemente como máquina U. La máquina opera con una cinta que, cuando se quiere simular la evolución de una determinada máquina de Turing T mientras se procesa una determinada la cadena w, se carga inicialmente en su primera sección con una codificación adecuada de las instrucciones de la máquina T seguida, después de un marcador particular identificable, por la misma w.
En la evolución de la U se distinguen etapas sucesivas, cada una de las cuales corresponde a un paso en la evolución de la máquina T. En cada etapa, la primera sección de la franja de la U nunca se modifica, mientras que la segunda parte debe modificarse en la nueva cuerda para la T La simulación de un paso de la T se obtiene con una primera fase en la que la cabeza se desplaza desde la posición del segundo tramo, en el que estaba, hacia el primer tramo en busca del quíntuple que constituye el instrucción que el T debe ejecutar. Esta búsqueda se realiza con la U en estados que recuerdan qué instrucción se busca. Una vez encontrada la instrucción, hay una segunda fase de la U en la que la cabeza vuelve a la derecha hasta la posición en la que se debe realizar el paso evolutivo, mientras que los estados recuerdan cómo se debe realizar el paso para la T La tercera fase de la U se refiere a la ejecución del paso.
Podemos entonces comprender cómo con estos estadios evolutivos formados por tres fases la U puede simular todos los pasos del T, cualquiera que sea. Se observa que la máquina de Turing universal también es capaz de simular su propia evolución mientras procede a simular cualquier máquina T. También se observa que la evolución de la U es enormemente más fatigosa y más lenta que la evolución de la máquina T simulada: la generalidad de la gama de la U se paga con su bajísima eficiencia.
También está claro que la máquina de Turing universal tiene un papel puramente como un modelo computacional teórico, útil por las consideraciones generales a las que puede conducir y no por su capacidad para proporcionar resultados específicos (a través de maniobras extremadamente laboriosas y en un tiempo muy largo). Puede decirse que el primer segmento de la correa de la máquina U contiene el "programa" particular que le permite simular la máquina T particular. La máquina de Turing universal constituye por tanto un modelo de ordenador con programación interna.
Dentro de los videojuegos Dwarf Fortress , Minecraft [2] [3] y el juego de cartas Magic the Gathering [4] es posible crear una máquina de Turing universal. Tales juegos son, por lo tanto (accidentalmente) Turing completos .