Maquina de Turing

Variações da Máquina de Turing

Sharbell Kemel da Silva, 121150108
Fernando da Rosa Oliveira, 121150113
Emilio Roberto Reginaldo Tubino, 121151541
Ricardo de Oliveira Dora, 121150115
Johnnie Menges Giacomelli,131151768

Roteiro
●

Máquina de Turing

●

Variações

●

−

Determinística

−
−

Não determinística
Cabeçote imóvel

−

Fita infinita para ambos os lados

−

Múltiplas fitas

−

Múltiplos cabeçotes

−

Universal

Bibliografia

Máquina de Turing
●

Proposta por Alan Turing em 1936

●

Formalização de algoritmo

●

Mesmo poder computacional de qualquer computador Máquina de Turing
●

Consiste de:
−

Fita de leitura/escrita
●
●

−

Símbolo de início de fita
Demais símbolos

Cabeçote
●
●
●
●

Estado inicial
Estados finais
Estado atual
Transições

●

Fita infinita em um dos lados

●

Quantidade de estados e símbolos finitos

Máquina de Turing
●

Funções de transição:
−

Ler símbolo em posição da fita
Modificar símbolo

−

Mover cabeçote

−

Mudar de estado

−

●

Exemplo:
(Q, r) → (S, t, {< ou >})

Q = estado atual

r = símbolo lido

S = novo estado

t = símbolo escrito

= direção de movimento (esquerda, direita)

Máquina de Turing
●

Pode ser representada por um grafo

Variações
●

●

●

A máquina de Turing possui várias variações
Não alteram o poder computacional da máquina Cada variação pode ser representada por uma máquina de Turing básica

Determinística
●

Máquina de Turing normal

●

Somente um resultado por entrada

Não-determinística
●

Um ou mais resultados por entrada

●

Máquina decide melhor caminho

Não-determinística
Não-determinismo é uma importante generalização dos modelos de máquinas.
No caso da Máquina de Turing, para o mesmo estado corrente e símbolo lido, diversas alternativas são possíveis. Cada alternativa é percorrida de forma totalmente independente.