CDR: Re: Godel & Turing - a final point

[Bill Stewart]

At 05:16 PM 11/9/00 -0600, Jim Choate wrote:
>On Thu, 9 Nov 2000, Jim Choate wrote:
>> On Wed, 8 Nov 2000, Sampo A Syreeni wrote:
>> 
>> > You are talking about two very different problems, here. Gödel/Turing
sorta
>> > things are about problems where quantifiers over an infinite set are
>> > permitted.
>> In the particular case we are speaking of we are talking about the
>> situation where the language consists of "all
>> consistent/valid/evaluatable/assignable boolean sentences".
>> 
>> Hence, somebody did a naughty...
>
>If you have a 'language' that is provably consistent then you know that
>that language is not complete or 'universal'. There MUST!!! be sentences
>which are not included in the listing.

That's fine.  The Satisfiability problem, and in particular 3-SAT,
doesn't claim to be complete or universal.  It's just a very large and
versatile class of Booleans, but it doesn't pretend to contain
Booleans that describe encodings of their own truth values
(unlike this discussion :-)   Just things of the form
	(A1 or A2 or A3...) AND (B1 or B2 or B3...) AND ....


				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639