Funções Recursivas e Máquinas de Registradores

A teoria das funções recursivas constrói as funções computáveis a partir de um punhado de operações básicas, enquanto as máquinas de registradores computam com números inteiros armazenados em registradores, dois modelos que enquadram a máquina de Turing e confirmam a robustez da computabilidade.

Definition

As funções recursivas gerais são aquelas construídas a partir de constantes, sucessor e projeções por composição, recursão primitiva e minimização ilimitada; máquinas de registradores são dispositivos abstratos que computam incrementando, decrementando e testando o conteúdo de um conjunto finito de registradores que contêm números naturais.

Scope

Este tópico abrange as funções recursivas primitivas, a adição de minimização ilimitada para obter as funções recursivas gerais, a função de Ackermann como uma função computável que não é recursiva primitiva, máquinas de registradores e contadores e sua universalidade, e a equivalência de todos esses modelos com a computabilidade de Turing.

Core questions

• Como as funções computáveis podem ser definidas aritmeticamente sem qualquer máquina?
• Por que a minimização ilimitada é necessária além da recursão primitiva?
• Como máquinas de registradores simples alcançam o poder total da computação?
• Por que esses modelos aritméticos e de máquina coincidem com as máquinas de Turing?

Key theories

Equivalência com a computabilidade de Turing

As funções recursivas gerais e as funções computadas por máquinas de registradores são exatamente as funções Turing-computáveis, reforçando a tese de Church-Turing através de modelos definidos em termos puramente aritméticos e de máquina elementares.

Além da recursão primitiva

A função de Ackermann é total e computável, mas cresce muito rapidamente para ser recursiva primitiva, mostrando que a busca ilimitada é essencial e que as funções recursivas primitivas são uma subclasse própria das funções computáveis.

Universalidade das máquinas de registradores

Minsky mostrou que uma máquina com apenas dois contadores e as operações de incremento, decremento e teste de zero já é Turing-completa, uma demonstração extrema de quão pouca estrutura a computação completa requer.

Clinical relevance

Máquinas de registradores modelam a aritmética inteira de processadores reais mais diretamente do que as fitas, a recursão primitiva corresponde a programas que sempre terminam e fundamenta linguagens funcionais totais e análise de terminação, e a visão de função recursiva conecta a computação aos fundamentos da matemática.

History

Gödel e Herbrand definiram as funções recursivas gerais no início da década de 1930, e Kleene desenvolveu a teoria, incluindo o papel da minimização. Ackermann havia exibido anteriormente sua função de crescimento rápido, e Minsky introduziu máquinas de registradores e contadores na década de 1960, provando a universalidade até mesmo de máquinas de dois contadores.

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

Qual é a diferença entre funções recursivas primitivas e funções recursivas gerais?

As funções recursivas primitivas são construídas usando laços limitados e sempre terminam, mas não capturam todas as funções computáveis. Adicionar minimização ilimitada, uma busca que pode durar indefinidamente, produz as funções recursivas gerais, que coincidem exatamente com as funções Turing-computáveis.

Como uma máquina com apenas dois contadores pode ser tão poderosa quanto um computador?

Minsky mostrou que dois registradores contendo números naturais, com apenas incremento, decremento e teste de zero, podem simular uma máquina de Turing codificando sua fita nos registradores. A construção é altamente ineficiente, mas prova que o hardware mínimo já atinge o poder total da computação.