computabilidade

Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação. A computabilidade de um problema é intimamente ligada à existência de um algoritmo para resolver o problema. Os modelos mais estudados da computabilidade são as funções Turing-Computáveis e as funções μ-recursivas, e o cálculo lambda, todos os quais têm poderes computacionais equivalentes. Outras formas de computabilidade são também estudadas: noções de computabilidade mais fracas que as máquinas de Turing são estudadas na Teoria dos autômatos, enquanto que noções mais fortes que as máquinas de Turing são estudadas no campo da Hipercomputação.