Funções Recursivas Primitivas para Programadores de Produção

Funções recursivas primitivas: um guia para programadores de produção

Programadores costumam usar o termo "completude de Turing". Em certos domínios, não ser Turing-completo às vezes é visto como uma virtude ou um requisito. No entanto, a maior parte das discussões se baseia em informação incorreta. O que não ser Turing-completo realmente significa é outra coisa. Completude de Turing é um termo matemático, com um significado muito específico. Não é permitido reinterpretá-lo para outros usos.

Parte I: Resumo

• Se um programa escrito em uma linguagem Turing-completa executa mais rápido que O(22N), então ele também pode ser implementado em uma linguagem não Turing-completa.
• A maioria dos problemas práticos é mais rápida que "dois de dois de dois".
• Linguagens não Turing-completas não impõem limitações práticas.
• Um programa que não termina e um programa que leva um tempo absurdamente grande para terminar são tratados da mesma forma.

Parte II: Como as máquinas funcionam

Máquinas de estados finitos (Finite State Machines)

• Uma máquina de estados finitos recebe uma string como entrada e retorna "sim" ou "não".
• Ela tem um número finito de estados.
• A função de transição de estado recebe o estado atual e o próximo símbolo de entrada, e retorna um novo estado.
• Uma máquina de estados finitos não pode entrar em loop infinito.
• Uma máquina de estados finitos tem o mesmo poder de expressão que expressões regulares.

Máquinas de Turing (Turing Machines)

• Uma máquina de Turing é um pouco mais complexa que uma máquina de estados finitos.
• Uma máquina de Turing opera usando uma fita variável.
• A função de transição de estado recebe o estado atual e o símbolo atual da fita, e retorna um novo estado, um símbolo e uma direção de movimento.
• Uma máquina de Turing funciona como uma função e pode entrar em loop infinito.
• Uma máquina de Turing pode simular uma máquina de estados finitos.

Programando máquinas de Turing

• Máquinas de Turing têm uma fita infinita.
• Máquinas de Turing não executam programas fornecidos pelo usuário. O programa é hardcoded na máquina.
• Uma máquina de Turing universal pode simular outras máquinas de Turing.
• Máquinas de Turing têm a mesma capacidade computacional que linguagens como Python.

Limites das máquinas de Turing

• Existem funções que não podem ser implementadas com máquinas de Turing.
• É possível enumerar todas as máquinas de Turing, mas não todas as funções.
• Certos problemas (por exemplo, o problema da parada) não podem ser resolvidos por máquinas de Turing.
• O poder das máquinas de Turing torna impossível determinar se um programa vai terminar.

Parte III: Voltando aos problemas práticos

Funções recursivas primitivas (Primitive Recursive Functions)

• Funções recursivas primitivas recebem uma tupla de números naturais como entrada e retornam um número natural.
• Elas começam com as funções zero e succ e constroem outras funções a partir delas.
• Recursão geral não é permitida, mas formas restritas de loop são permitidas.
• É possível definir operações como adição, multiplicação e exponenciação.
• É possível definir operadores lógicos e condicionais.
• Números são usados para representar estruturas de dados.

Resumo do GN⁺

• Este texto foi escrito para ajudar na compreensão da completude de Turing e das funções recursivas primitivas.
• Ele explica o que não ser Turing-completo significa na prática.
• Explica a diferença entre máquinas de estados finitos e máquinas de Turing, e discute os limites das máquinas de Turing.
• Explica a definição e o uso de funções recursivas primitivas.
• Este texto ajudará programadores a aprofundar sua compreensão sobre completude de Turing e funções recursivas primitivas.
• Projetos com funcionalidades semelhantes incluem "expressões regulares" e "máquinas de estados finitos".