Trabalho de turing

Maquina de Turing
Uma máquina de Turing é o modelo idealizado original de um computador, inventado por Alan Turing em 1936. Máquinas de Turing são equivalentes aos modernos computadores eletrônicos em um determinado nível teórico, mas diferem em muitos detalhes.
É feita por uma fita que vai tanto para esquerda quanto para direita , dividida em celula imediato a outra, que contem um simbulo, partindo para um cabeçote que le e escreve sibulos na fita, e movese tanto para um lado quanto para outro, registrador de estados que faz o amarzenamento do estados da maquina ,uma tabela com as funções de ação, é ela que determina qual vai ser o simbulo a escrever, qual ser seu novo estado, para que lado ela
Em qualquer momento, a cabeça que é posicionada sobre uma das praças na fita. Com esta cabeça, a máquina pode realizar três operações básicas:
*Leia o símbolo na praça sob a cabeça.
*Edite o símbolo escrevendo um novo símbolo ou apagá-lo.
*Mova a fita esquerda de direita em uma praça para que a máquina possa ler e editar o símbolo em uma praça vizinha.
Funcionamento:
1- A máquina de Turing lê o símbolo de fita que está sob cabeça da fita da máquina de Turing. Este símbolo é referido como o símbolo corrente.
2- A máquina de Turing usa sua função de transição para mapear o estado atual eo símbolo atual para o seguinte: o próximo estado, o próximo símbolo e o movimento para a cabeça da fita. Se a função de transição não está definido para o Estado e atual símbolo atual,
3- A máquina de Turing muda seu estado para o próximo estado, que foi retornado pela função de transição.
4- A máquina de Turing substitui o símbolo corrente na fita com o próximo símbolo, que foi retornado pela função de transição.
5- A máquina de Turing move sua cabeça da fita um símbolo para a esquerda ou para a direita, ou não se move a cabeça da fita, dependendo do valor do "movimento" que é retornado pela função de transição.
6- Se o estado da máquina de Turing é um estado parada, em