TC - RESUMO - BIXETE

Prévia do material em texto

• MT recursiva = decidivel e nunca entra em um 
loop, ou ela aceita ou rejeita uma entrada 
• MT recursivamente enumerável= 
reconhecível entra em loop, e rejeição 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 • 51. (*) Uma MT executa por t passos. Então no Maximo quantas células diferentes da ta ela utilizou? 
Isto e, qual, no Maximo, o espaço utilizado pela MT? 
Conclua que se L Є TIME(n) então L Є SPACE(n). Mais 
geralmente, se L Є TIME(f), então L Є SPACE(f). 
• no máximo t células foram tocadas (lidas ou escritas) 
pela cabeça de leitura/gravação de cada uma das fitas. 
Em cada passo, a cabeça de leitura/gravação de cada 
uma das fitas só pode se movimentar única célula á 
direita ou á esquerda. Se o movimento for sempre em 
uma única direção, depois de t passos terão sido 
tocadas t células. Para cada inversão da direção de 
movimento uma célula é reutilizada. 
• Uma linguagem L pertence a TIME( f ) se existe uma MT 
M de decisão que toma uma entrada x e que termina a 
sua execução depois de um número de passos menor ou 
igual a c f (n) tal que x Є L sse M(x) = 1. Ou seja, M 
executa em tempo c f (n).Uma linguagem L pertence a 
SPACE( f ) se existe uma MT M que toma uma entrada 
x e que termina a sua execução depois de utilizar um 
número de células menor ou igual a c f (n) nas fitas de 
trabalho (todas exceto a de entrada e a de saída). Ou 
seja, M executa em espaço c f (n). 
 
Definição 2.2.6. Dizemos que uma MT de 
decisão M decide uma linguagem L se 
x Є L se e somente se M(x) = 1 
M(x) é o resultado da execução da MT M 
com a entrada x. A linguagem que uma MT 
M de decisão decide é denotada por L(M). 
Assim, se M decide L, então L = L(M). Usamos 
o símbolo M de uma MT para duas 
finalidades:(a) para a descrição da MT, como 
quando dizemos que M = (Q, , I, q) e (b) 
para a execução da máquina com certa 
entrada, como em M(x). 
 
 • 39) (*) O que e uma MT Universal? Quantas MT 
universais existem? Uma MT universal sempre para o 
seu processamento? 
• Uma maquina de turing universal(MTU) recebe como 
parâmetro uma maquina de turing M e uma entrada x, 
ela capaz simular qualquer máquina de turing. Não 
existe nada mais poderoso que uma MTU. Seu tempo 
de execução é indeterminado, com certa entradas ela 
pode nunca parar. 
• AMTU toma como entrada a descrição de uma 
máquina M e a entrada x desta máquina separados por 
t. A descrição de M é feita por uma codificação das 
suas instruções: cada instrução desta máquina é 
transcrita em símbolos da MTU 
 
Mostre como construir uma maquina de Turing de uma fita 
que simula uma MT k>1 fita. 
• Seja M= uma MTD com k fitas. Construímos uma 
MTD P com uma única fita equivalente a M. Ou seja 
M(x)= P(x) para p todo x se M parar a sua execução com 
x ou P(x) se M(x) (M(x) é usado para “M nunca termina 
a sua execução com a entrada x”). Assumindo que as 
celulas das MT’s são numeradas, sendo 0 a posição 
inicial da cabeça de leitura/gravação. As células a direita 
são positivas e as esquerdas negativas. As k fitas de M 
são representadas por um único símbolo de P que se 
encontra na posição 0 . Para cada símbolo criasse um 
outro simbolo para pode indicar qual a posição 
correta da cabeça de leitura/gravação. Se a codificação 
de um símbolo s de P na posição j da fita indicar que o 
simbolo da fita i de M é ~r ,então na simulação que P 
esta fazendo o simbolo da fita i é r e a cabeça de 
leitura/gravação desta fita esta sobre esta posição. 
 
 
 51. (*) Uma MT executa por t passos. Então no Maximo quantas células diferentes da ta ela utilizou? Isto e, 
qual, no Maximo, o espaço utilizado pela MT? Conclua 
que se L Є TIME(n) então L Є SPACE(n). Mais 
geralmente, se L Є TIME(f), então L Є SPACE(f). 
• Em cada passo, a cabeça de leitura/gravação de cada 
uma das fitas só pode se movimentar única célula á 
direita ou á esquerda. Se o movimento for sempre em 
uma única direção, depois de t passos terão sido tocadas 
t células. Para cada inversão da direção de movimento 
uma célula é reutilizada. Se uma linguagem Є TIME(n) 
,ou seja <=cn tempo então ela vai utilizar <=cn espaço , 
então obrigatoriamente se L Є TIME(n) então L Є 
SPACE(n), pq se utilizo tempo <=cn tbm utilizara espaço 
<=espaço de cn , se ela Є TIME(f), então L Є SPACE(f). 
 
 
Prove que a linguagem H={<M>x :M(x) } não é recursiva. 
Provaremos por contradição. Assumiremos que exista um algoritmo Para 
que decida H e chegaremos a uma contradição. 
Assumindo a existência de Para, podemos construir um procedimento Q: 
 procedure Q( T ) 
 begin 
 while Para(T, T) do 
 ; 
 end 
