Maquina Touring

1. Introdução

A máquina de Turing foi proposta por Alan Turing e 1936 e embora tenha sido criada anos antes do primeiro computador digital, tem uma grande importância para a ciência da computação, pois possui no mínimo o mesmo poder computacional de qualquer computador de propósito geral.

2.1. Máquina de Turing

Os aspectos básicos das maquinas de Turing são semelhantes aos dos Autômatos Finitos e Autômatos de Pilha, mas são capazes de reconhecer linguagens que são impossíveis para estes autômatos. A sua forma básica consiste de um controle finito, uma fita e um cabeçote que pode realizar leituras ou escritas na fita (ver Figura 1). Existem outras formas mais sofisticadas das máquinas de Turing que se utilizam de múltiplas fitas, máquinas com dispositivos de memória que podem ser lidos ou gravados em regime de acesso aleatório, mas nenhum dos modelos apresenta um poder computacional maior do que a forma básica. Uma visão amplamente aceita é de que qualquer forma aceitável de expressão das ideias contidas em um “algoritmo” seja, em última instância, equivalente à que pode se obter empregando-se uma máquina de Turing. A máquina de Turing foi idealizada para satisfazer os seguintes critérios:
Devem operar como Autômatos.
Devem ser simples de descrever, de definir e de entender.
Podem apresentar a maior generalidade possível quanto as computações que podem realizar.
Uma máquina de Turing consiste de um controle de estados finito associado a uma unidade de fita. A comunicação entre ambas é proporcionada por um simples cabeçote responsável pela leitura e escrita dos símbolos na fita. A unidade de controle opera de forma que a cada passo ela realiza duas operações, que dependem do seu estado atual e do símbolo lido da fita pelo cabeçote:
Levar a unidade de controle para um novo estado.
Gravar um símbolo na célula na posição apontada pelo cabeçote, ou então mover o cabeçote uma posição, para a esquerda ou direita.
A fita é delimitada na extremidade esquerda, mas