Projetando uma tabela de estados da Máquina de Turing

Question

Há alguma orientação útil para descrever o que uma máquina de Turing faz se você já possui o pseudocódigo do algoritmo?

Estou fazendo um curso de teoria da complexidade e demoro um pouco para descrever uma máquina de Turing que decide ou aceita alguma linguagem (estados, transições, etc.) mesmo sabendo como poderia codificá-la em algo como C ou mesmo assembly .Acho que não pratiquei o suficiente com máquinas de Turing (trabalhando nisso), mas agradeço qualquer sugestão.

editar

Não quero fazer um simulador de Máquina de Turing, quero descrever uma Máquina de Turing no papel (alfabeto, estados, transições) para decidir algum idioma.

Aqui está um exemplo trivial do que quero dizer: digamos que preciso escrever uma Máquina de Turing que passe por uma sequência de 0s e 1s e mude todos os 0s dela para 1s.Por exemplo, se você começar com 11010 na fita (entrada), ele parará com 11111 na fita (saída).Agora, em uma linguagem de alto nível, você sabe que é algo como:

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

A descrição da máquina de Turing é informalmente algo como:

Você tem dois estados, q e halt.Quando você estiver no estado Q e vê um 1, vá para a direita sem alterá -lo.Se você vir um 0, altere -o para 1 e vá para a direita.Se você vir o símbolo em branco (extremidade da fita), vá para o estado de interrupção.

Formalmente você terá algo como {q, halt} para estados.{((q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (parar, 0, L) )} para transições.

Ora, este problema é trivial, mas existem outros que são mais envolventes (adicionar números unários ou reconhecer uma linguagem com número igual de a's, b's e c's).Eu poderia facilmente escrever o pseudocódigo para eles, mas escrever a Máquina de Turing é muito mais desafiador (leva muito tempo) e eu queria saber se havia algumas dicas, recursos ou diretrizes que me ajudassem a melhorar na resolução de problemas como esse.

Answer 1

Isenção de responsabilidade: Sua pergunta é muito geral, portanto esta resposta também o é.Observe que eu sou tudo menos especialista em TMS, e essa abordagem geralmente não será muito eficiente (eu não posso prometer que sempre será eficaz).Estou apenas anotando alguns pensamentos aqui.

Eu sugeriria tentar uma abordagem como esta:Pegue seu pseudo-código e reduza-o para que consista apenas em a) variáveis ​​booleanas e b) if-declarações.Por exemplo:

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 você tiver aninhado ifs, substitua-os por andé;remover else blocos usando not:

if something:
    if something_else:
        do_a
    else:
        do_b

torna-se

if something and something_else:
    do_a

if something and not something_else:
    do_b

Cada if bloco deve então conter apenas um MOVE_TO_PREVIOUS ou MOVE_TO_NEXT, possivelmente um WRITE comando e qualquer número de atribuições variáveis.

Conclua tudo if cláusulas tais que cada um Dos seus booleanos e a letra atual é sempre verificada, duplicando os blocos onde NECESSARY.Exemplo:

if something and something_else:
    do_a

torna-se

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

Agora, se você tiver n booleanos e eu cartas, você deveria ter eu * 2ⁿ ifS.Imagine que você armazenou os booleanos em um campo de bits, então cada combinação possível de booleanos representa um número inteiro.Portanto, o acima se torna

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 então se torna

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

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

# ...

Este valor inteiro para o campo de bits é o estado da máquina de Turing.O do_a part é apenas uma atribuição aos booleanos (ou seja,O campo de bits, então é o seu novo estado), um comando de gravação (se não houver, apenas escreva a carta que já estava lá) e um comando de movimento, portanto, explicitamente uma transição da máquina de Turing.

Espero que qualquer uma das opções acima faça sentido.

Answer 2

Você precisa de uma ferramenta pronta para uso, simulador de máquina de Turing? Há Muitos disponíveis. Ou na verdade você quer fazer o seu próprio? Esta parece ser uma implementação válida no JavaScript: http://klickfamily.com/david/school/cis119/turingsim.html Você pode analisar o código e traduzi -lo em C ou C ++ com bastante facilidade.