Axiomas de Peano e expressões simbólicas

Como relacionar os axiomas de Peano e expressões simbólicas de LISP

As expressões simbólicas em LISP (pelo menos o LISP inicial de John McCarthy) formam um sistema em tudo análogo aos números naturais e igualmente poderoso. Cada um deles pode ser usado para codificar sequências arbitrárias de símbolos, no entanto, e por razões óbvias, as expressões simbólicas são de leitura bastante mais fácil.

Vejamos então a semelhança entre os axiomas de Peano para os números naturais e os postulados das expressões simbólicas em LISP1.

Axiomas de Peano

  1. zero é um número
  2. o sucessor de um número é um número
  3. o zero não é sucessor de nenhum número
  4. dois números diferentes têm sucessores diferentes
  5. (Principio de indução finita) Uma propriedade que é verdade para zero, para um número e para o seu sucessor então também é verdade para todos os números.

Axiomas para expressões simbólicas

  1. átomos são expressões simbólicas
  2. o cons de duas expressões simbólicas é uma expressão simbólica
  3. um átomo não é o cons de duas outras expressões simbólicas
  4. se a é diferente de b, c é diferente de d, então o cons de a e c é diferente do cons de b e d.
  5. (Principio de indução finita) Se uma propriedade é verdadeira para todos os átomos, verdadeira para quaisquer duas expressões simbólicas e para o seu cons então também é verdade para todas as expressões simbólicas.

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: LISP, Peano, números, Godel

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

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.