¿Es el poder computacional de Probe Machine más fuerte que el de la máquina de Turing? ¿Por qué?

Distinguiría entre poder y capacidad. Suponiendo que la máquina de sonda esté completa, la capacidad computacional de una máquina de sonda es la misma que la de una máquina de Turing, ya que el rango de funciones que cualquiera puede realizar es el mismo.

El poder se define como la tasa de trabajo. Entonces, consideremos el poder computacional como la tasa de cálculo. Suponiendo que la misma velocidad de reloj para versiones sincrónicas o la velocidad de propagación de la señal para versiones asincrónicas de cada máquina, es probable que la máquina de prueba computeará muchas funciones a una velocidad más rápida debido a su paralelismo. Sin embargo, también tendrá muchos más componentes y probablemente usará más energía.

Para equilibrar las cosas, tendría que asignar los mismos recursos a cada constructor de máquinas. En ese caso, el constructor de Turing Machine podría cambiar la materia por energía, dado que necesita muchos menos materiales, y luego su máquina sería mucho más rápida y, por lo tanto, más poderosa :-).

Sería verdaderamente revolucionario, muy probablemente no. La tesis de Church-Turing establece que no hay nada computacionalmente más fuerte que una TM. Se ha mantenido cierto durante mucho tiempo.

En una nota al margen, ese artículo al que se refiere le iría bien con otra ronda de revisión por pares. Puedo ver por qué haces esta pregunta, ya que el texto en ocasiones casi parece afirmar esto, por ejemplo, cuando el texto dice “PM propuesto en este documento es un modelo matemático, cuya capacidad de cálculo y efectividad exceden las de TM”.

Difícil de distinguir de los resúmenes en papel, pero no veo ninguna referencia al no determinismo o la computación cuántica. Lo que indicaría que el paralelismo permite que se computen más operaciones simultáneamente, pero no cambia el número de operaciones requeridas. Por lo tanto, no cambia las medidas de complejidad computacional existentes basadas en máquinas de Turing, y no cambia los límites de computabilidad y capacidad de decisión. Sufrirá el mismo problema de detención. Sin embargo, gracias por la pregunta, me fascinaría leer los detalles cuando estén disponibles.