La conception d'une table d'état machine de Turing

Question

Sont-ils des indications utiles pour décrire ce qu'est une machine de Turing fait si vous avez déjà le code de pseudo pour l'algorithme?

Je prends un cours sur la théorie de la complexité et il me prend un certain temps pour décrire une machine de Turing qui décide ou accepte une langue même si je sais comment je pourrais coder dans quelque chose comme C (états, transitions, etc.) ou même assemblage. Je suppose que je ne ai pas eu assez de pratique avec des machines de Turing (travaille), mais j'apprécie toutes les suggestions.

modifier

Je ne veux pas faire un simulateur de machine de Turing, je veux décrire une machine de Turing sur le papier (alphabet, états, transitions) pour décider une langue.

Voici un exemple trivial de ce que je veux dire, dis que je dois écrire une machine de Turing qui passe au-dessus d'une chaîne de 0 et de 1 et change tous les à 0 dans 1s. Par exemple, si vous commencez avec 11010 sur la bande (entrée), il arrête avec 11111 sur la bande (sortie). Maintenant, dans un langage de haut niveau vous savez qu'il est quelque chose comme:

Go over every character on tape
    If character is 0 change it to 1

La description de la machine de Turing est officieusement quelque chose comme:

  

Vous avez deux états, q et arrêt. Quand   vous êtes sur l'état q et vous voyez un 1, allez   à droite sans le modifier. Si   vous voyez un 0, changer à 1 et aller à   la droite. Si vous voyez le symbole vide   (Fin de la bande), puis aller à l'arrêt   état.

Formellement, vous aurez quelque chose comme {q, arrêt} pour les Etats. {((Q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (arrêt, 0, L) )} pour les transitions.

Maintenant, ce problème est trivial, mais il y a d'autres qui sont plus gratifiante (ajouter des numéros unaire ou reconnaître une langue avec nombre égal de A, années b et c de). Je pourrais facilement écrire le pseudocode pour eux, mais l'écriture de la machine de Turing est beaucoup plus difficile (me prend beaucoup de temps) et je me demandais s'il y avait des conseils, des ressources ou des lignes directrices qui me aident à mieux réussir à résoudre des problèmes comme ça.

Answer 1

Disclaimer: Votre question est très générale, est donc si cette réponse. Notez que je suis tout sauf un expert sur les mémoires de traduction, et cette approche ne sera généralement pas très efficace (je ne peux pas promettre même il sera toujours efficace). Je suis juste griffonner quelques réflexions ici.

Je suggère d'essayer une approche comme ceci: Prenez votre pseudo-code et réduire de telle sorte que il ne se compose que d'une) variables booléennes et b) if déclarations. Par exemple:

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

Lorsque vous avez imbriqué ifs, les remplacer par ands; retirer les blocs de else en utilisant not:

if something:
    if something_else:
        do_a
    else:
        do_b

devient

if something and something_else:
    do_a

if something and not something_else:
    do_b

Chaque bloc de if doit alors contenir qu'un seul MOVE_TO_PREVIOUS ou MOVE_TO_NEXT, peut-être une commande WRITE et un nombre quelconque des affectations de variables.

Remplir toutes les clauses de if telles que tous un seul de vos booléens et la lettre actuelle est toujours cochée, la duplication les blocs où neccessary. Exemple:

if something and something_else:
    do_a

devient

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

Maintenant, si vous avez n booléens et m lettres, vous devriez avoir m * 2 ⁿ ifs. Imaginez que vous avez enregistré les booléens dans un champ de bits, de sorte que chaque combinaison possible de booléens représente un entier. Par conséquent ce qui précède devient

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

# ...

qui devient alors

if THIS_LETTER_IS("A") and bitfield == 7:
    do_a

if THIS_LETTER_IS("A") and bitfield == 3:
    do_a

# ...

Cette valeur de nombre entier pour le champ de bits est l'état de la machine de Turing. La partie do_a est juste une affectation aux booléens (à savoir le bitfield, il est donc votre nouvel état), une commande d'écriture (s'il n'y en a pas, il suffit d'écrire la lettre qui était déjà y) et une commande de mouvement, par conséquent explicitement une transition de la machine de Turing.

J'espère que l'un des sens ci-dessus fait.

Answer 2

Avez-vous besoin d'un outil prêt à l'emploi, simulateur de machine de Turing? Il y a assez nombreux disponibles . Ou vraiment vous voulez faire votre propre? Cela semble être une implémentation valide en JavaScript: http://klickfamily.com/david/ école / cis119 / TuringSim.html vous pouvez analyser le code et le traduire en C ou C ++ assez facilement.