Indecidibilidade
Prof.: Edson Holanda
[email protected]
Teoria da computação
Programa Hello, World
main( )
{
printf( "Hello, World \n");
getch( );
}
?????
“O programa P com a entrada E,
imprime a string ‘Hello, world’?”
Programa Hello 2
main()
{ int n, total, x, y, z;
scanf("%d", &n);
total = 3;
while(1) {for (x = 1; x <= total - 2; x++)
for ( y = 1; y <= total -1; y++)
{ z = total - x - y;
if (exp(x,n) + exp(y,n) == exp (z,n))
{ printf("Hello, World");} }
total++; }
}
Programa Hello 2
int exp(int i, int n)
{ int res, j;
res = 1;
for ( j = 1 ; j <= n ; j++ )
{ res = res * i; }
return(res);
}
Último teorema de Fermat
 “Não
existem soluções
inteiras para a equação
xn + y n = z n ,
se n > 2”.
Testador hipotético
P
E
Testador de Hello,
world
Sim
H
Não
Testador hipotético
P
Sim
H1
E
Hello,
World
Testador hipotético
Sim
P
H2
Hello,
World
O que acontece quando…. ?
Sim
H2
H2
Hello,
World
Vamos chamar esse problema de
‘Hello, world’
Princípio da Redução
Problema Hello, world
Redução de
Hello, world
Problema Chamar F1
Reduzindo um problema a outro
Sim
Instância
de P1
Construir
Instância
de P2
Decidir
Não
Um exemplo de redução

Vamos mostrar que o
problema: “ O programa P,
dada a entrada E,chamará a
função f1?” é indecidível.

Obs.: Vamos supor que o
programa possui uma função
chamada f1
Prova:


Usaremos uma demonstração
por absurdo;
Como só conhecemos um
problema indecidível, Hello,
world fará o papel de P1 no
diagrama mostrado
anteriormente.
Prova: (cont.)

Precisamos projetar um
algoritmo que converta o
problema Hello, world no
problema de chamar F1.
Prova: (cont.)

