Computabilidade e Decibilidade

Computabilidade e Decibilidade

1. Computabilidade

   • Investiga a limitação dos computadores
     • O que é computável(solucionável) e o que não é
       • Problemas
         • Problemas Solucionáveis
           • existe um algoritmo que soluciona o problema
             • entrada com uma resposta afirmativa (ACEITA) ou negativa (REJEITA).
           • Todo problema Solucionável é Parcialmente Solucionável.
             • Problemas Parcialmente Solucináveis
               • existe um algoritmo capaz de responder SIM
                 • São Computáveis
         • Problemas Insolucionáveis
           • não existe um algoritmo (Máquina Universal) que solucione o problema
             • Problemas não computáveis
               • Problema da Parada
                 • Não existe um algoritmo genérico capaz de verificar se o programa vai parar ou não para a entrada.
                   • Loop Infinito
               • Equivalência de compiladores:
                 • Não existe algoritmo genérico capaz de comparar quaisquer dois compiladores de LLC e verificar se são equivalentes
         • A classe dos problemas Parcialmente Solucionáveis contém propriamente a classe dos problemas Solucionáveis e parte da classe dos problemas Não-solucionáveis.
     • O que não considerar?
       • o limitações reais de uma implementação
         • tamanho de espaço de endereços
         • tamanho da memória principal
         • questões de tempo
     • Máquina de Post
       • é um autômato determinístico, baseado na estrutura de dados do tipo fila com um símbolo auxiliar.
     • Máquina de Pilha
       • são modelos de computação equivalentes às gramáticas livres de contexto.
   • Princípio da Redução
     • solucionabilidade de um problema a partir de outro.
       • Reduzir o problema de B, a partir de resoluções feitas em A
       • Se A não é solucionável, B também não é, já que A é parte de B
       • Se B é parcialmente solucionável, então A é também parcialmente solucionável

2. Complexidade

   • trata da eficiência da computação em computadores existentes
     • Complexidade temporal
       • tempo de processamento exigido
     • Complexidade espacial
       • espaço de armazenamento exigido

3. Decibilidade

   • Máquinas de Turing
     • Linguagens Recursivas
       • Sempre respondem se a cadeia pertence ou não pertence a linguagem
       • Linguagens Recursivas Enumeráveis
         • Não é possível determinar se aceita ou não a entrada
       • Um problema decidível é estabelecer se a linguagem é recursiva
         • Não considera a quantidade de tempo gasto e sim se ele é finito

4. Problemas de Decisão

   • Solução
     • um algoritmo que determina a resposta correta para cada umas das perguntas
       • completo
         • produz uma resposta para todas as questões do problema;
       • mecanicista
         • consiste em um conjunto de instruções bem definidas;
       • determinista
         • para entradas idênticas retorna a mesma resposta;
     • Problema Decidível
       • Investigação da Solucionabilidade
         • problema de reconhecimento de linguagens
           • Os argumentos do problema SIM/NÃO são codificados como palavras de um alfabeto, gerando uma linguagem.
             • investigação se a linguagem gerada é recursiva (problema solucionável) ou enumerável recursivamente (problema parcialmente solucionável).

Imágenes y archivos del mapa