Redutibilidade
51 pág.

Redutibilidade


DisciplinaTeoria da Computação545 materiais16.681 seguidores
Pré-visualização3 páginas
posição da cabeça l/e, e o conteúdo da fita. Aqui, 
existem \ud835\udc5e estados. 
\uf0a7 O tamanho da fita é \ud835\udc5b, então a cabeça pode estar 
em \ud835\udc5b posições, e \ud835\udc54\ud835\udc5b possíveis palavras de 
símbolos do alfabeto da fita podem aparecer na 
fita. 
\uf0a7 O produto destas três quantidades é o número 
total de diferentes configurações de \ud835\udc40 com uma 
fita de tamanho \ud835\udc5b 
 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5: Prova 
\uf0a7 Idéia: Vamos \u201cobservar\u201c M por \ud835\udc5e\ud835\udc5b\ud835\udc54\ud835\udc5b 
configurações. Caso não páre durante este 
intervalo, então M está necessariamente 
repetindo configurações o que caracteriza um 
loop 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 4: Prova 
\uf0a7 S = \u201cNa entrada \ud835\udc40, \ud835\udc5d , onde \ud835\udc40 é um \ud835\udc34\ud835\udc3f\ud835\udc3f e 
\ud835\udc5d é uma palavra: 
1. Simule \ud835\udc40 em \ud835\udc5d por \ud835\udc5e\ud835\udc5b\ud835\udc54\ud835\udc5b até que \ud835\udc40 páre 
2. Se \ud835\udc40 parou, Aceite se \ud835\udc40 aceitou, Rejeite se \ud835\udc40 
rejeitou. Caso contrário, Rejeite 
50 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home (8) 
\uf0a7 Provas de decidibilidade podem ser realizadas 
atráves do estabelecimento de um limite para 
o processamento de uma MT 
\u2022 Após este limite a entrada é imediatamente 
rejeitada 
 
 
51