¿El álgebra de Turing está completo?

Depende de qué tipo de álgebra, aunque es probable que casi cualquier álgebra sea completa de Turing, porque no es un requisito difícil y surge de elementos interactivos muy simples. Si considera que la teoría general de la recursividad, el cálculo lambda y los sistemas Post tag son formas de álgebras en el sentido, por ejemplo, de sistemas de reescritura , entonces ciertamente lo son y el modelo de Turing sería equivalente a un álgebra, si no un álgebra por sí mismo . En cuanto al álgebra que se nos enseña en la escuela, creo que está probado por Turing a través de conjuntos de diofantinas utilizados para resolver (en negativo) el décimo problema de Hilbert.

En cuanto a su conexión con la dinámica, como el problema de 3 cuerpos, es un poco complicado porque el problema de 3 cuerpos es un sistema continuo, mientras que la integridad de Turing se define en sistemas discretos. Pero bajo una renormalización, por ejemplo, entropía teórica de la medida (Kolmogorov-Sinai) o dinámica simbólica (que es lo que probablemente quiere decir con álgebra), no es difícil concebir cálculos con el problema de los 3 cuerpos (principalmente aprovechando soluciones estables) y cómo puede conducir a la indecidibilidad (principalmente en función de su comportamiento caótico) y, por lo tanto, a responder de manera positiva si ese sistema dinámico es completo en Turing.

Creo que sí, es completo de Turing, porque el cálculo lambda es, y el cálculo lambda es un álgebra.

Si se pregunta cómo puede conducir cálculos arbitrarios utilizando solo sustituciones y manipulaciones de símbolos (lo que significa álgebra, después de todo), Combinador de punto fijo (un ejemplo de esto es el combinador Y, donde el famoso fondo de capital de riesgo recibe su nombre) )

También, tesis de Church-Turing.