Típicamente hablamos de un sistema existente, ya definido, que se está completando con Turing. Así que no hay forma de “colarse” en una función de compilación; Se dan las reglas del sistema S. La definición de Turing-complete es que el sistema S puede simular cualquier máquina de Turing de una sola cinta (o, de manera equivalente, simular una máquina de Turing universal).
Su pregunta realmente es sobre lo que significa “simular”. Si mi sistema formal es muy simple, ¿por qué no puedo definir la simulación como “ejecutar la máquina de Turing hasta que se detenga y luego poner el resultado como la traducción S de ese estado final”? Hay un par de formas de abordar esto. Una es requerir asignaciones separadas de la máquina Turing y su cinta de entrada: un par de funciones en lugar de una sola función prohíbe ese tipo de acceso directo. El otro es exigir que el mapeo sea computable, lo que no es una máquina Turing integrada (o cualquier otra cosa que requiera resolver el problema de detención).
Una formulación (pero no la única) es arreglar una máquina universal de Turing T, y requerir una función computable F de cintas de máquina de Turing a estados en S, y una función computable de estados en S como “aceptar” o “no aceptar” . Luego defina S como Turing completo si para cualquier cinta [matemática] t [/ matemática], luego [matemática] S (F (t)) [/ matemática] se detiene en un estado de aceptación si y solo si [matemática] T (t ) [/ math] lo hace.
- ¿Cuáles son algunos trucos de acceso directo para las matemáticas? ¿Cómo puedo hacer cálculos muy, muy rápido? Editar: gracias chicos por tan buenas respuestas, aunque las conocía todas.
- ¿Cómo es probar un teorema que nadie ha probado antes?
- Cómo demostrar [matemáticas] e ^ {i \ pi} = - 1 [/ matemáticas] algebraicamente
- Si tengo la serie de Fourier de una función, ¿cómo puedo encontrar la función?
- ¿Podemos dividir un vector por un vector y por qué?
No necesita un paso de “descompilación”, la integridad de Turing se puede determinar mediante un mapeo de máquinas de Turing a S, que garantiza que S sea al menos tan potente como una máquina de Turing. Un mapeo bidireccional proporciona “equivalencia de Turing”.
