Tese Church Máquina de Turing

Problemas de Decisão

Máquina de Turing

• Uma Máquina de Turing (MT simples) é uma 6-upla   M = (Q, S, G, d, q0, F)

• Q: Conjunto de estados
• S: Alfabeto de entrada
• G: Alfabeto da fita  ( Σ ⊂ Γ, b ε Γ, b ∉ Σ,   : símbolo vazio da fita )
• q0 ε Q:  Estado inicial
• F ⊆ Q:   Conjunto de estados finais
• d: Q × Γ  Q × Γ × { ← , ↓,  →}

Linguagem Enumerável

• Uma linguagem L é recursivamente enumerável  se L = L(M) para alguma Máquina de Turing M (i.e., se L é aceita por alguma M).
• Exemplo: MT que reconhece  L = { 0n10n

| n ≥ 0} = { 1, 010, 00100, 0001000,

0001000, … }

Linguagem Enumerável

Recursivamente

• L é recursiva  ⇔  Existe Máquina de Turing M que sempre pára (i.e., se LA ⊆ L é aceita por M, então M rejeita  å*-LA ).
• L é recursivamente enumerável  ⇔  Existe

M tal que LA = L (i.e., se x Ï L, a máquina M com entrada x pode não parar, ou seja, M pode entrar em loop).

Tese de Church

• “Qualquer procedimento efetivo pode ser realizado por uma máquina de Turing”.
• A noção de procedimento efetivo é informal, e assim, a tese de Church-Turing afirma a equivalência entre um conceito informal e um formal, não sendo portanto, passível de demonstração.

Tese de Church

• No entanto, existe considerável evidência que suporta essa proposição, já que inúmeros sistemas formais, como por exemplo,
• A Máquina de Turing;  
• As funcões recursivas parciais;
• As funções m-recursivas de Gödel, Herbrand e Kleene;
• O cálculo l de Church;
• Os sistemas de produção de Post;
• As linguagens de programação Fortran, Pascal, C, Lisp, Java, etc…
• entre outros,
• mostram-se todos equivalentes uns aos outros, e todos foram definidos para caracterizar os procedimentos efetivos.

Máquina de Turing Universal

• É uma MT que, quando apresentada a uma codificação de uma Máquina de Turing M e a cadeia α, simula de M com a entrada α.
• MT        ⇔   Um programa específico
• MTU  ⇔   Computador + software básico

Máquina de Turing Universal

• 1) O conjunto das MTs é enumerável:      #{MTs} =  #ℚ  =  #ℤ  →  < #ℝ
• 2) MTs podem ser enumeradas, usandose, por exemplo, a codificação delas que aparece na definição/construção da MTU.

INDECIDIBILIDADE

• Um problema de decisão é uma sentença (usualmente uma pergunta) que pode ser verdadeira ou falsa (V ou F), ou ter como resposta sim ou não (S ou N).
• OBS: Problemas de decisão são úteis pela simples razão de que eles só possuem 2 respostas possíveis..

INDECIDIBILIDADE

• Um problema de decisão é decidível, quando ele pode ser respondido

computacionalmente. Ou seja, problemas (de decisão) decidíveis são problemas computáveis ⇒ Existe um algoritmo para resolvê-lo.

• Exemplo:
• Problema computável: Qual foi a quantidade de chuva ontem em São Paulo?
• Problema decidível:          A quantidade de chuva ontem em São Paulo foi maior que

10mm?

INDECIDIBILIDADE

• Um problema de decisão é indecidível, quando ele não tem resposta computacional. Ou seja, problemas (de decisão) indecidíveis são problemas não-computáveis ⇒ Não existe um algoritmo capaz de resolvê-lo.
• Problema não-computável: Quantas vezes a seqüência numérica 123 ocorre na expansão desse número?
• Problema indecidível: O número de ocorrências da seqüência 123 na expansão decimal (infinita) de um certo número irracional é par?
• OBS: O problema em si de como produzir a expansão infinita do número pode ser computável. Por exemplo, existem algoritmos para produzir a expansão do número π.

INDECIDIBILIDADE

• Considera-se que um problema de decisão está em aberto do ponto de vista de sua decidibilidade, quando ainda não é possível estabelecer se ele decidível ou indecidível.
• Exemplo: Não se sabe ainda se a questão  Choverá daqui a 100 dias?  é decidível ou indecidível 

O Problema da Parada  (Halting

Problem)

• O problema indecidível mais famoso:    A máquina de Turing M pára com entrada a ?
• Em sua formulação mais atual:   O programa (ou algoritmo) R  pára com entrada X?

O Problema da Parada  (Halting Problem)

[pic 1]

...