Exemplos de Máquinas de Turing
# Exemplos de Máquinas de Turing

Os exemplos a seguir são para complementar o artigo Máquina de Turing.

## Primeiro exemplo de Máquina de Turing

A tabela a seguir é o primeiro exemplo (Alan Turing 1937):
    "1. A máquina pode ser construída para calcular a sequência 0 1 0 1 0 1..." (0 <vazio> 1 <vazio> 0...) (Indecidível p. 119)
| Configuração | Configuração | Comportamento | Comportamento |
| m-configuração (estado) | Símbolo da fita | Operações na fita | m-configuração final (estado) |
| b | vazio | P0, R | c |
| c | vazio | R | e |
| e | vazio | P1, R | f |
| f | vazio | R | b |
Com relação às ações que a máquina realmente executa, Turing (1936) (Indecidível p. 121) afirma o seguinte:
    "Esta [exemplo] tabela (e todas as tabelas que seguem o mesmo tipo) deve-se entender como padrão que, para uma configuração descrita nas duas primeiras colunas, as operações na terceira coluna são realizadas sucessivamente, e, em seguida, a máquina passa por cima para a configuração-m na última coluna." (Indecidível p. 121)
Ele deixa isso muito claro quando ele reduz a tabela acima para uma única instrução chamado de "b" (Indecidível p. 120), mas sua instrução consiste em 3 linhas. Instrução "b" tem três possibilidades diferentes de símbolos {Nenhum, 0, 1}. Cada possibilidade é seguido por uma seqüência de ações até que cheguemos a coluna mais à direita, onde o m-configuração final é "b":
| m-configuração atual (instrução) | Símbolo da fita | Operações na fita | m-configuração final (instrução) |
| b | Nenhum | P0 | b |
| b | 0 | R, R, P1 | b |
| b | 1 | R, R, P0 | b |
Como observado por um número de influenciadores, incluindo o próprio Turing (1937), (por exemplo, Post (1936), Post (1947), Kleene (1952), Wang (1954)) as instruções de Turing não são atômicas — outras medidas de simplificação do modelo podem ser feitas sem reduzir o seu poder computacional; veja mais em Máquina de Post-Turing.
Como se afirma no artigo Máquina de Turing, Turing propôs que a tabela ainda ser atomizada, permitindo que apenas uma única imprimir/apagar seguido por uma fita simples movimento E/R/D. Ele nos dá este pequeno exemplo da primeira tabela convertida (Indecidível, p 127.):
| m-configuração atual (estado Turing) | Símbolo da fita | Operação de imprimir | Movimento da fita | m-configuração final (estado Turing) |
| q$_1$ | vazio | P0 | R | q$_2$ |
| q$_2$ | vazio | P vazio, i.e. E | R | q$_3$ |
| q$_3$ | vazio | P1 | R | q$_4$ |
| q$_4$ | vazio | P vazio, i.e. E | R | q$_1$ |
A declaração de Turing ainda implica cinco operações atômicas. A uma dada instrução (m-configuração) da máquina:
* observa o símbolo da fita abaixo da cabeça
* com base no símbolo observado vai para a sequência-instrução apropriada para usar
* imprima no símbolo S$_j$ ou apague ou não faça nada
* mova a fita para a esquerda, direita ou fique parada
* vá para a m-configuração final para esse símbolo
Como as ações de uma máquina de Turing não são atômicas, uma simulação da máquina deve atomizar cada 5-tupla em uma seqüência de ações mais simples. Uma possibilidade — utilizado nos seguintes exemplos de "comportamentos" de sua máquina — é como se segue:
    (q$_i$) Símbolos da fita de teste sob a cabeça: Se o símbolo for S$_0$ vá para o q$_i$.01, se o símbolo for S$_1$ vá para o q$_i$.11, se o símbolo for S$_2$ vá para o q$_i$.21, etc.
       (q$_i$.01) imprima o símbolo S$_j$0 ou apague ou não faça nada. Então vá para o q$_i$.02
       (q$_i$.02) mova a fita para a esquerda ou direita ou fique parado. Então vá para o qm0
       (q$_i$.11) imprima o símbolo S$_j$1 ou apague ou não faça nada. Então vá para o q$_i$.12
       (q$_i$.12) mova a fita para a esquerda ou direita ou fique parado. Então vá para o qm1
       (q$_i$.21) imprima o símbolo S$_j$2 ou apague ou não faça nada. Então vá para o q$_i$.22
       (q$_i$.22) mova a fita para a esquerda ou direita ou fique parado. Então vá para o qm2
    (etc — todos os símbolos devem ser contabilizados)
