Importância da recursão na teoria da computabilidade

Diz-se que a teoria da computabilidade também é chamada de teoria da recursão. Por que é assim chamado? Por que a recursão tem tanta importância?

Nas décadas de 1920 e 1930, as pessoas tentavam descobrir o que significa "computar efetivamente uma função" (lembre-se, não havia máquinas de computação de uso geral e a computação era algo que as pessoas faziam).

Várias definições de "computável" foram propostas, das quais três são mais conhecidas:

1. O cálculo$\lambda$
2. Funções recursivas
3. Máquinas de Turing

$\lambda$

Mais tarde, houve um esforço, popularizado por Robert Soare , de mudar "recursivo" para "computável". Assim, hoje em dia falamos de funções computáveis ​​e conjuntos computáveis ​​enumeráveis. Mas muitos livros antigos e muitas pessoas ainda preferem a terminologia "recursiva".

Tanta coisa para a história. Também podemos perguntar se a recursão é importante para a computação de um ponto de vista puramente matemático. A resposta é um "sim!" Muito definitivo. A recursão está na base das linguagens de programação de uso geral (até os whileloops são apenas uma forma de recursão porque while p do cé a mesma que if p then (c; while p do c)) e muitas estruturas de dados fundamentais, como listas e árvores, são recursivas. A recursão é simplesmente inevitável na ciência da computação, e na teoria da computabilidade especificamente.

A teoria da computabilidade é o estudo das funções computáveis ​​:-).

Tais funções são geralmente (nesta comunidade) definidas como funções que podem ser expressas com uma máquina de Turing.

$f: \mathbb{N} \mapsto \mathbb{N}$$T$$T$$x = 1^n$$T$$1^{f(x)}.$

Como se vê, se você definir funções computáveis ​​dessa maneira (programas), elas serão equivalentes ao conjunto de funções que se pode obter usando as regras descritas aqui . Eles são chamados de funções recursivas, uma vez que uma das regras para obter tais funções é uma definição recursiva (consulte a 5ª regra na wikipedia).

Portanto, a razão pela qual a teoria da recursão tem muita importância é equivalente à questão de por que as funções computáveis ​​são importantes. E a resposta para este último deve ser bastante óbvia :)