Prerrequisito – Problema de la máquina de Turing : Dibuje una máquina de Turing que multiplique dos números.
Ejemplo:
Pasos:
- Paso 1. Primero ignore los 0, C y vaya a la derecha y luego, si B encontró, conviértalo en C y vaya a la izquierda.
- Paso 2. Luego ignore los 0 y vaya a la izquierda y luego convierta C en C y vaya a la derecha.
- Paso 3. Luego, convierta todo X en X y vaya a la derecha si encuentra 0, conviértalo en X y vaya a la izquierda; de lo contrario, si encuentra C, conviértalo en B, vaya a la derecha y detenga la máquina.
- Paso 4. Si luego encuentra X, conviértalo en X y vaya a la izquierda, luego C en C y luego a la izquierda, luego Y en Y y a la izquierda.
- Paso-5. Luego, si B encontró, conviértalo en B y a la derecha, entonces si Y en 0 y a la derecha o si C en C y a la derecha, vaya al paso 3 y repita el proceso; de lo contrario, si 0 se encuentra después del 4to paso, conviértalo en Y y luego a la derecha Y en Y y derecha luego C en C y derecha luego 0 en 0 o X en X y derecha luego C en C y derecha luego 0 en 0 y derecha luego B en 0 y luego izquierda luego 0 en 0 y luego izquierda luego C en C y luego izquierda 0 en 0 o X en X y a la izquierda, luego C en C y a la izquierda.
- Paso-6. Luego repita el paso 5.
Aquí, q0 muestra el estado inicial y q1, q2, ….., q10, q11 son los estados de transición y q12 muestra el estado final.
Y X, Y, 0, C son las variables utilizadas para la multiplicación y R, L muestra derecha e izquierda.