TC-Lista de exercicios-Respostas

Prévia do material em texto

Vocês tem permissao para modificar dai se modificar coloca de uma outra cor e nao apaga o 
que foi escrito, olha nao tenho ctz de muita coisa que ta ae e tb nao liguem para os erros de 
ortografia! auhauha
 
1) ---
 
2) A simulação em uma MTND usando busca em profundidade é uma péssima escolha, pois 
essa busca pode fazer que nunca se encontre um estado de aceitação, fazendo com que essa 
busca não pare, sempre indo para o infinito. Uma escolha para se fazer a simulação seria a 
busca em largura. 
 
 
3) Assumindo uma MTD M com 3 fitas e uma MTND N, com entrada x e tanto para 
M quanto para N, definimos que N(x) sempre pára, podemos representar uma MTND em uma 
MTD. A MTD M realiza uma busca em largura na árvore de execução da MTND N realizando 
todas as suas computações. Quando é encontrado o estado QA (Estado de aceitação) a 
computação da MTD M termina, quando é encontrado o estado QR (Estado de rejeição) o 
passo representado no momento é retornado para o vertice anterior da MTND N e é trocado 
para o próximo caminho não deterministico. A fita de número 3 é usada para representar a 
simulação da MTND, a fita de número 2 é usada para representar o caminho da árvore da 
computacao, é representada por e1, e2, e3, ... , et, onde t é o numero de passos realizados no 
momento, a fita 1 representa o número de passos realizados no momento. Assim conseguimos 
representar uma MTND em uma MTD. 
 
4) Um codigo unário é representado por uma entrada de '1s', exemplo:
 1 - 1
 2 - 11
 3 - 111
 4 - 1111
 5 - 11111
 6 - 111111 
 ...
 
 Iremos realizar uma MT M onde que soma dois numeros unários, as entradas serão 
representadas em celulas da MT M separadas por um espaço.
 Exemplo:
 M = ...| | | 1 | 1 | 1 | | 1 | 1 | | | | | ... 
 C
 A cabeça (C) de leitura/escrita é posicionada no primeiro celula de entrada. 
 Passo 1:
 Se a leitura realizada for 1 entao se escreve 1 e vai para direita.
 M = ...| | | 1 | 1 | 1 | | 1 | 1 | | | | | ... 
 C
 M = ...| | | 1 | 1 | 1 | | 1 | 1 | | | | | ... 
 C
 Passo 2: 
 Se a leitura realizada for ' ' então se escreve 1 nessa posição e vai para a direita.
 M = ...| | | 1 | 1 | 1 | | 1 | 1 | | | | | ... 
 C
 M = ...| | | 1 | 1 | 1 | 1 | 1 | 1 | | | | | ... 
 C
 Passo 3:
 Se a leitura realizada for ' 1 ' então se escreve 1 e vai para direita.
 M = ...| | | 1 | 1 | 1 | 1 | 1 | 1 | | | | | ... 
 C
 Passo 4: 
 Se a leitura realizada for ' ' vai para esquerda e escreve 1. 
 M = ...| | | 1 | 1 | 1 | 1 | 1 | 1 | | | | | ... 
 C
 Passo 5: 
 Se a leitura realizada for ' 1 ' então se escreve ' ' e vai para direita.
 M = ...| | | 1 | 1 | 1 | 1 | 1 | | | | | | ... 
 C 
 Passo 6:
 Se a leitura for 1 escreve 1 e vai para esquerda.
 M = ...| | | 1 | 1 | 1 | 1 | 1 | | | | | | ... 
 C 
 M = ...| | | 1 | 1 | 1 | 1 | 1 | | | | | | ... 
 C
 ...
 
 M = ...| | | 1 | 1 | 1 | 1 | 1 | | | | | | ... 
 C 
 Passo 7:
 Se a leitura for ' ' escreve ' ' e vai para direita.
 M = ...| | | 1 | 1 | 1 | 1 | 1 | | | | | | ... 
 C 
 Com isso temos a posição da cabeça exatamente no inicio do valor da soma dos números 
unários.
 
5) -- 
 
6) OK
 
