Importância da recursão na teoria da computabilidade

12

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?

user5507
fonte

Respostas:

20

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λ
  2. Funções recursivas
  3. Máquinas de Turing

λ

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.

Andrej Bauer
fonte
1

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:NNTTx=1nT1f(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 :)

Jernej
fonte