La respuesta definitiva está en este artículo : [1510.01671] La reprogramabilidad conductual transfronteriza revela evidencia de universalidad de Turing generalizada.
La respuesta es quizás bastante intuitiva para algunos y, por lo tanto, extremadamente sorprendente, pero señala hacia la dirección establecida por Wolfram y explicada por Todd Rowland en una de las otras respuestas a esta pregunta. Por lo tanto, fortalece, o tal vez incluso prueba, el Principio de Equivalencia Computacional de Wolfram.
Es cierto que depende de la enumeración elegida de las máquinas de Turing, pero para las “enumeraciones naturales”, por ejemplo, enumerando por tamaño o simplemente tomando un conjunto completo de máquinas de Turing de tamaño fijo, se puede demostrar que la densidad de los programas universales de Turing y así, las capacidades de reprogramación de los programas de computadora aleatorios (vea la explicación a continuación sobre lo que significa una máquina aleatoria de Turing) asintóticamente alcanza la medida 1 ( esto significa que la mayoría de ellos son Turing universales y eventualmente prácticamente todos ).
- ¿Cuál es el algoritmo más rápido para obtener la matriz inversa?
- ¿Alguna idea para optimizar una arquitectura de computadora (ISA) para un conjunto determinado de algoritmos?
- ¿Con qué frecuencia fallan las unidades en los servidores?
- ¿Cuál es el mejor sistema operativo de computadora de todos los tiempos?
- ¿Cómo se puede percibir Internet a través de una interfaz cerebro-computadora?
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.
Esta figura muestra cómo los programas informáticos (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). Esto significa que con la probabilidad asintótica 1, un programa de computadora ‘aleatorio’ (cf abajo) será capaz de realizar un cálculo universal.
Tenga en cuenta que la forma en que se prueba la universalidad de Turing para una máquina o autómata determinado es precisamente mediante la búsqueda de un compilador o codificador, como algunos lo llaman, este es el enfoque general para las pruebas de universalidad, desde Turing hasta Minsky’s hasta la Regla 110 de Cook y Wolfram , por mencionar algunos ejemplos (la Regla 110 requería una codificación basada en otro modelo de cómputo, una práctica común, un compilador entre 2 ‘lenguajes de programación’ diferentes).
También tenga en cuenta que uno puede generar programas de computadora o máquinas de Turing al azar al producir sus instrucciones / reglas basadas en un proceso aleatorio (por ejemplo, lanzar una moneda), cada bit es parte de un programa ejecutable, la mayoría de los programas resultarán no válidos pero uno toma solo los válidos y crea una distribución de programas. Este tipo de distribuciones se llama Distribución Universal (significa que la distribución no es asintóticamente confiable en la enumeración TM) como lo define Leonid Levin (el mismo matemático que coautorizó la pregunta de P = NP? Junto con S. Cook) y se basó en concepto de probabilidad algorítmica (R. Solomonoff). Vea, por ejemplo, nuestro trabajo sobre la creación de una distribución de salida a partir de una distribución de programas de computadora para aproximar numéricamente dicha Distribución Universal en el límite: Cálculo de la complejidad de Kolmogorov a partir de las distribuciones de frecuencia de salida de máquinas pequeñas de Turing
Además , 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 comenzar a aumentar el tamaño y obtener resultados como una función de tamaño TM, que es como se hizo en las dos referencias anteriores anteriores. Entonces, el marco para hacer esta pregunta está bien definido y ahora tiene una respuesta muy interesante, y creemos que es muy fundamental.
