Una máquina Turing universal puede emular cualquier otra máquina Turing (incluida ella misma), otra máquina Turing no puede. Sin embargo, lo que sí es cierto es que el conjunto de todas las máquinas de Turing es universal, pero una cosa es el conjunto y otras son máquinas de Turing individuales. Algunos son universales, otros no. Sin embargo, tiene razón en que una máquina de Turing universal es simplemente una máquina de Turing simple en sí misma, en el sentido de que no hay nada especial con su descripción o naturaleza y, por lo tanto, es esencialmente como cualquier otra, excepto por su poder computacional. Pero que la máquina universal de Turing sea solo una máquina de Turing es la base de uno de los principales resultados de Alan Turing en su artículo seminal que demuestra tanto la universalidad como la indecidibilidad del problema de Halting.
Sin embargo, pueden no ser tan diferentes después de todo, ¡porque este documento muestra que casi todas las máquinas de Turing son en realidad máquinas de Turing universales! :
[1510.01671] La reprogramabilidad conductual transfronteriza revela evidencia de universalidad generalizada de Turing.
- ¿En qué subáreas de matemáticas debería centrarme para mejorar mis algoritmos en informática?
- Cómo resolver este problema matemático discreto
- Para aquellos que son buenos en programación pero no en matemáticas, ¿qué les resulta difícil de las matemáticas?
- ¿Cómo decimos que un lenguaje no bombeable no es regular?
- ¿Qué campo en informática es un equilibrio entre matemática y programación?
Para las ‘enumeraciones naturales’, por ejemplo, enumerando por tamaño o simplemente tomando un conjunto completo de máquinas Turing de tamaño fijo, se puede demostrar que la densidad de los programas universales de Turing y, por lo tanto, las capacidades de reprogramación de los programas de computadora aleatorios (vea la explicación a continuación máquina aleatoria de Turing significa) asintóticamente alcanza la medida 1 ( esto significa que la mayoría de ellos son Turing universales y eventualmente prácticamente todos ).
El enfoque se basa en el concepto de ‘ universalidad intrínseca ‘, que proporciona una fuerte evidencia de la universalidad de Turing ubicua al explorar el espacio del compilador basado en el cálculo de reescalado y la emulación de grano grueso. Incluso mostramos una serie de resultados de cruce de límites, que incluyen instancias de emulación (en todos los casos para todas las condiciones iniciales) de Wolfram Class 2 Elementary Cellular Automata (ECA) por clase 1 ECA, clases 2 y 3 ECA emulando clases 1, 2 y 3 , y Clase 3 ECA emulando las Clases 1, 2 y 3, junto con resultados de un tipo similar para CA general (vecindario r = 3/2), incluyendo Clase 1 CA emulando las Clases 2 y 3, Clases 3 y 4 emulando todas las demás clases (1, 2, 3 y 4). Esto significa que no solo encontramos que la mayoría de los programas de computadora pueden emular a la mayoría de los otros programas de computadora, sino que incluso proporcionamos las codificaciones específicas.
En lugar de explorar programas de computadora aleatorios, uno puede hacerlo aún mejor no solo tomando una muestra de TM sino arreglando tamaños de TM y luego tomando un conjunto completo de TM para un tamaño dado y comience a aumentar el tamaño y obtenga resultados en función de TM tamaño, que es como se hizo en la referencia anterior. Entonces, el marco para hacer esta pregunta está bien definido y ahora tiene una respuesta muy interesante, y creemos que es muy fundamental. Aquí una figura que resume los resultados:
Esta figura muestra cómo los programas de computadora (AC sin pérdida de generalidad) alcanzan asintóticamente la universalidad intrínseca completa (y, por lo tanto, la universalidad de Turing porque la universalidad intrínseca es un requisito más estricto). El gráfico muestra los programas de computadora acumulados que pueden reprogramarse para comportarse como al menos otro programa de computadora (no trivial) en el mismo espacio de reglas con un compilador de hasta 15 (ECA) y 12 (GCA). Un compilador de computadora (como cualquier definición de compilador de computadora) es solo un programa de traducción que no actúa, pero al comienzo del cálculo y, por lo tanto, no está interactuando con el programa de computadora en cuestión (evidentemente, reglas triviales como las reglas 0 y 255 de ECA nunca se reprogramen pero son efectivamente de medida 0).
