Sumário da matéria teórica da aula de 070418

Sumário da matéria teórica da aula de 070418

	     Sumário da matéria teórica da aula de 070418
             --------------------------------------------

T. domínio: enunciar:
     L é r.e.  sse existe f rec. (parcial) com
                   L = {i : f(i) definido}
---------------------------------------------------------
T. contra-domínio: enunciar:
     L infinita é r.e.  sse existe f:A -> B  rec. total com
                        L = {f(i) : i em A}

     Prova:

     => Seja L infinita e r.e.
        Existe M que enumera os elementos de L
        Existe M' que recebe i e funciona como M 
           conta em c os x para os quais x foi listado
           quando c=i escreve x e pára.
        Nota: o contra-domínio de M' é L

     <= Seja L infinita e existe f: A -> B rec. total com
             L = {f(i) : i em A}
        Existe M tal que
          dado x
          1) enumera o contra-domínio de f (com dovetailing)
          2) quando e se for listado x
               a) apaga a fita
               b) escreve 1 na fita

          Então  M(x) = | 1 se x pertence a L
                        | não definido se não x pertence a L


          Então L pertence à classe r.e.

---------------------------------------------------------

T. Rice (enunciado)
   Seja P uma qualquer propriedade não trivial (ver apontamentos) das
   funções. Então o seguinte problema não é decidível
     Dados: i (inteiro natural)
     Pergunta: a função {i} tem a propriedade P?

Demonstração: Seja
      - B a classe das funções com a propriedade P e B' a classe
        complementar 
      - ^(x) a função não definida em nenhum ponto.

   Seja h(x) uma função que não está na mesma classe (B ou B') de
   ^(x). Sem perda de generalidade supomos h em B, ^ em B'.
   Seja a função computável parcial    (porque é f computável?)

          f(x,y) = | h(y)   se {x}(x) está definido
                   | ^      se {x}(x) não está definido

   Existe uma função g tal que
      f(x,y) = {g(x)}(y)
   g é recursiva (parcial). Para cada x, a MT {g(x)}, recebendo y,
   coloca "x,y" na fita (y já lá estava) e simula f(x,y)
       g: inteiro -> MT

   Temos: 
      Para todo o y: {g(x)}(y) = h(y)  se {x}(x) está definido
      Para todo o y: {g(x)}(y) = ^(y)  se {x}(x) não está definido

   Então {x}(x) está definido   sse  {g(x)} está em B
   Se tivermos um processo de decisão (MT...) para "f está em B?",
   então teríamos um processo de decisão para PAP; mas PAP é
   indecidível. 

---------------------------------------------------------

Problema TOTAL:
   Dado: i (inteiro natural)
   Pergunta: a função {i}(x) é total, isto é, para todoo x {i}(x)
   pára? 

   Classe a que pertence TOTAL

---------------------------------------------------------

Problema A é completo numa classe C se (definição):
   A pertence a C
   Para todo o problema B em C temos B <= A

equivalente:

Linguagem L é completa numa classe C se (definição):
   L pertence a C
   Para todo a linguagem L' em C temos L' <= L

 Consequências práticas: um eventual algoritmo para A seria um
   algoritmo para todos os problemas de B.

   Teorema: L_PGP é completo na classe r.e.

   Prova. 1) L_PGP está em r.e.
          2) Seja A em r.e. Queremos mostrar que A <= L_PGP
             Se A em r.e., existe MT M, seja i o índice de M, tal que
                {i}(x) = | 1 se x pertence a L_A  
                         | ^ se x não pertence a L_A  
             Então x pertence a L_A  sse {i}(x) pára,
               isto é, se  <i,x>  pertence a L_PGP
          A  <=  PGP
          x  --> <i,x>     (i é fixo para cada redução)
          (completar...)
  

Sumário da matéria teórica da aula de 070418