O chamado "canonical" Máquina de estados finitos faz os testes de símbolos "em paralelo"; veja mais em Microcode.
No exemplo a seguir do que a máquina faz, observamos algumas peculiaridades dos modelos de Turing:
    "A convenção de escrever os números apenas em quadrados alternativos é muito útil: Vou sempre fazer uso dele." (Indecidível p. 121)
Assim, quando a impressão que ele ignora todos os outros quadrados. Os quadrados impressos são chamados F-quadrados; os quadrados em branco no meio podem ser utilizados para "marcadores" e são chamados de "E-quadrados" como em "susceptível de apagamento." Os F-quadrados, por sua vez são os seus "Figuras quadrados" e só vai arcar com os símbolos 1 ou 0 — símbolos que ele chamou de "figuras" (como em "números binários").
Neste exemplo, a fita começa "em branco", e os "dados" são então impressas sobre ele. Para abreviar apenas a tabela-estados são mostrados aqui:
| Sequência | Identificador de instruçao | | | | | Cabeça | | | | | | | | | | | | | |
| 1 | 1 | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
| 2 | 2 | . | . | . | . | . | 0 | . | . | . | . | . | . | . | . | . | . | . | . |
| 3 | 3 | . | . | . | . | . | . | 0 | . | . | . | . | . | . | . | . | . | . | . |
| 4 | 4 | . | . | . | . | . | 1 | . | 0 | . | . | . | . | . | . | . | . | . | . |
| 5 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | . | . | . | . | . | . | . | . |
| 6 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . | . | . |
| 7 | 3 | . | . | . | . | . | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . | . |
| 8 | 4 | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . |
| 9 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . | . |
| 10 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . |
| 11 | 3 | . | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . |
| 12 | 4 | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . |
| 13 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . |
| 14 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 |
A mesmo "execução" com toda a fita-impressão intermediária e os movimentos são mostrado aqui:
Um olhar mais atento sobre a tabela revela certos problemas com o próprio exemplo &mdash de Turing, nem todos os símbolos são contabilizados.
Por exemplo, suponha que sua fita não foi inicializada em branco. O que aconteceria? A máquina de Turing iria ler valores diferentes do que os valores pretendidos.

## Uma cópia da sub-rotina

Este é um importante sub-rotina muito utilizado na rotina "multiplicar".
A máquina de Turing exemplo lida com uma série de 0s e 1s, com 0 representado pelo símbolo em branco. Sua tarefa é dobrar qualquer série de 1s encontradas na fita escrevendo um 0 entre eles. Por exemplo, quando a cabeça lê "111", vai escrever um 0, em seguida, "111". A saída será "1110111".
A fim de cumprir a sua missão, esta máquina de Turing vai precisar apenas 5 estados de operação, que são chamados {s$_1$, s$_2$, s$_3$, s$_4$, s$_5$}.Cada estado faz 4 ações:
* Leia o símbolo sob a cabeça
* Escreva o símbolo de saída decidida pelo estado
* Mova a fita para a esquerda ou para a direita decidido pelo estado
* Mude para o seguinte estado decidida pelo estado atual
| m-configuração inicial (instrução atual) | Símbolo da fita | Operações na fita | Movimento da fita | m-configuração final (próxima instrução) |
| s$_1$ | 0 | N | N | H |
| s$_1$ | 1 | E | R | s$_2$ |
| s$_2$ | 0 | E | R | s$_3$ |
| s$_2$ | 1 | P1 | R | s$_2$ |
| s$_3$ | 0 | P1 | L | s$_4$ |
| s$_3$ | 1 | P1 | R | s$_3$ |
| s$_4$ | 0 | E | L | s$_5$ |
| s$_4$ | 1 | P1 | L | s$_4$ |
| s$_5$ | 0 | P1 | R | s$_1$ |
| s$_5$ | 1 | P1 | L | s$_5$ |
| H | - | - | - | |
Uma "execução" das sequências da máquina através de 16 máquinas-configurações (também conhecido como "estados de Turing"):
| Sequência | Identificador de instrução | | | | | | Cabeça | | | | | |
| 1 | s$_1$ | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | s$_2$ | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | s$_2$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 4 | s$_3$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 5 | s$_4$ | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 6 | s$_5$ | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 7 | s$_5$ | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | s$_1$ | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 9 | s$_2$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 10 | s$_3$ | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 11 | s$_3$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 12 | s$_4$ | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 13 | s$_4$ | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 14 | s$_5$ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 15 | s$_1$ | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 16 | H | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
O comportamento da máquina pode ser descrito como um circuito: ele começa em s$_1$, substitui o primeiro 1 com um 0, em seguida, usa s$_2$ para mover para a direita, pulando 1s e o primeiro 0 encontrado. s$_3$, em seguida, salta a próxima seqüência de 1s (inicialmente não há nenhuma) e substitui o primeiro 0 que encontra com um 1. s$_4$ move para a esquerda, pulando 1s até encontrar um 0 e muda para s$_5$. s$_5$ então se move para a esquerda, pulando 1s até encontrar o 0 que foi originalmente escrito por s$_1$.
Ele substitui aquele 0 por um 1, move uma posição para a direita e digita s$_1$ novamente para mais uma rodada do loop.
Isso continua até que s$_1$ encontra um 0 (esta é a 0 no meio das duas seqüências de 1s), momento em que pára a máquina.

