TEORIA DA COMPUTAÇÃO

TEORIA DA COMPUTAÇÃO

1. Computabilidade

   • Estudo
     • O que é: Habilidade de resolver problemas de forma efetiva.
       • Investiga os limites da computabilidade e do que pode ser implementado.
         • Objetiva evitar a pesquisa de soluções inexistentes de problemas
   • Problemas
     • Solucionabilidade: Objetiva evitar a pesquisa de soluções inexistentes.
       • Problemas Solucionáveis (Computáveis)
         • Existe um algoritmo, soluciona o problema, para quando a resposta é afirmativa (ACEITA)
       • Problemas Não Solucionáveis (Não computáveis
         • Não existe um algoritmo (Máquina Universal)
           • Pare quando a resposta é afirmativa (ACEITA)
           • Alguns problemas não-solucionáveis, são parcialmente solucionáveis
     • Computabilidade: Estudo para a resolução do problema
     • Problemas de Decisão
       • Verificar se a função associada, é ou não computável em uma Máquina Universal
         • Se a solução não puder ser expressa por uma Máquina Universal, o problema é completamente é insolúvel
       • Booleano: SIM/NÃO
     • Relação dos Problemas
       • Solucionáveis ∪ Não-Solucionáveis = Todos os Problemas
         • Problemas Parcialmente Solucionáveis contém: propriamente a dos Problemas Solucionáveis e parcialmente a dos Problemas Não-Solucionáveis
           • Todo problema solucionável é parcialmente solucionável
           • Existem problemas não-solucionáveis com solução parcial e também problemas completamente insolúveis que não possuem solução parcial nem total.
       • Computáveis ∪ Não-Computáveis = Todos os Problemas