7) OK
 
8) Um automato finito normal não possui memoria, portanto, não tem a autonomia de retornar 
um estado ja computado, em contrapartida uma MT possui memoria, representado por uma 
ou mais fitas infinitas com celulas que representa um valor e uma cabeça de leitura ou escrita. 
Essa cabeça pode se locomover livremente entre as células dessa fita podendo ir para direita 
ou esquerda, portanto, possui memoria.
 
9) Não consegue fazer todas as computações porque ela perdeu a propriedade de poder 
guardar valores, portanto, não possui memoria, pq ela não consegue voltar para um estado 
anterior. Ela é comparado a um automato finito simples.
 
10) --
 
11) Um MT decidivel é uma máquina que para qualquer entrada ela SEMPRE PÁRA. Se a 
entrada não pertece a linguagem a MT retorna 0, se a linguagem pertence a linguagem ela 
retorna 1. Já uma MT qualquer pode ser que ela nunca pare.
 
12) Não, pois a MT M é uma maquina qualquer, então ela nem sempre para, se a maquina M 
não aceita a entrada x então M(x) não para, o algoritmo correto seria:
 
 funcao(x)
 Begin
 if M(X) == 1 then
 return 1
 else
 while true dois
 ;
 end if
 end
 
 
13) Não, porque pode existir alguma entrada na linguagem que pode fazer com que a maquina 
nunca pare.
 
14) Sim, pois se a entrada não pertence a linguagem ela irá retornar 0 e se a entrada pertence 
a linguagem a maquina irá retornar 1. Uma MT decidivil sempre pára.
 
15) Para fazer a simulação so precisamos concatenar as fitas em uma unica, isso é possível 
pois a fita é infinita, porem a quantidade de celulas computadas é finita.
Exemplo:
 Fita: ... 1 2 1 2 1 2 1 2 ...
 M = | ... | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | ... |
 
16) Para poder fazer a simulação de 2 ou mais fitas em uma MT de uma fita podemos 
representar as entradas analisadas por um unico simbulo na MT de uma unica fita.
 Exemplo:
 Tenho uma MT M com 3 fitas e queremos representa-la em uma MT N com uma fita, 
tendo Si como i-ésimo simbulo lido da primeira fita, Sj j-ésimo simbulo lido na segunda fita e Sk 
o k-ésimo simbulo lido na terceira fita :
 
 M = 
 | ... | Si | ... |
 | ... | Sj | ... |
 | ... | Sk | ... |
 
 Entao N possui um Jijk que representa os simbulos Si,Sj e Sk
 
 N = | ... | Jijk | ... | 
 
Então o alfabeto da máquina N vai ter um símbolo pra cada combinação de k símbolos do 
alfabeto de M?
Por exemplo, se o alfabeto de M for {0, 1}, o de N será {00, 01, 10, 11}? 
(pra duas fitas, no caso)
 ISSO! =D 
 
17) Temos uma MT N com uma fita infinita tanto para esquerda quanto para a direita, 
queremos representala em uma MT M que possui uma fita infinita somente para a direita. 
Como os numeros naturais são equipotentes para os numeros inteiros então podemos 
enumerar da seguinte forma:
 -2 -1 0 1 2
 N = | ... | | | | | | ... | 
 
 M pode representar N assim:
 0 1 -1 2 -2 ...
 M = | | | | | | ... |
 
 
18) É o inverso do exercício anterior, por exemplo: (comecei M no 1 por comodidade, como 
ninguém sabe realmente se os naturais começam no 1 ou no 0, não deve ser problema)
 1 2 3 4
M = | | | | | ...
 
E sendo:
 -2 -1 0 1 2
N = … | | | | | | ...
 
Podemos mapear os índices i da fita de M para a de N através da função
 
f(i) = 
if i % 2 == 0 --> - floor(i/2)
if i % 2 == 1 --> floor(i/2)
 
Dessa forma os índices em M seriam:
 0 -1 1 -2
M = | | | | | …
 
 
19) Não, pois o conjunto dos numeros naturais é equipotente ao conjunto dos numeros inteiros, 
portanto conseguimos enumeralos.
 
