Encontré un artículo de Wikipedia de a list of Turing machine equivalents. Sin embargo, no indica un método para determinar si una máquina determinada es equivalente a la máquina de Turing.Cómo saber si una máquina es equivalente a la máquina de Turing
¿Necesito usar la definición de una máquina de Turing para probarlo? ¿Podría dar un ejemplo?
Gracias.
La forma estándar de probar que algo se ha completado es implementar uno de los equivalentes TM en su máquina. Si eso es posible, entonces su máquina está completa. Si no es así, entonces no lo es. Por lo tanto, si intentara probar, por ejemplo, que un nuevo lenguaje de programación está completo, escogería el equivalente TM que es más simple de implementar, y luego mostraré que mi lenguaje de programación puede simularlo.
De la parte superior de mi cabeza: si su máquina puede simular una de las máquinas equivalentes conocidas de la máquina Turing, entonces su máquina también es equivalente a la máquina Turing.
Probablemente la forma más fácil de hacerlo es hacer algo como esto.
EDITAR: No estoy implicando que este sea un requisito para que una máquina sea equivalente a la máquina de Turing, a pesar de que podría ser. ¿Tal vez alguien que es un poco más hábil en informática teórica puede aclararme esto?
Si muestra puedes simular una máquina de turing en tu modelo, estás mostrando solo una implicación (tu modelo es más poderoso que las máquinas de turing), la otra implicación necesaria para la equivalencia (las máquinas de turing pueden simular tu modelo) puede estar equivocada, pero la [iglesia- turing thesis] (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis) conjetura que la segunda implicación es siempre cierta. – Lapinot
En realidad, no se puede demostrar realmente. Al menos, la formalización completa de estas pruebas comunes de igualdad podría requerir una lógica mucho más formal de lo que cabría esperar incluso en la informática teórica. (si no está de acuerdo, dígame: estoy ansioso por hablar de esto.)
Sin embargo, es más claro desde el contexto. Intenta construir una simulación de una "máquina" de esquema de computación A dentro de otro modelo de computación B. Esto significa que B puede simular A, y por lo tanto tiene toda la potencia de A. Si lo haces viceversa, estos dos modelos se llaman equivalente.
Marque esta pregunta http://stackoverflow.com/questions/2550888/what-is-the-relationship-between-turing-machine-modern-computer – Cratylus
Creo que esto pertenece a cstheory.stackexchange.com – MSalters