Lista de exercícios de teoria da computação

1) Pesquisar: Problema da Parada.
R: Dada uma máquina universal “M” qualquer e uma palavra “W” qualquer sobre o alfabeto de entrada, existe um algoritmo que verifique que “M” para, aceitando ou rejeitando, ao processar a entrada “W”.

2) Pesquisar: Principio da Redução de Problema.
R: Investigar a solucionabilidade de um problema a partir de outro, cuja classe de solucionabilidade é conhecida.

3) Qual é o décimo problema de Hilbert?
R: Conceber um algoritmo que testasse se um polinômio tinha uma raiz inteira. OU Encontrar um algoritmo que determine se uma equação diofantina tem solução.

4) Qual a área de teoria da computação que se baseia em problemas com respostas binárias?
R: Solucionabilidade.

5) Qual o objetivo da área da questão anterior?
R: O objetivo do estudo da solucionabilidade de problemas é investigar a existência ou não de algoritmos que solucionem determinada classe de problemas, ou seja, investigar os limites da computabilidade e conseqüentemente os limites do que pode ser efetivamente implementado em um computador.

6) Quais são as classes de solucionabilidade? Defina.
R: Problema Solucionável: um problema é dito solucionável se existe um algoritmo que soluciona o problema, tal que sempre pára com uma resposta afirmativa ou negativa.
Problema Não-Solucionável: Um problema é dito Não-solucionável se não existe um algoritmo que solucione o problema tal que sempre pare para qualquer entrada.
Problema Parcialmente Solucionável ou Computável: Um problema é dito
Problema Parcialmente Solucionável ou Computável: é solucionável se existe um algoritmo que sempre pare quando a resposta é afirmativa (ACEITA). Entretanto, quando a resposta esperada for negativa, o programa pode parar (REJEITA) ou permanecer processando indefinidamente (LOOP).
Problema Completamente Insolúvel ou Não-Computável: quando não existe um algoritmo que solucione o problema tal que sempre pára quando a resposta é afirmativa (ACEITA).

7) Cite