20) Não, elas tem a mesma quantidade de células, pois conseguimos enumerar essas k fitas 
em uma unica fita pois osnumeros Inteiros são equipotentes aos numeros (inteiros)^k.
 
21) Os conceitos de enumeração de conjuntos.
 
22) Uma linguagem L é considerada recursiva se somente se existir uma MT que enumera 
crescentimente os elementos dela. Assumimos que L esta contido em E*, e a ordem crescente 
é a ordem induzida da ordem dos elementos de E. Seja N a MT que enumera os elementos de 
L em ordem crescente. Faremos uma M que decide se x pertence a L ou não, com x sendo a 
entrada de M.
 N simula a execução de M até que está produza um elemento maior que x, que é a entrada 
de M. Se x tiver sido enumerado entao N escreve 1 e vai para o estado QA e pára, senao N 
escreve 0 e vai para o estado QR e pára.
 Suponha que L é recursiva, entao existe um algoritmo elem(i) que retorna o i-esimo elemento 
de E* na ordem lexicográfica. A MT que implementa o seguinte algoritmo enumera em ordem 
crescente os elementos de L:
 
 i = 0;
 while true do 
 begin 
 if elem(i) pertence a L
 then
 imprima elem(i);
 end if
 i = i + 1;
 end 
 
23) ---
 
24) Sendo T o conjunto de todas as MT entao T ~ conjunto dos naturais, pois T é infinito e |T| 
<= conjunto dos naturais. 
 Temos um S = { L : L C E* }
 S = 2^E*
 Existe f: S -> [0,1] bijetora
 entao:
 E* = { 0, 1, 00, 01, 10 , 11, 000 , ...}
 
 conseguimos entao uma entrada x pertencente a [0,1] :
 0 1 1 0 1 0 1 ... 
 | | | | | | | |
 E*={0, 1, 00, 01, 10, 11, 000, ... }
 
 Com isso L = {1,00,10,000, ...} 
 Logo 2^E* = S ~ [0,1] ~ Conjunto dos reais
 |S| => |T|. Logo há linguagens indecidíveis. 
 
25) A tese pode ser descrita na seguinte frase:
 Toda função que seria naturalmente consideravel computável pode ser computada por 
uma Maquina de Turing. Devido a imprecisao 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. Entao a tese a seguir pode ser modificada 
para que qualquer linguagem de programação de propósito geral é suficiente para expressar 
qualquer algoritmo.
 
26) Uma linguagem recursivamente enumerada é computavel, ou seja, existe um algoritmo 
que reconhece essa linguagem, porem, não necessariamente para qualquer entrada. Uma 
linguagem é computavel quando existe uma maquina de turing que sempre pára para cadeias 
pertencentes a linguagem, para cadeias fora da linguagem a maquina de turing não para. Um 
exemplo dessa linguagem é : 
 L = {WW | W é uma palavra sobre os simbulos A e B}
 
27) Uma linguagem é recusiva ou também chamada de decidivel quando existe uma MT que 
reconhece a linguagem e sempre pára. Retorna 0 caso a entrada não pertence a linguagem ou 
retorna 1 caso a entrada pertence a linguagem. Um exemplo para ela é :
H = {<M> _ x : M(X) pára} não é recursiva mas é r.e. (By Teta) 
28) 
 
 L = {2 * n | n >= 0}
 
 i = 0;
 while true do
 begin 
 if par(i) pertence a L then
 imprima par(i);
 end if
 i = i + 1;
 end
 
 
29) Um número de linguagens em um dado alfabeto. S = {L | L C E*} , S = 2^E* ~ Reais (já 
provado anteriormente!) 
O complemento de H (exercício 27) não é recursivamente enumerável.(By Teta)
 
 
30) 
 
 binario(x) =
 Desenho em meu caderno:
 (q0, 1, q1, 1, D)
 (q0, 0, q1, 0, D)
 (q0, espaço, qR, espaço, D)
 (q1, 0, q1, 0, D)
 (q1, 1, q1, 1, D)
 (q1, espaço, qA, espaço, D)
 i = 0
 while true do
 if binario(i) pertece a L then
 imprima binario(i)
 end if
 i = i + 1
 end
 
 Como na MT do binario a entrada sempre será um binário e como no fim sempre se 
