Teoria de Computabilidade

A teoria da computabilidade estuda os problemas e verifica se existe uma função computável que os solucionem. Um resultado fundamental foi obtido pelo pesquisador inglês Alan Turing. O problema da decisão (ou parada) é posto da seguinte forma: “Dado  um algoritmo A qualquer, existe um algoritmo B que, determina se A termina?”. Turing demonstrou que trata-se de um problema indecidível. Em decorrência, mais tarde, desta descoberta criou-se o prêmio Turing, o que é análogo ao prêmio Nobel, oferecido à cientistas e pesquisadores da área da computação.

Dentro da teoria das funções computáveis, existe a teoria computacional da complexidade (complexidade não no sentido de dificuldade), que estuda a eficiência dos algoritmos. Um algoritmo soluciona um problema. Solucionar um problema é equivalente a computar uma função do conjunto de entrada para o conjunto de saída. Assim a computação de uma função (computável) pode ser realizada por um algoritmo.

Para medirmos a eficiência de um algoritmo, necessitamos de: axiomas de medidas e modelo formal de computação. Os axiomas de medidas permitirão quantificar o número de operações efetuadas pelo algoritmo quando executado segundo as diretrizes do modelo formal de computação.