Sobre a elegância de expressões escritas em LISP

Sobre a elegância das expressões de LISP e suas consequências

A medida, de uma expressão simbólica $latex2png equation$ em LISP é o número de caracteres utilizados para a escrever; representa-se por $latex2png equation$ . Por exemplo, o tamanho da expressão (car '(a b)) é dado por

> (length "(car '(a b)))")

13

Vamos definir a complexidade de uma expressão $latex2png equation$ , como o número de caracteres da expressão mais pequena que a tem como valor. Vamos denotar este número por $latex2png equation$ . Assim, como,

> (quote a)

a

vem que $latex2png equation$

Dada uma expressão $latex2png equation$ denote-se por $latex2png equation$ a expressão mínima cujo valor é $latex2png equation$ , i.e., o seu tamanho é a complexidade de $latex2png equation$ , ou seja, $latex2png equation$ .

Vamos dizer que uma expressão $latex2png equation$ é elegante se é a expressão mais pequena que tem o seu valor. Assim o tamanho de uma expressão elegante é igual à complexidade do seu valor.

Alguns exemplos de expressões elegantes são: o átomo t ou, ainda, qualquer número, i.e., a expressão 2 tem valor 2. O átomo t, que é uma expressão, tem valor t, e logo H(t)=|t|=1. t é uma expressão elegante.

O proximo passo é traduzir a construção de Chaitin em Common Lisp.

Ref:

Preciso de mais referências para continuar...

Palavras chave: LISP, Goedel, beleza

Última actualização/Last updated: 2012-02-26 [15:48]

1999-2011 (c) 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.