escreve um espaço e vai para direita, sempre é conservado o estado anterior da MT, com isso 
conseguindo escrever em seguincia todos os numeros binários. Logicamente essa máquina 
nunca irá parár pois existe um enumerador que não deixa isso acontecer
 
31) 
 
Utilizaremos M como sendo a MT (binario(x)) feita no exercicio anterior.
Configuracao:
 M1(0) M2(0) M3(0) M4(0) ...
 M1(1) M2(1) M3(1) M4(1) ...
 M1(2) M2(2) M3(2) M4(2) ...
 M1(3) M2(3) M3(3) M4(3) ...
 ... ... ... ... ...
 
 
Algoritmo:
passoExecN é o e-nésimo passo da execução de M(x)
 
begin 
 passoExecN = 1;
 while true do
 entrada = 0;
 k = passoExecN;
 while passoExecN > 0 then
 if M(entrada) pertence a L then
 imprimaFita3 M(entrada);
 end if
 passoExecN = passoExecN - 1;
 entrada = entrada + 1;
 end while
 passoExecN = k + 1; 
 end while
end 
 
32) 
Assumindo uma MT N com 3 fitas e uma MT com uma fita, onde na primeira fita possui os 
números inteiros separados por um espaço , na segunda fita será simulado a M e na terceira 
fita será imprimido todas as MT M que param com uma determinada entrada.
Configuracao:
 M1(0) M2(0) M3(0) M4(0) ...
 M1(1) M2(1) M3(1) M4(1) ...
 M1(2) M2(2) M3(2) M4(2) ...
 M1(3) M2(3) M3(3) M4(3) ...
 ... ... ... ... ...
 
 
 
Suponha que exista um algoritmo para(P espaço E) no qual P é <M> e E a entrada. 
Para representar a configuração acima é necessario saber qual maquina M está
sendo simulada. Exemplo : Similando o primeiro passo de M com a entrada 0 = para(<M 1> 
espaço 1) entao:
Algoritmo:
begin 
 passoExecN = 1;
 while true do
 entrada = 0;
 k = passoExecN;
 while passoExecN > 0 then
 if para(<M passoExecN> espaço entrada) == 1 then
 imprimaFita3 para(<M passoExecN> espaço entrada);
 end if
 passoExecN = passoExecN - 1;
 entrada = entrada + 1;
 end while
 passoExecN = k + 1; 
 end while
end 
 
Temos na fita 3 todas as Maquinas que param. 
 
 
33) Não existe como enumerar pois :
 
 Procedure Q (P espaço entrada)
 begin 
 while para(P espaço entrada) == 1 do 
 ;
 end while
 end
 Com isso fica trivial que é impossivel enumerar.
 [Allan]
Tem um jeito bem mais fácil :D
Se L é recursiva, há uma máquina M que decide L. Para que ela seja RE, deve existir uma 
máquina N que reconheça L (ou seja, ou aceita, ou para, ou fica em loop). Basta modificar a 
máquina M fazendo o estado de rejeição dela passar a ter um laço infinito para ele mesmo.
[/Allan]
 
 
34)
 
isso me parece uma gambiarra estranha, não soa digno de teóricos da computação hauhauha 
 
[Allan]
Tem um jeito bem mais fácil :D
Se L é recursiva, há uma máquina M que decide L. Para que ela seja RE, deve existir uma 
máquina N que reconheça L (ou seja, ou aceita, ou para, ou fica em loop). Basta modificar a 
máquina M fazendo o estado de rejeição dela passar a ter um laço infinito para ele mesmo.
[/Allan]
 
Se L é uma linguagem recusiva entao L tb é uma linguagem recursivamente enumerada. L 
pode ser computada pela MT M entao:
 
 Procedure Q(x)
 begin
 if M(x) == 1 then
 return 1
 else
 while true do 
 ;
 end if
 end
 Com esse algoritmo conseguimos provar que uma linguagem recursiva tb é uma linguagem 
