El diseño de una tabla de estado de la máquina de Turing
-
21-09-2019 - |
Pregunta
¿Son las directrices útiles a la descripción de lo que lo hace una máquina de Turing si ya tiene el pseudo código para el algoritmo?
Me estoy tomando un curso sobre teoría de la complejidad y me toma un tiempo para describir una máquina de Turing que decide o acepta alguna lengua (estados, transiciones, etc.) a pesar de que sé cómo podría codificar en algo así como C o incluso el montaje. Creo que simplemente no he tenido suficiente práctica con las máquinas de Turing (trabajando en ello), pero agradecería cualquier sugerencia.
editar
No quiero hacer un simulador de máquina de Turing, quiero describir una máquina de Turing en papel (alfabeto, estados, transiciones) para decidir algún lenguaje.
Este es un ejemplo trivial de lo que quiero decir, digo que necesito para escribir una máquina de Turing que va sobre una serie de 0s y 1s y 0s cambia todo los en ella a 1s. Por ejemplo, si usted comienza con 11010 en la cinta (entrada) se detiene con 11111 en la cinta (salida). Ahora bien, en un lenguaje de alto nivel que se sabe que es algo como:
Go over every character on tape
If character is 0 change it to 1
La descripción de la máquina de Turing es informalmente algo como:
Usted tiene dos estados, q y alto. Cuando usted está en el estado q y ves un 1, ir a la derecha sin cambiarlo. Si se ve un 0, cambiarlo a 1 e ir a el derecho. Si aparece el símbolo en blanco (Final de la cinta) y luego ir a la parada estado.
Formalmente que tendrá algo como {q, detener} para los estados. {((Q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (alto, 0, L) )} para las transiciones.
Ahora bien, este problema es trivial, pero hay otros que son más envolvente (añadir números unarios o reconocer un lenguaje con igual número de unos de b, de, yc 's). Yo podría escribir el pseudocódigo para ellos, pero la escritura de la máquina de Turing es mucho más difícil (me lleva mucho tiempo) y me preguntaba si había algunos consejos, recursos, o directrices que me ayude a ser mejores para resolver problemas como ese.
Solución
Renuncia: Su pregunta es muy general, por lo tanto, también lo es que esta respuesta. Tenga en cuenta que yo soy otra cosa que un experto en TM y este enfoque por lo general no será muy eficiente (Ni siquiera puedo prometer que siempre será efectiva). Sólo estoy apuntando algunas ideas aquí.
sugeriría probar un enfoque como este: Tome su pseudo-código y reducirlo de manera que
que sólo se compone de a) variables booleanas y b) if
-declaraciones.
Por ejemplo:
if THIS_LETTER_IS("A"):
found_an_even_number_of_A = not found_an_even_number_of_A
if THIS_LETTER_IS("Q") and previous_letter_was_X and found_an_even_number_of_A
and not checking_for_alternative_2:
# can't be a word of alternative 1, so check for alternative 2
going_back_to_start_to_check_for_alternative_2 = True
if going_back_to_start_to_check_for_alternative_2:
MOVE_TO_PREVIOUS
else:
MOVE_TO_NEXT
if going_back_to_start_to_check_for_alternative_2 and THIS_LETTER_IS(EMPTY):
# reached the beginning, so let's check for alternative 2
going_back_to_start_to_check_for_alternative_2 = False
checking_for_alternative_2 = True
Cuando se tiene if
s anidados, reemplazarlos con and
s; eliminar los bloques else
utilizando not
:
if something:
if something_else:
do_a
else:
do_b
se convierte
if something and something_else:
do_a
if something and not something_else:
do_b
Cada bloque if
debe entonces sólo contener uno o MOVE_TO_PREVIOUS
MOVE_TO_NEXT
, posiblemente un comando WRITE
y cualquier número
de asignación de variables.
Completar todas las cláusulas if
tal que cada una sola de sus booleanos y la letra actual siempre es revisada, duplicadoras
los bloques donde es necesario. Ejemplo:
if something and something_else:
do_a
se convierte
if THIS_LETTER_IS("A") and something and something_else and something_i_dont_care_about_here:
do_a
if THIS_LETTER_IS("A") and something and something_else and not something_i_dont_care_about_here:
do_a
if THIS_LETTER_IS("Q") and something and something_else and something_i_dont_care_about_here:
do_a
if THIS_LETTER_IS("Q") and something and something_else and not something_i_dont_care_about_here:
do_a
Ahora, si usted tiene n booleanos y m letras, se debe tener m * 2 n if
s.
Imagínese que usted ha almacenado los valores booleanos en un campo de bits, por lo que cada combinación posible de booleanos representa una
entero. Por lo tanto el anterior se convierte
if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and bitfield[2]:
do_a
if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and not bitfield[2]:
do_a
# ...
que luego se convierte
if THIS_LETTER_IS("A") and bitfield == 7:
do_a
if THIS_LETTER_IS("A") and bitfield == 3:
do_a
# ...
Este valor entero para el campo de bits es el estado de la máquina de Turing. La parte do_a
es sólo una asignación a los booleanos (es decir, el campo de bits, por lo que es su nuevo estado), un comando de escritura (si no hay ninguno, acaba de escribir la letra que ya estaba
allí) y un comando de movimiento, por lo tanto, explícitamente una transición máquina de Turing.
Espero que alguna de las marcas sentido anteriormente.
Otros consejos
¿Necesita una herramienta lista para su uso, simulador de máquina de Turing? Hay bastante muchos disponibles . O realmente desea hacer su propia? Esta parece ser una aplicación válida en JavaScript: http://klickfamily.com/david/ la escuela / cis119 / TuringSim.html se podría analizar el código y traducirla en C o C ++ con bastante facilidad.