✍ 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/keywords: LISP, Goedel, beleza

Última actualização/Last updated: 2014-11-13 [00:02]


1999-2014 (ç) 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.