✍ 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óprio1, 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: 23-01-2017 [09:19]


GNU/Emacs

1999-2017 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.