Comp
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