teoria da computabilidade

A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 1930 com o estudo das funções computáveis e do grau de Turing. O ramo se estendeu e passou a incluir o estudo generalizado da computabilidade e definibilidade. Nessas áreas, a teoria da recursão sobrepõe-se à teoria da prova e teoria efetiva de descrição dos conjuntos. As questões básicas envolvidas na teoria da recursão são " O que significa para uma função (N->N) ser computável?" e "Como funções não-computáveis são classificadas em uma teoria baseada nos seus níveis de não-computabilidade?". As respostas para estas perguntas levaram a uma rica teoria que ainda está sendo estudada atualmente.O ramo se aproximou também com relação à ciência da computação. Estudiosos da recursão em lógica matemática frequentemente estudam a teoria da computabilidade relativa, noções de redutibilidade e estruturas de grau descritas neste artigo. Isto contrasta com a teoria das hierarquias subrecursivas, métodos formais e linguagens formais que são comuns no estudo da teoria da computabilidade na ciência da computação. Existe uma sobreposição considerável no conhecimento e nos métodos entre estas duas comunidades de pesquisa. No entanto, não existe uma grande separação entre elas.