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@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639