Turing Machine Simulation

A Máquina de Turing

Uma máquina de Turing é um modelo matemático de computação que descreve uma máquina abstrata que manipula símbolos em uma fita de acordo com uma tabela de regras. Apesar da simplicidade do modelo, ela é capaz de implementar qualquer algoritmo de computador.

A máquina opera em uma fita de memória infinita dividida em células discretas, cada uma das quais pode conter um único símbolo retirado de um conjunto finito de símbolos chamado de alfabeto da máquina.

Ela tem uma "head" que, em qualquer ponto da operação da máquina, está posicionada sobre uma dessas células, e um "estado" selecionado de um conjunto finito de estados. Em cada etapa de sua operação, a head lê o símbolo em sua célula. Em seguida, com base no símbolo e no estado presente da máquina, a máquina escreve um símbolo na mesma célula e move a head um passo para a esquerda ou para a direita, ou pára a computação.

A escolha do símbolo de substituição a ser escrito, a direção para mover a head e se vai parar é baseada em uma tabela finita que especifica o que fazer para cada combinação do estado atual e do símbolo lido. Como um programa de computador real, é possível para uma máquina de Turing entrar em um loop infinito que nunca irá parar.

A Invenção

A máquina de Turing foi inventada em 1936 por Alan Turing, que a chamou de "máquina a" (máquina automática). Foi o orientador de doutorado de Turing, Alonzo Church, quem mais tarde cunhou o termo "máquina de Turing" em uma revisão. Com esse modelo, Turing foi capaz de responder a duas perguntas negativamente:

1. Existe uma máquina que possa determinar se qualquer máquina arbitrária em sua fita é "circular" (por exemplo, congela ou falha em continuar sua tarefa computacional)?

2. Existe uma máquina que possa determinar se qualquer máquina arbitrária em sua fita imprime um dado símbolo?

Assim, fornecendo uma descrição matemática de um dispositivo muito simples capaz de computações arbitrárias, ele foi capaz de provar propriedades da computação em geral - e em particular, a incomputabilidade do Entscheidungsproblem ('problema de decisão').

Definição Formal

A máquina de Turing pode ser formalmente definida como uma 7-tupla M = (Q, Γ, b, Σ, δ, q0, F):

• Q é um conjunto finito e não vazio de estados;
• Γ é um conjunto finito e não vazio de símbolos do alfabeto de fita;
• b é o símbolo branco (o único símbolo permitido para ocorrer na fita infinitamente muitas vezes em qualquer etapa durante a computação);
• Σ é o conjunto de símbolos de entrada, ou seja, o conjunto de símbolos permitidos para aparecer no conteúdo inicial da fita, e é um subconjunto de Γ excluindo o símbolo branco b;
• δ é uma função parcial chamada função de transição, que mapeia um estado atual (exceto os estados finais) e um símbolo da fita para um novo estado, um símbolo da fita e uma direção de movimento da head (esquerda ou direita). Se δ não for definida para o estado atual e o símbolo da fita atual, então a máquina para; intuitivamente, a função de transição especifica o próximo estado transitado do estado atual, qual símbolo substituir o símbolo atual apontado pela head e o próximo movimento da head;
• q0 é o estado inicial;
• F é o conjunto de estados finais ou estados de aceitação. O conteúdo inicial da fita é dito ser aceito por M se eventualmente parar em um estado de F;