É necessário estabelecer modelos computacionais abstratos que exprimam os aspectos
práticos de uma computação. O modelo mais usado é o da máquina de Turing.
Definição 2.1 (Máquina de Turing determinıstica). Uma máquina de Turing deter-
minıstica é uma quádrupla M = (S,Σ, δ, s). Aqui S é o conjunto finito de estados,
onde s ∈ S determina o estado inicial da máquina. A máquina usa um conjunto fi-
nito de sımbolos, denotado Σ; esse conjunto inclui os sımbolos especiais BLANK e
FIRST1. A funç˜ao δ é a função de transição da máquina de Turing, mapeando S × Σ
em (S ⋃ {HALT, Y ES, NO}) × Σ × {←,→,STAY }. A máquina têm três estados:
HALT (o estado de parar), Y ES (o estado de aceitar), NO (o estado de rejeitar)(esses estados formalmente não estão em S).
A máquina de Turing determinıstica funciona da seguinte maneira [16]. A entrada da
máquina é geralmente vista como sendo escrita numa fita; a máquina pode ler e escrever nessa fita. Assumimos que HALT, Y ES e NO, e também os sımbolos ←, → e STAY ,como não pertencentes a S ⋃Σ. A máquina começa no estado inicial s com o cursor no primeiro sımbolo da entrada x; este sımbolo é sempre FIRST. O resto da entrada é uma sequência finita de sımbolos (“string”) de Σ \{BLANK,FIRST}; o sımbolo BLANK,situado a esquerda da fita, identifica o final da “string” de entrada.
A função de transição dita as acções da máquina e pode ser vista como o seu programa.
Em cada passo, a máquina lê o sımbolo α da entrada que está sendo apontada pelo
cursor. Baseado nesse sımbolo e no estado corrente da máquina, é escolhido o próximo
estado, um sımbolo β a ser sobreescrito em α e um movimento do cursor em direç˜ao `a
{←,→,STAY }, onde ← e → diz para o cursor mover para o próximo sımbolo `a esquerda
ou `a direita, respectivamente, e STAY diz para o cursor permanecer na posiç˜ao presente.
A função de transição é projetada para garantir que o cursor nunca saia do fim da entrada, identificado por FIRST. A máquina pode claramente sobreescrever o sımbolo BLANK.
Se a máquina pára no estado Y ES, dizemos que ela aceitou a entrada x. Se a máquina
pára no estado NO, dizemos que ela rejeitou a entrada x. O terceiro estado, HALT, é
para a computaç˜ao de funç˜oes que n˜ao sejam booleanas; nesses casos, a saıda da funç˜ao computada é escrita na própria fita. Um algoritmo corresponde a uma máquina de Turing que sempre pára.
Uma máquina de Turing probabilıstica corresponde a uma variação da máquina de Tu-
ring vista acima, adicionada da habilidade de gerar bits aleatórios em um passo [16]. Dado uma entrada x, a máquina de Turing probabilıstica aceita x com alguma probabilidade, como veremos na seç˜ao 2.2. A essa máquina corresponde um algoritmo probabilístico.
Fonte:
[em linha][consult 13 Dez 2009] Disponível em www:URL:
