Wolfram|Alpha: Systematic knowledge, immediately computable.

Wednesday, April 28, 2010

“Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.

Quine's Paradox. Named after the brilliant Willard Van Orman Quine, author of a favorite book of mine titled Quiddities: An Intermittently Philosophical Dictionary. The sentence is intended to show a paradox similar to The Liar Paradox can be had even without self-reference.

Named after him is the Quine Program, denoting a program that can reproduce itself as output, given no input (which makes the problem trivial, and is considered 'cheating'.)

It is effectively the Fixed Point of the execution environment. An example in Scheme looks like this:

((lambda (x)
   (list x (list (quote quote) x)))
      (lambda (x)
         (list x (list (quote quote) x)))))

For a mind-opening exposition on all things recursive and self-referential, I highly recommend a read of the amazing work by Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid

No comments:

Post a Comment