Cómo diseñar una máquina de Turing que acepte una cadena de longitud impar

Considere un escenario de cinta múltiple, donde la cinta superior tiene entrada. La cinta superior se desplaza al presionar todos los símbolos de entrada. Usaré el ejemplo:

BB 1 0 0 0 1 BB

La cinta inferior tiene dos símbolos:

BBXYBB

A medida que la entrada se lee, rebota entre X e Y. Cuando se lee el primer 1 , se mueve hacia la derecha en la cinta inferior desde B-> X. Luego, después de eso, rebotas entre:
operación de lectura de entrada
1 B-> X
0 X-> Y
0 X <-Y
0 X-> Y
1 X <-Y

Luego llegue a donde solo acepta si la cinta superior lee una B (indicando el final de la entrada) y la cinta inferior lee una X (indicando un número impar). ¡Espero que esto ayude!

Puede representar esto más fácilmente con un DFA o NFA, pero así debería explicarse una máquina de Turing.

¿Cuáles son algunas señales de que uno es un prodigio de la informática?

Teoría de conjuntos: ¿Cuál es la cardinalidad de [matemáticas] \ Sigma ^ * [/ matemáticas]?

¿Por qué la inducción es más omnipresente que cualquier otra técnica de prueba en informática y lógica matemática?

¿Hay buenos libros / artículos científicos sobre el problema de la capacidad de interpretación del aprendizaje automático (cajas negras, haciendo de las redes neuronales una caja blanca)?

¿Cuál es un mejor método para aprender sobre sistemas operativos, Linux desde cero o MINIX?

¿Qué tan difícil es ingresar al programa CSE en la Universidad de Washington?

Entonces, un número impar es un número que deja un resto de 1 después de la división por 2, ¿verdad? Podemos realizar la división por 2 en una máquina Turing usando un algoritmo simple.

Coloque la cabeza al comienzo de la cadena de entrada.

Si la cadena de entrada está vacía o todos los símbolos en la cadena de entrada están tachados, rechazar y detener.
si la cadena de entrada tiene una longitud 1, o solo hay un símbolo que no se ha tachado, entonces acepte y detenga.
Tache cualquier otro símbolo en la cadena de entrada que aún no se haya tachado.
Ve al paso 1.

Espero que esto ayude.

Mostafa Hany Gomaa

Ni siquiera necesita una máquina de turing para resolver este problema. Considere el siguiente autómata finito determinista:

Debería poder averiguar cómo se vería la TM equivalente. (Sugerencia: es bastante similar, solo necesita definir una función de transición y definir algunos formalismos).