La progettazione di una Macchina di Turing tabella di stato del

Question

Ci sono le linee guida utili a descrivere ciò che una macchina di Turing non se hai già il pseudo-codice dell'algoritmo?

Io sto seguendo un corso sulla teoria della complessità e mi ci vuole un po ' per descrivere una macchina di Turing che decide o accetta in alcune lingue (stati, transizioni, ecc.) anche se so come potrei codice in qualcosa di simile a C o anche assieme.Credo che, semplicemente, non ho avuto abbastanza pratica con le macchine di Turing (lavorando), ma apprezzo ogni suggerimento.

modifica

Non voglio fare di una Macchina di Turing simulatore, vorrei descrivere una Macchina di Turing su carta (alfabeto, stati, transizioni) per decidere in alcune lingue.

Ecco un banale esempio di quello che intendo, dire che ho bisogno di scrivere di una Macchina di Turing che va oltre una stringa di 0 e 1 e le modifiche di tutti i 0 a 1s.Per esempio, se si inizia con 11010 sul nastro (input), si arresta con 11111 sul nastro di uscita (output).Ora in un linguaggio di alto livello, sai, è qualcosa di simile a:

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

La macchina di Turing descrizione informalmente qualcosa di simile:

Si dispone di due stati, q e lo stop.Quando si sono stato q e si vede un 1, andare a destra, senza dover cambiare.Se vedi 0, cambio a 1 e andare al destra.Se vedi il simbolo bianco (fine nastro) per poi andare alla sosta stato.

Formalmente si avrà qualcosa di simile {q, halt} per gli stati.{(q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (halt, 0, L))} per la transizione.

Ora questo problema è banale, ma ci sono altri che sono più coinvolgenti (aggiungere unario numeri o riconoscere una lingua con un numero uguale di a, b, e c).Potrei scrivere lo pseudocodice per loro, ma la scrittura è la Macchina di Turing è molto più impegnativo (mi prende un lungo periodo di tempo) e mi chiedevo se ci sono stati alcuni consigli, risorse, o linee guida, che mi aiutano a diventare migliori per risolvere problemi come il suo.

Answer 1

Disclaimer: La tua domanda è molto generica, quindi non è questa la risposta.Nota che io sono tutt'altro che un esperto di TMs, e questo approccio di solito non è molto efficiente (non riesco nemmeno promessa sarà sempre efficace).Sto solo buttando giù qualche pensiero qui.

Suggerisco di cercare un approccio come questo:Prendete il vostro pseudo-codice e ridurre così che si tratta solo di una) le variabili booleane e b) if-dichiarazioni.Per esempio:

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

Quando si hanno nidificato ifs, sostituirli con ands;rimuovere else blocchi utilizzando not:

if something:
    if something_else:
        do_a
    else:
        do_b

diventa

if something and something_else:
    do_a

if something and not something_else:
    do_b

Ogni if blocco dovrebbe quindi contenere solo uno MOVE_TO_PREVIOUS o MOVE_TO_NEXT, possibilmente un WRITE comando e l'eventuale numero di di assegnazioni di variabili.

Completo di tutti if le clausole del tipo che ogni singolo del tuo booleane E il carattere corrente è sempre controllato, duplicazione i blocchi dove necessario.Esempio:

if something and something_else:
    do_a

diventa

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

Ora, se si dispone di n booleane e m lettere, si dovrebbe avere m * 2ⁿ ifs.Provate a immaginare di avere memorizzato i valori booleani in un campo, in modo che ogni possibile combinazione di valori booleani rappresenta un integer.Da qui il sopra diventa

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

# ...

che poi diventa

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

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

# ...

Questo valore intero per il campo di bit che è la macchina di Turing stato.Il do_a è un compito per i valori booleani (es.il campo di bit, quindi è il vostro nuovo stato), un comando di scrittura (se non c'è nessuno, basta scrivere la lettera che è stata già c') e un comando di movimento, quindi in modo esplicito di una Macchina di Turing transizione.

Spero di sopra ha un senso.

Answer 2

Avete bisogno di uno strumento pronto per l'uso, Turing simulatore di macchina? Ci sono abbastanza molti disponibili . O in realtà si vuole creare il proprio? Questo sembra essere un'implementazione valida in JavaScript: http://klickfamily.com/david/ scuola / cis119 / TuringSim.html si potrebbe analizzare il codice e tradurlo in C o C ++ abbastanza facilmente.