Por que as funções computáveis também são chamadas de funções recursivas?

23

Na teoria da computabilidade, funções computáveis também são chamadas de funções recursivas. Pelo menos à primeira vista, eles não têm nada em comum com o que você chama de "recursivo" na programação do dia-a-dia (isto é, funções que se denominam).

Qual é o significado real de recursivo no contexto da computabilidade? Por que essas funções são chamadas "recursivas"?

Em outras palavras: qual é a conexão entre os dois significados de "recursividade"?

computability terminology history Golo Roden
fonte

2

função μ-recursiva

Thomas Klimpel

3

Eles trapaceiam, porque incluem o operador μ . Este é um operador de minimização, mas é claro que a minimização tem muito pouco a ver com recursão. Parece que alguém (Kleene) achou que "recursivo" soaria legal, então ele inventou uma desculpa para usar esse nome. Muito mais tarde, Robert Soare explicou que "computável" soaria muito melhor e que "recursivo" acabara de ser um truque de marketing dos primeiros dias, e todos concordaram.

Thomas Klimpel

3

O que há sobre funções recursivas primitivas? Copiados da Wikipedia, eles são definidos como

h (0, x_{1}, \dots, x_{k}) = f (x_{1}, \dots, x_{k})

$h(0,x_{1},\ldots ,x_{k})=f(x_{1},\ldots ,x_{k})$ e

. Essa é uma função que se chama.

h (S (y), x_{1}, \dots, x_{k}) = g (y, h (y, x_{1}, \dots, x_{k}), x_{1}, \dots, x_{k})

