Universidade Federal de Uberlândia
Mestrado em Ciência da Computação
Solução da 1a Prova de Teoria da Computação - 05/05/2010
Questão 1 (Valor = 7 pontos)
Um número real é dito algébrico se é raiz de um polinômio de√ coeficientes inteiros
an xn + an−1 xn−1 + ... + a1 x + a0 = 0. Por exemplo, o número 2 é algébrico pois é
raiz do polinômio x2 − 2 = 0. Um número real é dito transcendente se não for algébrico.
Por exemplo, é sabido que o número e não é algébrico. Mostrar que o conjunto dos
números transcendentes não é enumerável.
Solução:
• Mostremos primeiramente que o conjunto P de todos os polinômios a coeficientes
inteiros é um conjunto enumerável.
Seja Pn o conjunto dos polinômios de grau n, de coeficientes em Z. Cada elemento
de Pn está associado de forma única a uma sequência (a0 , a1 , ..., an ) de números
inteiros, de tamanho n + 1 (a sequência de seus coeficientes). Isto é, existe uma
função bijetora f : Pn → Z × Z × ... × Z (n + 1 vezes). Como Z × ... × Z é enumerável
S
(demonstrado em sala de aula), então Pn é enumerável. Temos que P = ∞
n=0 Pn .
Como a união enumerável de conjuntos enumeráveis é um conjunto enumerável
(demonstrado em sala de aula), temos que P é um conjunto enumerável, isto é, P
= {p1 , p2 , p3 , ....}.
• Mostremos que o conjunto A dos números reais algébricos é enumerável. Para cada
polinômio pi ∈P,S
seja Ri = {ri1 , ri2 , ..., riki } o conjunto (finito) de suas raı́zes reais.
Temos que A = ∞
i=1 Ri . Portanto, A é enumerável, já que é a união enumerável
de conjuntos finitos (mostrado em aula).
• Temos que R = A∪ A. Se o conjunto dos números reais transcendentes A fosse
enumerável, R seria enumerável, pois seria a união de dois conjuntos enumeráveis.
O que é absurdo, pois sabemos que R não é enumerável (mostrado na primeira lista
de exercı́cios).
Questão 2 (Valor = 7 pontos) Diga se é verdadeiro ou falso e prove sua resposta.
Seja L uma linguagem indecidı́vel. Então existe uma redução de AT M para L.
A afirmação é falsa. Contraexemplo: considere a linguagem ET M . Sabemos que ET M
é indecidı́vel. Entretanto, não existe AT M 6≤m ET M .
• ET M é Turing-reconhecı́vel. Seja w1 , w2 , ... o conjunto de todos os strings de Σ∗ .
Considere a seguinte máquina de Turing:
S = No input < M > faça:
1. i = 1
2. Repita os seguintes passos até atingir o estado qa
Execute passo de M em wi ,
Execute passos 1 e 2 de M em wi−1 ,
...
Execute passos 1, 2, ..., i de M em w1 ,
i=i+1
3. Aceita.
A máquina S reconhece a linguagem ET M .
• Suponhamos por absurdo que AT M ≤m ET M . Então, AT M ≤m ET M . Como
mostramos que ET M é Turing-reconhecı́vel (item anterior), então AT M seria Turingreconhecı́vel, o que é absurdo: se fosse Turing-reconhecı́vel, o problema AT M seria
decidı́vel, já que é Turing reconhecı́vel. E sabemos que AT M é indecidı́vel (mostrado
em sala de aula).
Questão 3 (Valor = 7 pontos)
Seja L = { < M, x > tal que em algum ponto do cálculo de M sobre o input x, M volta
para o estado inicial}. Mostre que L é indecidı́vel.
Sugestão: Mostre que AT M se reduz a L.
Solução: Seja M = (Q, Σ, Γ, δ, q0 , qa , qr ) uma máquina de Turing. Vamos modificar o
código de M , obtendo o código de M 0 = (Q0 , Σ0 , Γ0 , δ 0 , q00 , qa , qr )
Considere a seguinte função que associa uma instância de AT M a uma instância de L:
Para cada instância < M, w > de AT M seja < M 0 , x > a seguinte instância de L: x = w
e M 0 é a máquina de Turing que passamos a descrever abaixo:
1. estados de M 0 = Q ∪ {q00 }. Isto é, introduzo um novo estado em M 0 .
2. simbolos de input de M 0 = simbolos de input de M (Σ0 = Σ).
3. simbolos da fita de M 0 = simbolos da fita de M (Γ = Γ0 ).
4. estado inicial de M 0 = q00 .
5. estado de aceitação de M 0 = estado de aceitação de M = qa
6. estado de rejeição de M 0 = estado de rejeição de M = qr
7. Função de transição de M 0 = δ 0 . A idéia de M 0 é que sempre que M entrar no
estado qa quando executada no input w, M 0 vai entrar no seu estado inicial q00 . Os
outros passos de M 0 seguem a mesma estrutura da máquina M , isto é, seguem a sua
função de transição. Assim, só temos de fazer com que q00 simule o estado inicial de
M (no inicio do cálculo, tudo o que q0 faz, q00 deve fazer também). Se a partir de
algum estado q, M dirige-se para qa , então obrigo M 0 a passar de q para seu estado
inicial q00 . Veja que a introdução deste novo estado inicial foi feita para garantir que
M 0 volta ao inicio ao ser processada num input x SÓ SE M aceita x.
A função de transição de M 0 é dada por:
δ 0 (q00 , a) = δ(q0 , a) para todo a ∈ Σ
δ 0 (q, a) = δ(q, a)
para todo a ∈ Γ, caso δ(q, a) = (q1 , b, y), onde b ∈ Γ, y ∈ {R, L} e q1 6= qa
0
δ (q, a) = (q00 , b, y)
para todo a ∈ Γ, caso δ(q, a) = (qa , b, y), onde b ∈ Γ, y ∈ {R, L}
0
É claro que M aceita x se e somente se M 0 volta para seu estado inicial qO
em algum
ponto de seu cálculo ao ser executada sobre x.
Consideremos agora uma redução de AT M para L da seguinte maneira: para cada
instância < M, w > deAT M associamos uma instância < M 00 > de L, onde M 00 é a
seguinte máquina de Turing:
M 00 = No input x faça
1. Se x 6= w, rejeita
2. Se x = w, executa M 0 em w
Temos que:
se M aceita w então M 00 volta ao seu estado inicial q00 em algum passo, ao ser executada
em w
se M não aceita w então M 00 nunca volta a seu estado inicial q00 ao ser executada em
qualquer input x
Portanto, exibimos uma redução de AT M para L, mostrando assim que L é indecidı́vel.
Questão 4 (Valor = 7 pontos) Diga se é verdadeiro ou falso e prove sua resposta.
Sejam A e B duas linguagens indecidı́veis distintas tais que A se reduz a B. Então B
não se reduz a A.
Solução:
A afirmação é falsa. Para isto, vamos considerar um contraexemplo: dois problemas
A e B indecidı́veis, A 6= B tais que A ≤m B e B ≤m A. Seja A o problema HALT e B o
problema AT M .
HALT ≤m AT M : dada uma instância < M, w > de HALT, consideremos a instância
< M 0 , w > de AT M , onde M 0 é definida da seguinte maneira:
M 0 = No input x faça:
1. Se x 6= w, rejeita
2. Se x = w, executa M em w
3. Se pára em qa ou qr : aceita
É claro que M pára em w se e somente se M 0 aceita w.
AT M ≤m HALT : demonstrado em sala de aula, não é necessário repetir.
Só por uma questão de completude, vamos exibir a demonstração feita em sala de
aula:
Dada uma instância < M, w > de AT M , consideremos a instância < M 0 , w > de
HALT, onde M 0 é definida da seguinte maneira:
M 0 = No input x faça:
1. Se x 6= w, rejeita
2. Se x = w, executa M em w
3. Se aceita: aceita.
4. Se rejeita: entra em loop.
É claro que M aceita w se e somente se M 0 pára em w.
Questão 5 (Valor = 7 pontos)
Para cada um dos problemas, diga se é decidı́vel, Turing-reconhecı́vel ou co-Turingreconhecı́vel. Não é necessário justificar sua resposta.
1. ALLDF A = {< A >| A é autômato finito que pára para todos os seus inputs}.
Decidı́vel: SIM
Turing-reconhecı́vel: SIM
co-Turing reconhecı́vel: SIM.
2. ALLCF G = {< G >| G é gramática livre do contexto que gera todos os strings com
0’s e 1’s}.
Decidı́vel: NÃO
Turing-reconhecı́vel: NÃO
co-Turing reconhecı́vel: SIM.
3. L1 = {< G >| G é gramática livre do contexto que não gera nenhum string de
terminais}.
Decidı́vel: SIM
Turing-reconhecı́vel: SIM
co-Turing reconhecı́vel: SIM.
4. L2 = {< M >| M é máquina de Turing que não pára em nenhum input}
Decidı́vel: NÃO
Turing-reconhecı́vel: NÃO
co-Turing reconhecı́vel: SIM.
5. L3 = {< M >| M é máquina de Turing que não pára em algum input}
Decidı́vel: NÃO
Turing-reconhecı́vel: NÃO
co-Turing reconhecı́vel: NÃO.