El diseño de una tabla de estado de la máquina de Turing

Question

¿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.

Answer 1

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 ifs anidados, reemplazarlos con ands; 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 ⁿ ifs. 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.

Answer 2

¿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.