$h(S(y),x_{1},\ldots ,x_{k})=g(y,h(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$

Hendrik Jan

3

@GoloRoden Observe que a descrição da tag 'computabilidade' (você a usou para esta pergunta) diz: "teoria da computabilidade, também conhecida como teoria da recursão". Gödel denominou funções recursivas , mas o termo evoluiu para computável . Provavelmente para evitar confusões como a sua. As pessoas que estudam a teoria da computabilidade (intensivamente) tendem a usar o termo teoria da recursão mais para "respeitar" suas raízes.

Auberon

1

porque eles são definidos recursivamente, ou seja, " funções mais complexas são definidas em termos de funções anteriormente definidas e mais simples "

Nikos M.

13

Defina algumas funções básicas:

função zero

$z e r o : N \to N : x \mapsto 0$ $zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0$
função sucessora

$s u c c : N \to N : x \mapsto x + 1$ $succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1$
função de projeção

p_{i}^{n} : N^{n} \to N : (x_{1}, x_{2}, \dots, x_{n}) \mapsto x_{i}

$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i$

A partir de agora vou usar para denotar $\bar{x_n}$ $(x_1, x_2, \dots, x_n)$

Defina uma composição:

Funções dadas

cada um com a assinatura $g_1, g_2, \dots, g_m$ $\mathbb{N}^k \rightarrow \mathbb{N}$
$f : \mathbb{N}^m \rightarrow \mathbb{N}$

Construa a seguinte função:

\begin{aligned} h : N^{k} \to N : \bar{x_{k}} \mapsto h (\bar{x_{k}}) = f ( & g_{1} (\bar{x_{k}}), g_{2} (\bar{x_{k}}), \dots, g_{m} (\bar{x_{k}})) \end{aligned}

$\begin{align} h: \mathbb{N}^k \rightarrow \mathbb{N}: \bar{x_k} \mapsto h(\bar{x_k}) = f ( & g_1(\bar{x_k}), g_2(\bar{x_k}), \dots, g_m(\bar{x_k}) ) \end{align}$

Defina recursão primitiva:

Funções dadas

$f: \mathbb{N}^k \rightarrow \mathbb{N}$
$g: \mathbb{N}^{k+2} \rightarrow \mathbb{N}$

Construa a seguinte função (por partes):

h : N^{k + 1} \to N : (\bar{x_{k}}, y + 1) \mapsto {\begin{cases} f (\bar{x_{k}}), & y + 1 = 0 \\ g (\bar{x_{k}}, y, h (\bar{x_{k}}, y)), & y + 1 > 0 \end{cases}

$h : \mathbb{N}^{k+1} \rightarrow \mathbb{N} : \\ (\bar{x_k}, y + 1) \mapsto \begin{cases} f(\bar{x_k}), & y + 1 = 0 \\ g (\bar{x_k}, y, h(\bar{x_k}, y)), & y + 1 > 0 \end{cases}$

Todas as funções que podem ser feitas usando composições e recursão primitiva em funções básicas são chamadas recursivas primitivas . É assim chamado por definição. Embora exista um link com funções que se autodenominam, não é necessário tentar vinculá-las. Você pode considerar a recursão um homônimo.

Essa definição e construção acima foram construídas por Gödel (algumas outras pessoas também estavam envolvidas) na tentativa de capturar todas as funções computáveis, ou seja, existe uma Máquina de Turing para essa função. Observe que o conceito de uma máquina de Turing ainda não foi descrito, ou era pelo menos muito vago.

Felizmente, alguém chamado Ackermann apareceu e definiu a seguinte função:

$Ack : \mathbb{N}^2 \rightarrow \mathbb{N}$
$Ack(0, y) = y+1$
$Ack(x+1, 0) = Ack(x, 1)$
$Ack(x+1, y+1) = Ack(x, Ack(x+1,y))$

Esta função é computável, mas não há como construí-la usando apenas as construções acima! (ie não é recursivo primitivo) Isso significa que Gödel e seu grupo falharam em capturar todas as funções computáveis em sua construção! $Ack$

Gödel teve que expandir sua classe de funções de modo poderia ser construído. Ele fez isso definindo o seguinte: $Ack$

Minimização ilimitada

$g : \mathbb{N}^k \rightarrow \mathbb{N}$
SE ENTÃO ELSE não está definido. $\left[f(\bar{x_k}, y) = 0 \text{ AND } \\f(\bar{x_k}, z) \text{ is defined } \forall z < y \text{ AND } \\f(\bar{x_k}, z)\neq 0\right]$

$g(\bar{x_k}) = y$

$g(\bar{x_k})$

Este último pode ser difícil de entender, mas basicamente significa que é a menor raiz de (se existir uma raiz). $g((x_1, x_2, \dots, x_k))$ $f$

Todas as funções que podem ser construídas com todas as construções definidas acima são chamadas recursivas . Novamente, o nome recursivo é apenas por definição e não necessariamente tem correlação com funções que se chamam. Na verdade, considere isso um homônimo.

Funções recursivas podem ser funções recursivas parciais ou funções recursivas totais . Todas as funções recursivas parciais são funções recursivas totais. Todas as funções recursivas primitivas são totais. Como exemplo de uma função recursiva parcial que não é total, considere a minimização da função sucessora. A função sucessora não tem raízes, portanto sua minimização não está definida. Um exemplo de uma função recursiva total (que usa minimização) é . $Ack$

Agora Gödel foi capaz de construir o função, bem com a sua classe alargada de funções. De fato, toda função que pode ser computada por uma máquina de Turing pode ser representada usando as construções acima e vice-versa, toda construção pode ser representada por uma máquina de Turing. $Ack$

Se você estiver intrigado, tente aumentar a classe de Gödel. Você pode tentar definir o 'oposto' da minimização ilimitada. Ou seja, maximização ilimitada , ou seja, a função que encontra a maior raiz. No entanto, você pode achar que calcular essa função é difícil (impossível). Você pode ler o problema Busy Beaver , que tenta aplicar a maximização ilimitada.

Auberon
fonte

4

Eu sei que percebo que as definições dadas realmente não respondem à pergunta, mas minha resposta descreve a evolução da teoria da recursão / computabilidade. Pode valer a pena ler.

Auberon

Eu gosto, obrigado por seus esforços :-)

Golo Roden

h ((x_{1}, x_{2}, . . ., x_{k}), 0) = f ((x_{1}, x_{2}, . . ., x_{k}))

$h((x_1, x_2, ..., x_k), 0) = f((x_1, x_2, ..., x_k))$

h ((x_{1}, x_{2}, . . ., x_{k}, 0))

$h((x_1, x_2, ..., x_k, 0))$ . Além disso, não existe uma cláusula anterior à próxima cláusula else do ponto de marcador.

Eric Towers

2

μ

$\mu$

1

Existem algumas afirmações incorretas na sua resposta. Você não deve inventar uma história para obter uma resposta.

Kaveh

17

Os fundadores da teoria da computabilidade foram matemáticos. Eles fundaram o que agora é chamado de teoria da computabilidade antes de haver computadores. Como os matemáticos definiram as funções que poderiam ser computadas? Por definições recursivas!

Portanto, havia função recursiva antes de qualquer outro modelo de computação, como máquinas de Turing, máquinas de cálculo ou registradoras lambda. Então, as pessoas se referem a essas funções como funções recursivas. O fato de eles terem sido exatamente o que as máquinas de Turing e outros modelos podem calcular é um evento posterior (principalmente provado por Kleene).

$\mu$

O nome do campo usado para a teoria da recursão. No entanto, houve um impulso bem-sucedido nas últimas décadas para mudar o nome para algo mais atraente, da teoria da recursão para algo mais científico (versus mathy). Como resultado, o campo agora é chamado de teoria da computabilidade. No entanto, se você olhar para livros, trabalhos, conferências, etc., nas primeiras décadas, eles serão chamados de teoria da recursão e não de teoria da computabilidade. Até o título do livro de 1987 de Soare (que foi a principal pessoa por trás do impulso de mudar o nome para a teoria da computabilidade) é "Conjuntos e graus recursivamente enumeráveis".

Se você quiser saber mais sobre a história, um lugar divertido e bom para ler sobre ela é o primeiro capítulo da Teoria da Recursão Clássica de Odifreddi.

Kaveh
fonte

7

Robert Soare escreveu um ensaio sobre esta questão. Segundo ele, o termo funções recursivas (gerais) foi cunhado por Gödel, que as definiu usando algum tipo de recursão mútua. O nome ficou preso, embora mais tarde outras definições equivalentes tenham sido encontradas.

Para mais informações, recomendo o ensaio de Soare.

Yuval Filmus
fonte

0

em vez de colocar um longo comentário, decidiu adicionar uma resposta:

Como são definidas recursivamente , ou seja, " funções mais complexas são definidas em termos de funções mais simples definidas anteriormente "

Esse tipo de procedimento iterativo ou incremental cria funções bem definidas (no sentido matemático)

Este é o significado de recursividade na linguagem matemática. Veja abaixo como isso se relaciona com a recursão na linguagem de programação.

Compare este procedimento com técnicas e métodos como indução (matemática), que também é um exemplo de recursividade na matemática.

A programação tem uma veia matemática e também uma de engenharia.

Esse procedimento (geralmente construtivo) também é chamado de " bootstrapping " na linguagem dos sistemas operacionais.

No entanto, uma recursão em tempo de execução da mesma função (ou seja, se auto-calibrando durante o tempo de execução ), uma vez que deve (hmm, deveria) ocorrer em valores (ou argumentos) já calculados ou, em outras palavras, na parte do conjunto de resultados já calculado , também é recursivo no sentido acima, ou seja, " funções definidas previamente definidas (e seus valores) "

Outra coisa não está bem definida e leva a coisas como Stack Overflow :))))

Para dar um exemplo adicional de Sistemas operacionais, uma recursão de tempo de execução (chamada própria) pode ser tomada como o análogo de um sistema operacional reinicializado após uma certa atualização (por exemplo, atualização principal). Muitos sistemas operacionais fazem o seguinte procedimento:

uma inicialização inicial para carregar rotinas de baixo nível (por exemplo, E / S)
faça as atualizações necessárias (usando as rotinas de baixo nível)
reinicialize (efetivamente, chamando a si mesmo), mas desta vez carregando as rotinas mais complexas (ou mesmo todo o sistema)

Auberon bela resposta de demonstra um procedimento desse tipo em mais detalhes.

Nikos M.
fonte

Por que as funções computáveis ​​também são chamadas de funções recursivas?

Respostas:

Por que as funções computáveis também são chamadas de funções recursivas?