turing, maquina

Introdução
A máquina de Turing é um dispositivo teórico conhecido como máquina mundial, que foi concebido pelo matemático britânico Alan Turing, muitos anos antes de existirem os modernos computadores digitais. É um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento e não à sua implementação física.
Máquina de Turing com uma fita
Mais formalmente, uma máquina de Turing é normalmente definida como uma Tupla , onde é um conjunto finito de estados é um alfabeto finito de símbolos é o alfabeto da fita (conjunto finito de símbolos) é o estado inicial é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação) é o conjunto dos estados finais ⇒ é uma função parcial chamada função de transição, onde é o movimento para a esquerda e é o movimento para a direita.
Definições na literatura às vezes diferem um pouco, mas isto é sempre feito de maneira que a máquina resultante tem o mesmo poder computacional. Por exemplo, mudar o conjunto para , onde P permite ao cabeçote permanecer na mesma célula da fita em vez de mover-se para a esquerda ou direita, não aumenta o poder computacional da máquina.
Máquina de Turing com k fitas
Uma máquina de Turing com k fitas também pode ser descrita como uma 7-upla , onde é um conjunto finito de estados é um alfabeto finito de símbolos é o alfabeto da fita (conjunto finito de símbolos) é o número de fitas é o estado inicial é o símbolo branco é o conjunto dos estados finais ⇒ é uma função parcial chamada função de transição, onde é o movimento para a esquerda e é o movimento para a direita.
Note que uma máquina de Turing com "k" fitas não é mais poderosa que uma máquina de Turing tradicional.
A máquina final de Turing poderia ler qualquer conjunto de regras da sua fita. Turing provou que tal máquina, seria também um computador universal, isto é, poderia emular toda a máquina cujo