¿Es el principio de equivalencia computacional de Stephen Wolfram simplemente una extensión de la tesis de Church-Turing y la máquina universal de Turing de Turing?

Definitivamente están relacionados y el principio de equivalencia computacional definitivamente llegó mucho más tarde, pero no lo llamaría una simple extensión.

La referencia principal para el PCE es el capítulo 12 de Stephen Wolfram: un nuevo tipo de ciencia. Dice dos cosas. Existe un nivel máximo de sofisticación computacional llamado universalidad, y en una enumeración de un tipo de reglas, los ejemplos de universalidad ocurren desde el principio.

Por lo tanto, niega la posibilidad en el mundo natural de los cálculos que exceden una máquina universal de Turing. Algunos teóricos han definido y estudiado tales cosas. Puedes presumir de que tu auto es más brillante que el suyo, pero tu computadora / cerebro / sapo / roca universal no es mejor que cualquier otro.

La segunda parte es más difícil de explicar brevemente, pero podría reiterar que las reglas simples pueden producir un comportamiento complejo. Esto es contrario a la intuición, especialmente la afirmación aquí es que está sucediendo en todas partes, donde sea que se pueda encontrar un comportamiento complejo.

No hay duda de que otros han especulado acerca de extender la tesis de la TC al mundo natural, pero su libro aporta muchas pruebas para apoyarlo. Además, puede ver muchas aplicaciones de PCE en este libro que en sí mismas no se siguen de CT.

Otra referencia es una conferencia que di hace unos años que puede encontrar en esta página, Wolfram Science Summer School: Resources, impartida en la Wolfram Science Summer School, donde he sido director académico.

Están relacionados pero son diferentes, mira mi blog explicando aquí:

Computación similar a la física, PCE de Wolfram y tesis de Church

Además, PCE está básicamente probado por este documento :

[1510.01671] La reprogramabilidad conductual transfronteriza revela evidencia de universalidad generalizada de Turing.

Señala hacia la dirección establecida por Wolfram y explicada por Todd Rowland en una de las otras respuestas a esta pregunta. Fortalece, o tal vez incluso prueba, el Principio de Equivalencia Computacional de Wolfram.

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 el papel. Entonces, el marco para hacer esta pregunta está bien definido y ahora tiene una respuesta muy interesante, y creemos que es muy fundamental. Estas cifras lo resumen muy bien:

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).