O ; depois da instrução while é um comando vazio—o while repete 
enquanto Para(T, T) for true sem executar nenhum comando. Quando 
chamamos Q passando a sua própria descrição, ou seja, Q(<Q>) . 
Neste caso, o comando while em Q significa simplesmente “não pare 
a execução desta chamada de <Q>, Q(<Q>), se e somente se Q(<Q>) 
termina a sua execução”. Ou seja, “não pare se e somente se páre”. 
De qualquer forma, Q parando ou não, há uma contradição. 
 Mostre como construir uma MT de uma unica 
fita que simula uma MT com 2 fitas 
• R: Para fazer a simulação só precisamos 
concatenar as fitas em uma única, isso é 
possível pois a fita é infinita, porem a 
quantidade de células computadas é finita. 
Exemplo: 
 Fita: ... 1 2 1 2 1 2 1 2 ... 
 M = | ..| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | .. | 
 
 
A tese pode ser descrita na seguinte frase: Toda função 
que seria naturalmente considerável computável pode 
ser computada por uma Maquina de Turing. Devido a 
imprecisão da frase 'Toda função que seria 
naturalmente considerada computável" a tese não 
pode ser provada. Qualquer programa de computador 
pode ser traduzido por uma maquina de turing e uma 
maquina de turing pode ser traduzida por uma 
linguagem de programação de propósito geral. Então a 
tese a seguir pode ser modificada para que qualquer 
linguagem de programação de propósito geral é 
suficiente para expressar qualquer algoritmo. 
 
Toda máquina de Turing tem uma maquina de Turing de uma 
única ta que lhe é equivalente. 
• PROVA Mostramos como converter uma MT multifita M 
para uma MT equivalente S de uma única fita. A idéia 
chave é mostrar como simular M com S. Digamos que M 
tem k fitas. Então S simula o efeito de k fitas armazenando 
sua informação na sua única fita. Ela usa o novo símbolo # 
como um delimitador para separar o conteúdo das 
diferentes fitas. Além do conteúdo dessas fitas, S tem que 
manter registro das posições das cabeças. Ela faz isso 
escrevendo um símbolo de fita com um ponto acima dele 
para marcar o local onde a cabeça na que la ta estaria. 
Pense nisso tudo como tas e cabeças “virtuais”. Tal qual 
antes, os símbolos de ta .marcados com um ponto. são 
simplesmente novos símbolos que foram adicionados ao 
alfabeto de ta. A seguinte gura ilustra como uma ta pode 
ser usada representar três tas. 
 
 
SAT é NP-completo. 
 
 
Time(f) С SPACE(f) 
• Prova: Seja L Є Time(f), então existe uma MT M 
decide L em tempo <= cf(n). Mas M que utilizara 
no Maximo <=cf(n) células .Portanto L é decidida 
por uma MT que executa em espaço <=cf(n) e L Є 
SPACE(f) 
• Suponha q SATE <=p L.Mostre que qq ling, em 
NP é polinomialmente redutível a L 
• k R 
Prova: K Є NP k SAT L x Є K sse K(x) Є SAT sse RsatL 
(K(x)) Є L 
P(n)= n^a 
T(n)= n^b----------------------------------------------- 
P(t(n))= (n^b)^a= n^ba que é polin 
 
 
R: Se L é recursiva , então existe uma 
MT que decide L, então temos uma 
M'(x) = 1 - M(x) que decide L^c, 
então L^c tb é recursiva, lembrando 
que L^c é o conjunto de entradas 
que não pertence a L. 
 
2^E *~ [0,1] 
• g: 2^E * -> [0,1] 
G(L) =0.cL(a0) cL(a1).... 
Considerando os nume. Do conj [0,1]em binário, 
g é bijetora 
E*={a0,a1,a2...} .Onde a0,a1,a2.. É uma 
enumeração de E* 
G(L)=0,101010...se g(L’)=0,001101010... L’ 
poderia ser conj dos primos. Como g é 
bijetora, 2^E *~ [0,1]. 
Entao |T|=|N|<|R|~|[0,1]|= 2^E * 
Concluimos que há MT p/ decidir ou enumerar 
todas as linguagens