quote Goedel

Representando meta-funções como números inteiros (codificação de Goedel)

A notação quote em LISP permite de uma maneira muito simples aplicar todo o conjunto de expressões simbólicas num sub-conjunto de si próprio¹, isto faz com que o conjunto de expressões simbólicas seja infinito e, para além disso, podemos usar as expressões que sobram para representar ouras coisas. Podemos aplicar esta ideia aos números naturais de uma maneira simples. O quote de um número natural n é (* 2 n), i.e., o seu dobro, usando a analogia entre uma expressão "quoted", por exemplo, (quote a), e a a própria expressão, a, que se obtém de (cadr (quote 'a)). Ficamos assim, desta forma, com os números ímpares para representar outras coisas.

Dado uma lista ordenada de variáveis, todas as que podemos pensar, vamos codificar a n-ésima variável por $latex2png equation$ onde a primeira toma o valor 10. Por exemplo a->10, b->11, etc. Se usarmos $latex2png equation$ para representar cond, $latex2png equation$ para representar lambda, etc, a codificação de um procedimento (f x y z) pode ser escrita como $latex2png equation$ , onde $latex2png equation$ codifica a.

Assim a expressão

(cond ((null a) 3) (t 6))

pode ser codificada através do número $latex2png equation$

Ficamos assim com a codificação de Goedel de todas as expressões de LISP :)

1. Guy Lewis Steele, Jr. and Gerald Jay Sussman. "The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two)". MIT AI Lab. AI Lab Memo AIM-453. May 1978.

Palavras chave/keywords: LISP, quote, Goedel

Criado/Created: NaN

Última actualização/Last updated: 10-10-2022 [14:25]

Voltar à página inicial.