Ou seja, dado o programa P e
sua entrada E, devemos
contruir uma programa R e uma
entrada Z tais que R, com a
entrada Z, chame F1 SSE P
com a entrada E imprimir Hello,
world.
Prova: (cont.) A construção
1.
Se P tem uma função F1,
renomeie essa função e todas
as chamadas a ela. ( vamos
chamar esse novo programa de
P1)
Prova: (cont.) A construção
2.
Adicione a P1 uma função F1.
Essa função não faz nada e
não é chamada. ( vamos
chamar esse novo programa de
P2)
Prova: (cont.) A construção
3.
Modifique P2 para memorizar
os 12 primeiros caracteres que
ele imprime (armazenando em
um vetor global V. ( vamos
chamar esse novo programa de
P3)
Prova: (cont.) A construção
4.
Modifique P3 de forma que, sempre
que executar qualquer instrução de
saída, ele verifique em seguida no
vetor V se escreveu 12 caracteres ou
mais e, se for o caso, se Hello, world
são esses 12 primeiros caracteres.
Nesse caso, chame a nova função
F1. O programa resultade é R e a
entrada Z é igual a E.
Prova: (cont.) conclusão
Dessa forma transformamos um problema
Hello, world em um caso do problema
chamar F1.
Logo, se o problema chamar F1 fosse
decidível, então o problema Hello, world
também seria. O que é um absurdo poís
sabemos que Hello, world é indecidível.
Portanto, o problema chamar F1 também
é indecidível.
Importante:
Sobre a prova através de redução:
Observe a importância do raciocínio
recursivo na implementação do programa
H2.
Importante:
A tese de Church estabelece uma
correspondência entre as noções de
Algoritmo e Máquina de Turing.
Ou seja, podemos pensar num algoritmo
como uma máquina de turing que sempre
pára, para qualquer entrada, aceitando ou
rejeitando.
Importante:
Lembre que L é uma linguagem
recursivamente enumerável (RE) SSE
L = L1(M) para alguma Máquina de Turing
M.
Ling. Recursivas  Decidíveis  MT
sempre pára.
Uma modificação na MT
Seja M = (Q ,,  , q0, ß, F) uma
Máquina de Turing.
Assumiremos que a fita é infinita, tanto
do lado direito quanto do lado
esquerdo.
A palavra de entrada w será formado
por todos os símbolos diferentes do
branco, desde o mais a esquerda até o
mais o direita.
Outro problema indecidível
Vamos provar que é indecidível a
linguagem que consiste em pares
(M,w) tais que:
1. M é uma máquina de turing
(codificada em binário), com alfabeto
de entrada { 0, 1 }
2. w é um string de 0´s e 1´s.
3. M aceita a entrada w.
Enumeração dos strings binários
Ordene todos os strings de acordo com
o comprimento e os de mesmo
comprimento por ordem lexicográfica.
Ex: , 0, 1, 00, 01, ...
Dessa maneira podemos falar do
primeiro string (w1), do segundo string
(w2), etc.
Codificação para máquinas de Turing
Seja M = (Q ,,  , q0, ß, F),
precisamos atribuir números naturais
aos estados, aos símbolos e aos sentidos
(E e D).
1. Sejam q1,q2,...,qr para algum r.
Vamos admitir que q1 sempre será o
estado inicial e que q2 será o único
estado de aceitação (final).
Codificação para máquinas de Turing
2. Sejam X1, X2, ..., Xs para algum s.
Vamos admitir que X1 sempre será 0,
X2 será 1 e que X3 será ß. Os demais
símbolos são atribuídos de maneira
aleatória aos próximos naturais.
3. Atribuiremos D1 ao sentido E e D2
ao sentido D.
Codificação para máquinas de Turing
Agora podemos codificar o função de
transição (qi, Xj) = (qk, Xl, Dm),
para alguns naturais i, j, k, l e m.
Codificaremos essa regra pelo string
i
j
k
l
m
0 10 10 10 10
Obs.: Como todos os valores i, j, k, l e m
são, pelo menos, iguais a 1, não temos
dois, ou mais, 1´s consecutivos.
Codificação para máquinas de Turing
Um código para a MT M inteira consiste
em todos os códigos para as transições,
em alguma ordem, separados por pares de
1´s:
C111C211...Cn-111Cn
Codificação para máquinas de Turing
Exercício: Codifica a MT M abaixo,
M = ({q1,q2,q3},{0,1}, , q1, ß, {q2})
na qual  consiste nas regras:
(q1, 1) = (q3, 0, E),
(q3, 0) = (q1, 1, E),
(q3, 1) = (q2, 0, D),
Codificação para máquinas de Turing

Lembrem que precisamos codificar pares
que consistem em uma MT e uma string,
(M, w).

Para esse par usamos a codificação
anterior para M, seguida de 111 e por w.
Obs.: Em um código para uma MT não
contém três 1´s consecutivos.
Enumeração de MT´s

Agora podemos ordenar todas as MT´s de
acordo com o comprimento e as de
mesmo comprimento por ordem
lexicográfica.

Assim, podemos falar da Mi(i-ésima
máquina de Turing).

Obs.: Se o string não for uma representação
bem formada de alguma MT, então ela
representa um MT sem movimentos. L(M)={ }
A linguagem da diagonalização

A linguagem Ld, a linguagem da
diagonalização, é o conjunto de strings wi
tais que wi não está em L(Mi).

Vetor caracteristico: Formado por todas
as strings que são aceitas pela MT Mi.

O complementa da diagonal não é o vetor
característico de nenhuma MT.
Teorema: Ld não é RE


Ou seja, não existe nenhuma MT que
aceite Ld.
Prova: Vamos supor que Ld é L(M) para
alguma TM M. Como Ld é uma
linguagem sobre o alfabeto {0,1}, M está
na lista de MT que construímos, ou seja,
existe um código para M, digamos que
seja i ( M = Mi).
Teorema: Ld não é RE

Wi está em Ld ?

Se wi está em Ld, então Mi aceita wi.
Entretanto, por definição de Ld, wi não
está em Ld, porque contém somente os
valores wj tais que Mj não aceita Mj.
Teorema: Ld não é RE

Wi está em Ld ?

Se wi não está em Ld, então Mi não
aceita wi. Portanto, por definição de Ld,
wi está em Ld.

O que é uma contradição (absurdo) !!