Existe uma construção explícita curta de uma função recursiva universal ? Todas as definições que eu vi envolvem a numeração de máquinas de Turing de alguma forma, o que é possível, mas parece difícil e incontrolável escrever em uma linguagem de programação de nível superior (como Python, Haskell etc.)
9
Respostas:
E o intérprete Lisp original de McCarthy (originalmente aqui )? É universal, funciona em uma codificação natural (um Lisp AST), não depende de um intérprete externo e tem cerca de 20 linhas.
fonte
Certo. Escreva rotinas que computem cada uma das funções recursivas primitivas de Godel e escreva uma rotina para um operador de pesquisa ilimitado. O conjunto de funções que você pode calcular dessa maneira é equivalente ao conjunto de funções que as máquinas de Turing podem calcular. Mais informações aqui .
A desvantagem é que qualquer entrada em seu programa universal precisaria ser estruturada em termos dessas operações simples. Claro, é para isso que servem os compiladores.
fonte
Qualquer intérprete para qualquer idioma que seja completo em Turing é uma função recursiva universal. Existem interpretadores para linguagens de alto nível como C ++ ou Python.
A numeração de Godel existe, mas implicitamente. Por exemplo, o código C ++ calculando uma função recursivag é um índice para g .
fonte
Uma função universal
upode ser escrita facilmente em uma linguagem semelhante a Haskell (sem efeitos colaterais, funções de ordem superior), a saber:A função
ué universal porque aceita (a descrição) um programafe uma fita de entradax, e diz-lhe o resultado da execuçãofdex.Embora essa resposta não seja totalmente séria, ela mostra que um compilador ou intérprete para uma linguagem semelhante a Haskell já contém todas as partes necessárias para uma função universal. A moral da história é que é melhor gastar tempo estudando como os compiladores e intérpretes funcionam do que se preocupar em implementar uma função universal em termos de máquinas de Turing.
fonte
uassume uma função - eu chamaria de função de ordem superior. Eu gostariaude pegar um número inteiro ou um tipo de dados algébrico regular. Não forço nenhum modelo específico de computação, desde que o argumento touseja tangível - por exemplo, ele pode ser serializado de / para uma string.ufaz um fechamento, que é uma sequência finita de bytes. Mesmo no teorema utm usual, o número inteiro queurepresenta representa uma função.Veja também este artigo de John Tromp, usando lógica combinatória. Um artigo anterior, aparentemente não mais disponível, foi ainda mais organizado.
fonte