recursivamente enumerada. Pois se a linguagem recursiva retornar 1 a maquina pára e 
se M retornar 0 ela entra em um loop onde não irá parar, essa propriedade de não parar é 
justamente a diferença entre uma linguagemrecursiva e uma linguagem recursivamente 
enumerada. 
 
35) 
 Se L é recursiva , então existe uma MT que decide L,
 entao temos uma M'(x) = 1 - M(x) que decide L^c, entao L^c tb é recursiva, lembrando que 
L^c é o conjunto de entradas que nao pertece a L.
 
36)
Se L é Recursivamente enumerada entao:
 Conseguimos enumerar tanto L qndo L^c:
 L = a1, a2, a3 , a4 ... Pertence a L
 L^c = b1, b2, b3, b4, ... Não pertence a L.
 
 Construimos uma MT M recursiva que:
 x pertence a L -> M(x) = 1
 x nao pertece a L -> M(x) = 0
 
37) 
Não tenho ctz disso!
a) Decide a Linguagem A = (L UNION K)^c
b) Decide a Linguagem B = L - K
c) Decide a Linguagem C = L + K
d) Decide a Linguagem D = L^c.
e) Decide a Linguagem E = A^c.
 
38) ---
 
 
39) Uma maquina de turing universal(MTU) recebe como parametro 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.
 
40) --- 
 
41) Conseguimos construir uma nova MT que computa f apartir da MT M e acrescentando 
um estado que não tem utilidade conseguimos sempre uma nova MT que reconhece f. Assim 
conseguimos representar infinitas MT sempre acrescentando um novo estado.
 
42) --- 
 
43) H = {<M> espaço x : M(x) para}
 
Configuracao:
 
 M0(0), M0(1), M0(2) ...
 M1(0) M1(1), M1(2) ... 
 M2(0) M2(1), M2(2) ...
 M3(0) M3(1), M3(2) ...
 
 Primeiro passo executo M0 com a entrada 0, segundo passo executo M0 com entrada 1 e 
M1 com entrada 0, terceiro passo executo M0 com entrada 2, M1 com entrada 1 e M2 com 
entrada 0 e assim por diante. 
 
 Não conseguimos decidir se uma maquina irá parar ou não (já foi provado com um algoritmo 
anterior) mais ela é recursivamente enumerado.
 Sempre que envolve computação é não decidível!
 
44) S ~ 2^Conjunto dos naturais
Prova:
Temos um S = { L : L C E* }
 S = 2^E*
 Existe f: S -> [0,1] bijetora
 entao:
 E* = { 0, 1, 00, 01, 10 , 11, 000 , ...}
 
 com isso temos um x pertencente a [0,1] x = {0.101010...}
 f pertence 2^conjunto dos naturais associada a L tal que
 S ~ 2^ConjuntodosNaturais 
45) Com a prova acima conseguimos dizer tb que :S ~ 2^ConjuntodosNaturais ~ 
conjuntoDosNaturais^ConjuntoDosNaturais ~ [0,1]
 
46)
Temos um S = { L : L C E* }
 S = 2^E*
 Existe f: S -> [0,1] bijetora
 entao:
 E* = { 0, 1, 00, 01, 10 , 11, 000 , ...}
 
 conseguimos entao uma entrada x pertencente a [0,1] :
 0 1 1 0 1 0 1 ... 
 | | | | | | | |
 E*={0, 1, 00, 01, 10, 11, 000, ... }
 
 Com isso L = {1,00,10,000, ...} 
 
47) nao sei se ta certo: pelo pouco que sei, aprovo (guilheme)
 
Temos que T é o conjunto de todas as máquinas de turing, temos que esse conjunto é infinito, 
pois sempre conseguimos colocar instruções novas, mesmo que elas não tenham utilidade, 
conseguimos codificar todas as maquinas de turing em um inteiro, portanto, como T é um 
subconjutno de N, portanto |T| <= N entao T ~ N. Td é o conjunto de todas as máquinas de 
Turing que são decidíveis. Com isso Td é um subconjunto de T, entao, |Td| <= T entao Td ~ N
 
 
48)
Teta:
 
