Requisito previo: problema de la máquina de Turing : dibujar una máquina de Turing que copie datos.
Ejemplo –
Pasos:
- Paso 1. Primero convierta todos los 0, 1 en 0, 1 y vaya a la derecha, luego B en C y vaya a la izquierda
- Paso 2. Luego convierta todos los 0, 1 en 0, 1 y vaya a la izquierda, luego
- Paso 3. Si 1 lo convierte en X y va a la derecha, convierte todos los 0, 1 en 0, 1 y va a la derecha, luego convierte C en C y va a la derecha, luego convierte todos los 0, 1 en 0, 1 y va a la derecha, luego convierte B en 1 y va a la izquierda luego convierta todos los 0, 1 en 0, 1 y vaya a la izquierda, luego convierta C en C y vaya a la izquierda, luego convierta todos los 0, 1 en 0, 1 y vaya a la izquierda, luego convierta todo X en X y vaya a la derecha y luego repita todo el proceso desde paso-2 hasta el final
- Paso 4. Si 0, conviértalo en Y y vaya a la derecha, luego convierta todos los 0, 1 en 0, 1 y vaya a la derecha, luego convierta C en C y vaya a la derecha, luego convierta todos los 0, 1 en 0, 1 y vaya a la derecha, luego convierta B en 0 y ve a la izquierda, luego convierte todos los 0, 1 en 0, 1 y ve a la izquierda, luego convierte C en C y ve a la izquierda, luego convierte todos los 0, 1 en 0, 1 y ve a la izquierda, luego convierte todo Y en Y y ve a la derecha y luego repite todo el proceso desde el paso 2 hasta el final
- Paso-5. De lo contrario, si C encontró, conviértalo en C y vaya a la izquierda, luego convierta todo X en 1 e Y en 0 y vaya a la izquierda, luego convierta B en B y vaya a la derecha y detenga la máquina.
Máquina de Turing para copiar datos
Aquí, q0 muestra el estado inicial y q1, q2, ….., q9, q11 son los estados de transición y q12 muestra el estado final.
Y 0, 1 son los datos dentro de una máquina y X, Y, C son las variables utilizadas para copiar datos y R, L muestra derecha e izquierda.