Comp

Teoria da Computação
Computação Numérica Versão dos slides: 0.901
Prof. Dr.-Ing. Leonardo Andrade Ribeiro
DCC-UFLA, Lavras

Máquinas de Turing
Máquinas de Turing reconhece Linguagens

?
“Máquinas de Turing capturam e representam precisamente a noção abstrata a respeito do que é um algoritmo e quais são seus limites”
Prof. Dr.-Ing. Leonardo Andrade Ribeiro

“Modelo computacional universalmente aceito como possuindo poder de expressão equivalente aos computadores modernos”
2

Máquinas de Turing
 Até o momento, existem três possíveis resultados para computação: configuração de aceitação, configuração de rejeição, ou loop  O resultado de uma MT pode também ser definido em termos dos símbolos escritos na fita quando a computação termina
• Agora podemos ter um número infinito de possíveis resultados!

Prof. Dr.-Ing. Leonardo Andrade Ribeiro

3

Funções
 A função : → pode ser interpretada como um mapeamento que atribui um (e apenas um) elemento do contradomínio a um elemento do domínio  Atribuição para todos elementos de : função total; caso contrário, função parcial  ↑: não existe valor em atribuído a

Prof. Dr.-Ing. Leonardo Andrade Ribeiro

4

Computação de Funções
 Projeto de MTs para computar o valor de funções
• Elemento do contradomínio atribuído pela função a um elemento do domínio ; os elementos de representam a “entrada” da função

 Elementos de e são representados por palavras sobre o alfabeto de entrada
Prof. Dr.-Ing. Leonardo Andrade Ribeiro
5

Simplificações e Convenções
1→x, R

qu
Configuração de aceitação: MT encontra-se no estado de aceitação e lê um símbolo branco

˽→R,L

qa

1→x, R

qa
Prof. Dr.-Ing. Leonardo Andrade Ribeiro
6

Simplificações e Convenções (2)
 A computação inicia-se com um símbolo branco. A função do estado inicial é posicionar a cabeça e/l no ínicio da palavra de entrada

q0

˽→˽,R

qu

˽ q0 a

b

c

...

Prof. Dr.-Ing. Leonardo