### Descrição alternativa

Outra descrição vê o problema como a forma de manter o controle de quantos "1"s existem. Nós não podemos usar um estado para cada número possível (um para cada estado de 0,1,2,3,4,5,6 etc), porque então precisaríamos de estados infinitos para representar todos os números naturais, e a máquina de estado é finita - nós vamos ter que controlar isso usando a fita de alguma forma.
A forma básica é que funciona, copiando cada "1" para o outro lado, movendo-se para trás e para frente - é inteligente o suficiente para lembrar que parte da viagem está conectado. Em mais detalhe, ele carrega cada "1" para o outro lado, através do reconhecimento da separação "0" no meio, e reconhecendo a "0", por outro lado para saber que é atingido o fim. Ele volta usando o mesmo método, o meio de detecção "0", e, em seguida, a "0" no lado original. Este "0" no lado original é a chave para o enigma de como ele mantém o controle do número de 1s.
O truque é que antes de colocar o "1", marca que dígito como "feito", substituindo-o com um "0". Quando ele retorna, ele preenche de que "0" para trás com um "1", passa então para o próximo, marcando-o com um "0" e repetindo o ciclo, levando que "1" de diâmetro e de forma ligar. Com cada viagem em frente e para trás, o marcador de "0" se move um passo mais perto do centro. É assim que mantém o controle de quantos "1" 's que os tomou durante.
Curiosamente, quando ele retorna, o marcador "0" parece ser o fim da recolha de "1" s para isso - qualquer "1" s que já foram tomadas através são invisíveis a ele (do outro lado do marcador "0 ") e por isso, é como se está a trabalhar sobre um número (N-1) de" 1 "s - semelhante a uma prova por Indução matemática.
Uma completa "execução" mostra os resultados de "movimentos" intermediários. Para vê-lo melhor, clique na imagem, em seguida, clique na maior resolução de download:

## Algoritmo do castor de 3 estados

A seguinte tabela Turing de instruções foi derivado de Peterson (1988) página 198, Figura 7.15. Peterson move a cabeça; no seguinte modelo a fita se move.
| Símbolo da fita | estado atual A | estado atual A | estado atual A | estado atual B | estado atual B | estado atual B | estado atual C | estado atual C | estado atual C |
| | escreve símbolo | move a fita | próximo estado | escreve símbolo | move a fita | próximo estado | escreve símbolo | move a fita | proximo estado |
| 0 | 1 | R | B | 1 | L | A | 1 | L | B |
| 1 | 1 | L | C | 1 | R | B | 1 | N | PÁRA |
O desenho "estado" do castor ocupado 3-estados mostra as sequências internas de eventos necessários para realmente executar "o estado". Como observado acima, Turing (1937) deixa perfeitamente claro que esta é a interpretação adequada dos 5-tuplas que descrevem a instrução (Indecidíveis, p. 119). Para saber mais sobre a atomização de Turing 5-tuplas ver Máquina de Post-Turing:
A tabela a seguir mostra o "comprimido" da execução e & mdash; apenas o Turing afirma:
| Sequência | Identificador de instrução | | | | | | | Cabeça | | | | | | | |
| 1 | b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | A | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | C | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | B | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | A | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | B | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | B | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 9 | B | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 10 | B | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 11 | B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 12 | A | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 13 | C | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 14 | H | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
A "execução" completa do castor ocupado 3-estados. Os resultantes do estados de Turing (o que Turing denominados "configurações-m" & mdash; "máquinas-configurações") são mostrados em destaque em cinza na coluna A, e também sob instruções da máquina (colunas AF-AU))