Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!stanford.edu!agate!eris.berkeley.edu!doug
From: doug@eris.berkeley.edu (Doug Merritt)
Newsgroups: comp.compression
Subject: Re: Integer not expressable in less than 13 words
Message-ID: <1991Apr29.031638.17275@agate.berkeley.edu>
Date: 29 Apr 91 03:16:38 GMT
References: <15901@smoke.brl.mil> <1991Apr25.234539.24276@unislc.uucp> <15989@smoke.brl.mil>
Sender: root@agate.berkeley.edu (Charlie Root)
Organization: University of California, Berkeley
Lines: 47

In article <15989@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes:
>
>Oh, good -- then we can conclude that all positive integers are
>expressable in fewer than 13 English words. [...]
>In case you didn't detect the sarcasm, I'm well aware of Godel's
>work etc. but I don't think it helps answer the question "What is
>wrong with this argument?".  Self-reference is not automatically
>invalid; consider "This is a sentence."  [...]
>  Even "This is not a sentence." is meaningful, albeit
>false.  "The set of all sets that do not include themselves" is
>not meaningful, but you can't lay the entire blame on self-reference.

Some good points, good enough to reply to. (A great deal of the stuff
in this thread has sounded as if people had never heard the subject
discussed before, hard though that is to believe.)

You go too far with that last point, though. Self reference can be
very useful, but the "entire blame" for self-contradiction *does* lay
on self-reference.

Saying that such self-contradiction is "not meaningful" can work for
simple cases, where you can pin down the problem to a very small set
of symbols which contradict each other. It does not work in general,
however, because one can have very complex systems of logic/math
in which one finds contradictions, without any *single* statement being
the culprit. This is the general class of inconsistent statements,
and Godel's theorem does apply.

The big problem is that, Godel notwithstanding, systems with the power
of self-reference are just too handy to toss out. Try to get by on
propositional logic rather than predicate logic, for instance. This
was the reef on which Principia Mathematica foundered. The "Theory of
Types" was introduced to try to get around it, and most mathematicians
(e.g. all of the ones who hang out in sci.math) consider this to be
workable for the things they care about, but it turns out not to be
equivalent in power, and so no really ultimate solution has been found yet.

That is, people will sometimes claim the crisis is over, but they're the
ones who don't find a need for self referential systems. The people who
do find self reference handy (extremely frequent in CS) try to avoid
inconsistency by what amounts to exhaustive test. I have yet to see the
two camps agree on anything fundamental.
	Doug
-- 
--
Doug Merritt		doug@eris.berkeley.edu (ucbvax!eris!doug)
		or	uunet.uu.net!crossck!dougm