Teorema da Recursão
Teoria da Computação
Pós-graduação em Ciência da Computação
Profa. Sandra de Amo
Auto-referência

Máquina de Turing SELF
SELF = No input w
1. Apaga w da fita;
2. Insere na fita o string <SELF>
<SELF> = código da máquina SELF
Como construir a máquina SELF
Passo 1 : Máquina Pw = máquina que imprime w na fita
Pw = No input x
1.
Ignora x
2.
Imprime w na fita
Exemplo
: w = 00
Código da máquina P00
δ(q0,x) = (q1,0,R), para qualquer simbolo x da fita
δ(q1,x) = (q2,0,R), para qualquer simbolo x da fita
δ(q2,x) = (q2,B,R), para x ≠ B
δ(q2,B) = (qa,B,R).
Como construir a máquina SELF
Passo 2 : Máquina Q
= máquina que no input w
imprime o código da máquina
que imprime w.
w
<Pw>
Q
Input = w
Output = <Pw> (código da máquina Pw)
Máquina de 2 fitas:
Q = No input w
1. Constrói o string <Pw>
na fita 2
2. Apaga w da fita 1
3. Copia <Pw> na fita 1
Como construir a máquina SELF
Passo 3 : Máquina B
B = No input <M>
1.Computa Q(<M>) = < P<M>>
2.Imprime na fita < P<M> . M >
3.Pára
< P<M> . M > é o código “concatenado” de < P<M>> e <M>
δ(q0,..) = (q1,...)
........
δ(q,..) = (qa,..)
<P
>
(q’a,...)< M >
δ(q’_0, ...) = ...
........
δ(q’,..) = (q’a,....)
<M>
δ(q0,...)= (q1,...)
... .....
δ(q,...) = (q’_0,...)
........
δ(q’,...) =
Como construir a máquina SELF

Passo 4 : Máquina A
A = P<B>

Passo 5 : Máquina SELF
SELF = A . B
Máquina SELF
Self = No input x faça
1. Ignora x
2. Executa A: Imprime código da máquina B na fita
3. Executa B sobre o string da fita (no caso <B>) : Imprime código da
máquina que imprime B na fita seguido do código de B
4. Resultado na fita = <A.B>
Máquina SELF = A.B
Input w
a1 a2 a3 a4 a5
A
<B>
qB0 0 q1 0
R
# q1 0
...
B
< A .B >
qA0 0 q4 1
L
#
< P <B> > = <A>
qB0 0 q1 0
R
<B>
#
q1 0
Teorema da Recursão
Seja T máquina de Turing a duas fitas que recebe como
input dois strings : w na primeira fita e u na segunda fita
T : (w, u)  z
Então existe máquina de Turing R com uma fita tal que
R(u) = T(<R>, u)
Prova do Teorema da Recursão
Considere a máquina Pw a duas fitas
1.
2.
Pw = No input x
Transporta x para a segunda fita
Imprime w na primeira fita
Seja A = P <BT>
R = A.B.T
Input w
a1 a2 a3 a4 a5
1a fita
A
< B.T >
qBT0 0 q1 0
# q1 0
R
...
1a fita
B
1a fita
< A.B.T >
qA0 0 q4 1
L
#
qBT0 0 q1 0
< P <BT> > = <A>
a1 a2 a3 a4 a5
#
q1 0
< B.T >
2a fita
T
LOGO :
R
ABT (a1a2....a5) = T(<ABT>,a1a2...a5)
Característica da Máquina R

Constrói uma réplica de seu próprio código.

Continua o restante de seu cálculo que pode
incluir ações envolvendo seu próprio código.
Programas de vírus contém construção
análoga à descrita na prova do teorema da
recursão.
Outra formulação do Teorema da Recursão

Seja T máquina de Turing a duas fitas.
Para cada w fixo, seja a máquina de Turing a uma fita
Tw : u  z

Existem infinitas máquinas deste tipo.

O teorema da Recursão afirma que
existe uma máquina de Turing R a uma fita tal que
T<R> = R
Aplicações do Teorema da Recursão
Virus:
Dada uma máquina T, é possivel construir uma máquina T’
equivalente a T que replica seu próprio código na fita.
T’ = A.B.T
T’: No input x faça

Executa A

Executa B
% Após a execução do passo 2, tem-se o código de T’
na fita 1 e x na fita 2
3)
Executa T sobre x (que está na 2a fita)
4)
Se T aceita x, aceita. Se T rejeita x, rejeita.
Aplicações do Teorema da Recursão
Outra prova que o Problema da Parada é indecidível.
Suponha que Halt fosse decidível. Seja H uma MT que decide Halt. Considere a
máquina H que retorna o oposto de H:
H(<M,w>) = qa se H(<M,w>) = qr
H(<M,w>) entra em loop se H(<M,w>) = qa
Considere a máquina H’ = ABH
H’ : No input w faça:
1) Executa A
2) Executa B
% Após a execução do passo 2, tem-se o código <H’ > de H’ na fita 1 e w na
fita 2
3) Executa H em <H’,w>
H’(w) = qa (pára) se H(H’,w) = qr (isto é, se H’ não pára ao ser executada em w)
H’(w) entra em loop (não pára) se H(H’,w) = qa (isto é, se H’ pára ao ser
executada em w)
ABSURDO !
Aplicações do Teorema da Recursão
M é uma máquina minimal se não é possivel encontrar
máquina M’ equivalente com código mais curto.
Problema MIN = {<M> | M é uma MT minimal}
não é Turing Reconhecível.

É fácil ver que o MIN é infinito (existem infinitas
máquinas que são minimais).
Prova
Suponha que MIN fosse Turing Reconhecível.
Seja E uma máquina enumeradora de MIN.
Seja E a seguinte máquina:
E : No input x faça:
1) Aciona o enumerador E
2) A primeira vez que aparece um código de máquina de
Turing D no dispositivo de impressão de E que seja
maior do x, simule D em x.
Repare que como MIN é infinito, sempre vai aparecer um
código D maior do que x no dispositivo de impressão de
E.
Prova (continuação)
Considere a máquina M’ = ABE
M’ = No input w faça
1) Executa A
2) Executa B
% Após a execução do passo 2, tem-se o código <M’ > de
M’ na fita 1 e w na fita 2
3) Executa E em <M’>
M’(w) = D(w). Como o código de D é maior do que o de M’
então D não pode estar em MIN. Mas o código de D
aparece na enumeração dos códigos de MIN !!
ABSURDO
Teorema do Ponto Fixo
Seja f: ∑*  ∑* uma função computável qualquer.
f pode ser aplicada sobre códigos de máquina de Turing, produzindo
como resposta um string que pode ou não ser código de máquina
de Turing.
Teorema do Ponto Fixo: Existe uma máquina de Turing F tal que
f(<F>) é um código de MT equivalente a F
Isto é: o comportamento da máquina F fica inalterado após a
transformação de seu código via f.
Prova do Teorema do Ponto Fixo
Considere a seguinte máquina G
G(<M,w>) = f(<M>)(w)
Considere a máquina F = ABG. Vamos mostrar que F é equivalente à
máquina f(<F>)
F = No input w faça:
1.
Execute A
2.
Execute B
% Após a execução do passo 2, tem-se o código <F > de F na fita
1 e w na fita 2
3.
Execute G em (<F,w>)
Logo: F(w) = G(<F,w>) = f(<F>)(w). Portanto F é equivalente a f(<F>).