Não tenho a menor idéia do que seja LSC (deve ser complemento de LLC) e LEF, mas o resto 
é:
Regular C LLC C Rec C RE
sendo C o símbolo de contido.
 
 
49) Uma linguagem L pertence a Time(f) se a MT que decide essa linguagem recebe uma 
entrada x e que executa depois de utilizar um número de passos menor ou igual a c*f(n)
 
Time(n)
L = {<xMax <x1,x2,x3,..., xn>> : xMax é o maior elemento de < x1,x2,x3, …, xn }
 
Time(n²)
(Não sei se a representação é assim!!)
L = {<<x1,x2,x3,...,xn> < y1,y2,y3,...,yn >> : <x1,x2,x3, …,xn> é o conjunto ordenado de 
<y1,y2,y3, …, yn> } 
 
 
50) Uma linguagem L pertence a SPACE(f) se a MT que toma uma entrada x e que termina sua 
execução depois de utilizar o número de células menor ou igual a c*f(n).
 
 
SPACE(n)
 
L = {X espaço Y espaço XY}
 
51) Se temos t passos entao no maximo t células são tocadas, pois o espaço é finito. portanto 
se t = n entao Time(n) C Space(n), mais genericamente Time(f) C Space(f)
 
52) ---
53) São linguagens que podem ser aceitas por uma MT em tempo Polinomial
 
54) Uma linguagem L pertence a NP quando existe um polinômio P e uma MT M tal que :
x pertence a L sse existe y, |y| <= p(|x|) e M (x espaço y) = 1 com M executando em 
tempo polinomial.
Resumindo, existe uma MT M que com a entrada x ela consegue verificar a saida da 
Linguagem NP em tempo polinomial.
Seja H o conjunto de grafos com caminhos hamiltonianos, H pertece a NP, pois para 
cada grafo G, G pertece a H e existe um caminho hamiltoniano C e uma MT M que retorna 1 
com a entrada G espaço C.
 
 SAT = { $ : $ é uma formula do calculo proposicional a FNC satisfacivel} é NP, pois uma MT 
M , que toma tempo polinomial, e para cada $ pertencente a SAT, existe uma atribuição Y de 
valores às variáveis de $ tal que:
 $ pertence a SAT sse M($ espaço Y) = 1
 
 
55) M executa em tempo polinomial , digamos: n^m e R executa tb em tempo polinomial , 
digamos n^k.
Logo M(R(x)) executa em tempo:
 (n^k)^m = n^k*m que é polinomial.
 Time de R = TIME ( n^K ) entao TIME(n^k) C SPACE(n^k) (Pois t passos no máximo t 
celulas são tocadas) Portanto tem no max n^k celulas.
 A entrada de M é n^k.
58) Sabemos que SAT é NP-Completo pelo o teorema 6.0.1 então qualquer Linguagem NP 
pode ser redutivel a SAT. Afirmamos que SAT é redutivel a L, portanto, L é uma linguagem 
mais complexa que SAT. Como qualquer linguagem menor ou igual a NP pode ser redutivel a 
SAT então elas podem ser redutíveis a L.
59)
Não é . Para que ela seja considerada NP-Completa ela precisa que qualquer 
linguagem NP é polinomiavelmente redutivel a L ( isso ela é! ) e que L pertence a NP, como L 
nao pertece a NP ela não pode ser NP- Completa.
 
60) Não, para que uma linguagem B possa ser considerada NP-Completa ela precisa ser NP e 
que para qualquer T pertencente a NP seja redudiza a B.
Com isso temos que somente K é NP completa, pois conseguimos reduzer SAT e L 
nela. Temos que K é a linguagem mais complexa.
 
61) Não tenho certeza!!
 
R(x) é redutível a SAT em tempo n^3 e que produz saída |x|², portanto, sua complexidade é |x|², 
tem uma M(x) que executa em tempo n^5. Com isso podemos reduzir L SAT através de R e M :
 
M’(x) = M(R(x)) = M(|x|²) = (|x|²)^5 = |x|^10
Portanto a complexidade de M’ é |x|^10.