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

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...

Created: NaN

Last updated: 24-03-2026 [22:44]

For attribution, please cite this page as:

Charters, T., "Sobre a elegância de expressões escritas em LISP": https://nexp.pt/beleza.html (24-03-2026 [22:44])

(cc-by-sa) Tiago Charters - tiagocharters@nexp.pt