Sobre a elegância de expressões escritas em LISP
A medida, de uma expressão simbólica
em LISP é o número de caracteres utilizados para a escrever; representa-se
por
. 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 , como o número de caracteres da expressão mais pequena que a tem como valor. Vamos denotar este número por . Assim, como,
> (quote a) avem que
Dada uma expressão denote-se por a expressão mínima cujo valor é , i.e., o seu tamanho é a complexidade de , ou seja, .
Vamos dizer que uma expressão é 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:
- http://www.umcs.maine.edu/~chaitin/unknowable/ch5.html
- http://en.wikipedia.org/wiki/Berry_paradox
- http://en.wikipedia.org/wiki/Richard%27s_paradox
Preciso de mais referências para continuar...
Palavras chave/keywords: LISP, Goedel, belezaCriado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:25]
(c) Tiago Charters de Azevedo