Announcing ttcnf (Truth Table CNF), a program that computes the truth
tables generated by CNF boolean expressions of one to five variables.
It counts these truth tables in a number of ways. These results may be
useful in understanding CNF expressions.
http://www.qhull.org/ttcnf/
The number of truth tables for 3-CNF truth tables of three to five
variables is
256 43,146 120,510,132
This sequence is unlikely to be extended for a while. Using a 64-bit
computer, the generating program for six variables is easy to write,
but memory and time requirements make it impractical.
A conjecture is that 3-CNF truth tables are incompressible and hence
random. Randomness may be a pervasive property of the natural
numbers. The number of 3-CNF truth tables grows substantially slower
than the total number of truth tables
256 65,536 4,294,967,296
–Brad Barber
br…@shore.net wrote:
> Announcing ttcnf (Truth Table CNF), a program that computes the truth
> tables generated by CNF boolean expressions of one to five variables.
> It counts these truth tables in a number of ways. These results may be
> useful in understanding CNF expressions.
I once saw a story on tv where a guy took an adding machine, started
with 1, and kept adding 1 until he reached 1,000,000. They called him
the man who counted to a million. It took him years and a pile of
broken adding machines.
How is your procedure qualitatively different than his?
> A conjecture is that 3-CNF truth tables are incompressible and hence
> random.
Define incompressible here. And what does it have to do with
randomness (patternless phenomena)?
> Randomness may be a pervasive property of the natural
> numbers.
Is that why my computer is so flakey?
My 1st. grade math teacher lied!
And what is your favoritre random aspect of the natural numbers?
C-B
(Interested reader)
- Hide quoted text — Show quoted text -
> –Brad Barber
Charlie-Boo wrote:
> br…@shore.net wrote:
>>Announcing ttcnf (Truth Table CNF), a program that computes the truth
>>tables generated by CNF boolean expressions of one to five variables.
>>It counts these truth tables in a number of ways. These results may be
>>useful in understanding CNF expressions.
> I once saw a story on tv where a guy took an adding machine, started
> with 1, and kept adding 1 until he reached 1,000,000. They called him
> the man who counted to a million. It took him years and a pile of
> broken adding machines.
> How is your procedure qualitatively different than his?
A good point. Let’s trash the whole wicked experimental mathematics.
What’s use counting for example densities of zeros of Riemann’s function
on a computer? It’s passe, it’s abacus work, right? WRONG. If you don’t
know why, go troll somewhere else.
>>A conjecture is that 3-CNF truth tables are incompressible and hence
>>random.
> Define incompressible here. And what does it have to do with
> randomness (patternless phenomena)?
If you’d read the material the OP provided as a link, you’d have found
on the bottom of the page the words "algorithmic complexity". Does it
ring any bell or you just don’t understand the topic and want to
randomly troll? Your belief that randomness is somehow related to
patternless phenomena is by a large margin more vague and devoid of
concrete sense than the OP’s questions about randomness of small sets of
naturals.
>>Randomness may be a pervasive property of the natural
>>numbers.
> Is that why my computer is so flakey?
> My 1st. grade math teacher lied!
> And what is your favoritre random aspect of the natural numbers?
Again, from page OP provided (though I do admit it’s quite vague): "Is
randomness then a property of even relatively small subsets?" The
question certainly makes sense in his context. I am as far from an
expert as possible on this topic and maybe the problem has already been
solved, but I believe noone should dismiss the issue on the basis of it
being trivial (is it? I don’t think so) or badly posed or lame and
exactly such an attitude seems to follow from your post.
> C-B
> (Interested reader)
Really?
The results from ttcnf are in the On-Line Encyclopedia of Integer
Sequences.
A112535 — 3-CNF
http://www.research.att.com/projects/OEIS?Anum=A112535
A112650 — (n-1)-CNF
http://www.research.att.com/projects/OEIS?Anum=A112650
A109457 — 2-CNF (Knuth)
http://www.research.att.com/projects/OEIS?Anum=A109457
Charlie-Boo asks why?
Many problems are easy to test but expensive to solve. For example,
the traveling salesman problem minimizes the distance travelled in
visiting a set of cities. Computing the total distance for any
particular route is easy: sum the distance for each leg of the trip.
But computing the minimum distance appears to require a test for every
possible route.
The travelling salesman problem, and many other problems, are
equivalent to testing for satisfiability of a 3-CNF boolean expression.
These problems are called NP-complete. It is widely believed that
their solution requires more than polynomial time (abbreviated "P !=
NP"), but no one has been able to prove this statement.
Often the first step in understanding a problem is to analyze specific
cases. Ttcnf provides the details for five or fewer variables.
Instead of testing satisfiability, it generates all of the truth
tables. A 3-CNF expression is satisfiable if its truth table is not
0×0.
Charlie-Boo asked about incompressibility. A sequence is
incompressible if the shortest program to generate a sequence is the
sequence itself. For example, ’01010101….’ is easily compressed
(e.g., ‘a thousand pairs of 0 and 1′). A simple proof shows that at
least half of the numbers of n-bits are incompressible (search for
Kolmogorov Complexity). A similar proof holds for any fixed number of
additional bits (e.g., at least three quarters of the numbers of n-bits
require a program of at least n-1 bits).
It is unlikely that a similar proof applies to 3-CNF expressions. The
number of truth tables for 3-CNF expressions appears to grow much
slower than the number of possible truth tables.
If a sequence is incompressible, it doesn’t contain any patterns. A
conjecture is that the truth tables of 3-CNF expressions are
incompressible and random. If there were patterns in 3-CNF
expressions, a program should be able to use these patterns to
efficiently solve the satisfiability problem.
Charlie-Boo made a cogent observation: If randomness is a pervasive
property of the natural numbers, then almost all numbers are random,
including the numbers that define the contents of computer memory. As
Charlie-Boo observed, "Is that why my computer is so flakey?"
This does not imply that first-grade math teachers are fools. The
number of numbers is vast, leaving many useful numbers to run our
computers, keep the books, and challenge mathematicians.
Charlie-Boo asks "And what is your favorite random aspect of the
natural numbers?" Intelligence is sometimes seen as an emergent
property of complex computational systems. What appears to be
intelligence may really be randomness, leaving intelligence
unexplained.
–Brad
br…@shore.net wrote:
> Charlie-Boo asked about incompressibility. A sequence is
> incompressible if the shortest program to generate a sequence is the
> sequence itself.
That depends on the programming language. (So none of what you are
saying is meaningful.) Let us assume that silence gives consent, ok?
C-B
For example, ’01010101….’ is easily compressed
- Hide quoted text — Show quoted text -
> (e.g., ‘a thousand pairs of 0 and 1′). A simple proof shows that at
> least half of the numbers of n-bits are incompressible (search for
> Kolmogorov Complexity). A similar proof holds for any fixed number of
> additional bits (e.g., at least three quarters of the numbers of n-bits
> require a program of at least n-1 bits).
> It is unlikely that a similar proof applies to 3-CNF expressions. The
> number of truth tables for 3-CNF expressions appears to grow much
> slower than the number of possible truth tables.
> If a sequence is incompressible, it doesn’t contain any patterns. A
> conjecture is that the truth tables of 3-CNF expressions are
> incompressible and random. If there were patterns in 3-CNF
> expressions, a program should be able to use these patterns to
> efficiently solve the satisfiability problem.
> Charlie-Boo made a cogent observation: If randomness is a pervasive
> property of the natural numbers, then almost all numbers are random,
> including the numbers that define the contents of computer memory. As
> Charlie-Boo observed, "Is that why my computer is so flakey?"
> This does not imply that first-grade math teachers are fools. The
> number of numbers is vast, leaving many useful numbers to run our
> computers, keep the books, and challenge mathematicians.
> Charlie-Boo asks "And what is your favorite random aspect of the
> natural numbers?" Intelligence is sometimes seen as an emergent
> property of complex computational systems. What appears to be
> intelligence may really be randomness, leaving intelligence
> unexplained.
> –Brad
Charlie-Boo wrote:
> br…@shore.net wrote:
>>Charlie-Boo asked about incompressibility. A sequence is
>>incompressible if the shortest program to generate a sequence is the
>>sequence itself.
> That depends on the programming language.
Well, of course. However, in this context, one fixes the
computational model at the start and uses it throughout.
(So none of what you are
> saying is meaningful.) Let us assume that silence gives consent, ok?
Heh. Not so fast, C-B.
<snip>
Regards,
Rick
Charlie-Boo wrote:
> br…@shore.net wrote:
> That depends on the programming language. (So none of what you are
> saying is meaningful.) Let us assume that silence gives consent, ok?
You still don’t make an impression that you know what you are talking
about. Tip: consider growing families of finite sequences and all
possible Turing-complete languages. (And yes, the OP’s statement was
vague but if you just want to randomly whine, go away).
Rick Decker wrote:
> Charlie-Boo wrote:
> > br…@shore.net wrote:
> >>Charlie-Boo asked about incompressibility. A sequence is
> >>incompressible if the shortest program to generate a sequence is the
> >>sequence itself.
> > That depends on the programming language.
> Well, of course. However, in this context, one fixes the
> computational model at the start and uses it throughout.
Then you are talking about Quine programs (programs that output
themselves) and are defining any Quine program that is also the
shortest program to output it as being "random". That has nothing
to do with randomness, gives an infinite number of different ways to
define whether something is random or not (and so is a terrible
"definition"), and way less than half of the strings are Quine
Programs at all. If you were a programmer you would know more about
this.
C-B
BTW Virtually none of the concepts to which you are referring is
meaningful. That is why you will never be able to formally define them
and make any sense.
- Hide quoted text — Show quoted text -
> > Let us assume that silence gives consent, ok?
> Heh. Not so fast, C-B.
> <snip>
> Regards,
> Rick
- Hide quoted text — Show quoted text -
Charlie-Boo wrote:
> Rick Decker wrote:
>>Charlie-Boo wrote:
>>>br…@shore.net wrote:
>>>>Charlie-Boo asked about incompressibility. A sequence is
>>>>incompressible if the shortest program to generate a sequence is the
>>>>sequence itself.
>>>That depends on the programming language.
>>Well, of course. However, in this context, one fixes the
>>computational model at the start and uses it throughout.
> Then you are talking about Quine programs (programs that output
> themselves) and are defining any Quine program that is also the
> shortest program to output it as being "random". That has nothing
> to do with randomness, gives an infinite number of different ways to
> define whether something is random or not (and so is a terrible
> "definition"), and way less than half of the strings are Quine
> Programs at all. If you were a programmer you would know more about
> this.
> C-B
Okay, I’ll give this one more try (and will ignore the unmannerly
cheap shot).
Select your favorite programming language, X. We’ll stick with it
throughout this discussion. For any finite string, s, of 0s and 1s,
define the X-complexity of s to be the length in bits (bytes, whatever)
of the shortest X-program that produces s as output. Let’s denote the
X-complexity of s by K_X(s). Now it’s clear that there’s a constant
C such that for any string s, K_X(s) <= |s| + C, where |s| is the
length of s, since we could always write a program like this, for
s = ’000111010′, say:
function_s() {
print(’000111010′);
}
However, as has been noted before, some strings don’t carry much
information, like a string made of one hundred repetitions of ’01′
for example. We call a string (X-) compressible if it can be
generated by an X-program shorter than its length (with or without
the constant, it makes no real difference). Any other string we
call incompressible. Authors in this field also use "random" as
a substitute for "incompressible." Yes, it does depend on the
language chosen, but it doesn’t matter since no one is interested
in whether a particular string is incompressible, only that
for any particular length there is at least one incompressible
string of that length. This is easy to establish by counting
arguments.
The reason for the choice of "random" to describe such strings
makes sense if one thinks of "random" as related to "patternless."
For more information, look up "Kolmagorov complexity" or "algorithmic
information theory." It’s neat (and useful) stuff.
> BTW Virtually none of the concepts to which you are referring is
> meaningful. That is why you will never be able to formally define them
> and make any sense.
Well, it makes sense to a lot of theorists. Do with that what
you will.
Regards,
Rick
br…@shore.net wrote:
> Charlie-Boo asks "And what is your favorite random aspect of the
> natural numbers?"
Yes, I know how to unmask BS artists. You ask for details!
> Intelligence is sometimes seen as an emergent
> property of complex computational systems. What appears to be
> intelligence may really be randomness, leaving intelligence
> unexplained.
It requires intelligence to add up a long list of numbers, but an
adding machine uses only the smallest aspect of arithmetic, far from
being complex. So what you are saying lacks intelligence (or I should
say, the person who said that does.)
C-B
- Hide quoted text — Show quoted text -
> –Brad
RobertSzefler, Charlie-Boo & br…@shore.net wrote:
> > How is your procedure qualitatively different than his?
> A good point. Let’s trash the whole wicked experimental mathematics.
> What’s use counting for example densities of zeros of Riemann’s function
> on a computer? It’s passe, it’s abacus work, right? WRONG. If you don’t
> know why, go troll somewhere else.
You didn’t say anything about your procedure or his procedure, much
less show how yours is qualitatively different. You only quoted some
mumbo-jumbo about Riemann’s function (presumably just to try to impress
people – ha!)
C-B
Rick Decker & Charlie-Boo & br…@shore.net wrote:
> Okay, I’ll give this one more try (and will ignore the unmannerly
> cheap shot).
What unmannerly cheap shot (not that there were multiple)? Virtually
everything that I write is of very high quality, often offering
improvements to the published state of the art, e.g. my recent proof of
Rosser’s 1936 Theorem that by Occam’s Razor is to be preferred over
that of Rosser, Smullyan, Boolos and others. In fact, I have offered
two such proofs. Can you dispute that, one of my latest discoveries?
> Select your favorite programming language, X.
> For any finite string, s, of 0s and 1s,
> define the X-complexity of s to be the length in bits (bytes, whatever)
> of the shortest X-program that produces s as output. Let’s denote the
> X-complexity of s by K_X(s). Now it’s clear that there’s a constant
> C such that for any string s, K_X(s) <= |s| + C, where |s| is the
> length of s, since we could always write a program like this, for
> s = ’000111010′, say:
> function_s() {
> print(’000111010′);
> }
No. That’s your first mistake (and is related to the various other
flaws in Chaitin’s Algorithmic Information Theory.) The length of
the representation of a literal within a programming language is a
function of the programming language.
Specific Example: A Turing Machine requires many more than one bit or
character (it requires at least two tuples of 5 components) to write
each particular bit or character onto the tape.
General Example: One programming language can use the same constructs
as another but use two-byte syntax instead of one-byte syntax in the
program and/or its internal storage.
(Your assertions are the first step in a faulty "proof" of the
fallacious Invariance "Theorem" on which AIT is based. Assuming
that different programming languages use the same representation for a
literal will naturally reach the false conclusion that there is an
inherent length of the shortest program merely because you are tacitly
using your program above as a base of computing, which it is not. That
is why I say that your definitions make no sense.)
C-B
> Well, it makes sense to a lot of theorists.
Only to idiots. If you formalize it you see that it makes no sense.
Chaitin has always had problems when people tried to formalize his
stuff, having to backpedal many times.
> Do with that what you will.
LOL
- Hide quoted text — Show quoted text -
> Regards,
> Rick
Charlie-Boo wrote:
> Rick Decker & Charlie-Boo & br…@shore.net wrote:
>>Okay, I’ll give this one more try (and will ignore the unmannerly
>>cheap shot).
> What unmannerly cheap shot (not that there were multiple)? Virtually
> everything that I write is of very high quality, often offering
> improvements to the published state of the art, e.g. my recent proof of
> Rosser’s 1936 Theorem that by Occam’s Razor is to be preferred over
> that of Rosser, Smullyan, Boolos and others. In fact, I have offered
> two such proofs. Can you dispute that, one of my latest discoveries?
Do you mind presenting us with your breakthrough research?
- Hide quoted text — Show quoted text -
>>Select your favorite programming language, X.
>>For any finite string, s, of 0s and 1s,
>>define the X-complexity of s to be the length in bits (bytes, whatever)
>>of the shortest X-program that produces s as output. Let’s denote the
>>X-complexity of s by K_X(s). Now it’s clear that there’s a constant
>>C such that for any string s, K_X(s) <= |s| + C, where |s| is the
>>length of s, since we could always write a program like this, for
>>s = ’000111010′, say:
>> function_s() {
>> print(’000111010′);
>> }
> No. That’s your first mistake (and is related to the various other
> flaws in Chaitin’s Algorithmic Information Theory.) The length of
> the representation of a literal within a programming language is a
> function of the programming language.
Unfortunately you are right by a slick mistake the OP made in his
statement and yes it involves symbol/word representations but I doubt
you’ve really noticed that. And in general (apart from a density 0 set)
he is right and you should know that.
> Specific Example: A Turing Machine requires many more than one bit or
> character (it requires at least two tuples of 5 components) to write
> each particular bit or character onto the tape.
So? Would it suit you to include some constants in OP’s statements? In
what manner does it ruin his argument?
> General Example: One programming language can use the same constructs
> as another but use two-byte syntax instead of one-byte syntax in the
> program and/or its internal storage.
Gibberish. Count bits, will you? Think for a moment about constants and
constant factors.
> (Your assertions are the first step in a faulty "proof" of the
> fallacious Invariance "Theorem" on which AIT is based. Assuming
> that different programming languages use the same representation for a
> literal will naturally reach the false conclusion that there is an
> inherent length of the shortest program merely because you are tacitly
> using your program above as a base of computing, which it is not. That
> is why I say that your definitions make no sense.)
Well, enlighten us then what are the other miraculous options for
program representations apart from ol’good bits that will allow us to
surpass these "fallacious" theorems you despise so much.
>>Well, it makes sense to a lot of theorists.
> Only to idiots. If you formalize it you see that it makes no sense.
Charie, Boo!
> Chaitin has always had problems when people tried to formalize his
> stuff, having to backpedal many times.
At least he wrote some papers widely accepted by the community and
currently considered fundamental. Is the CS community wrong in general?
RobertSzefler & Charlie-Boo & Rick Decker & br…@shore.net wrote:
> Do you mind presenting us with your breakthrough research?
If you insist. Most of my results can be traced back to
http://arxiv.org/html/cs.LO/0003071 where I present a formal
axiomatization of several branches of Computer Science, including
Program Synthesis of number theory programs, DataBase Query Processing,
and the Theory of Computation.
Only a handful of authors have claimed to have generated Turing’s
theorem – the Unsolvability of the Halting Problem – and nobody
even claims to have (a) general formal axioms and rules that derive it,
and also (b) derive the unsolvabilty of the Membership Problem and the
solvability of various problems e.g. the existence of a Universal
Turing Machine.
(Fakes do things like write "axioms" that state the necessary
conclusions and even define a predicate almost identical with the
problem rather than being anything of general use.)
I have posted two proofs of Rosser’s 1936 extension to Godel’s 1st.
Incompleteness Theorem that are way simpler than those of Rosser,
Floyd, Rogers, Smullyan and Boolos (the latter based on Modal Logic),
as well as other authors who only repeat Rosser’s argument. Each of
my two proofs is easily formalized – as that is how I created them – by
formal manipulations.
Rosser’s Theorem can be proven by: "If a system is complete and
consistent, then the unprovable sentences coincide with the refutable
ones. However, the former is not recursively enumerable while the
latter is, so a consistent system must not be complete. qed" Who has
provided this or a simpler proof?
If there is interest, I can show (1) a formal derivation of this proof,
(2) another ultra-simple proof of Rosser’s Theorem [posted earlier],
(3) similar simple proofs of Godel’s results and (4) for a wide range
of Smullyan’s theorems, and (5) new Metamathematical theorems
generated including variations on Godel’s.
This includes a short proof of Godel’s 1st. Incompleteness Theorem
based on w-consistency, which most authors (e.g. Torkel) skip and those
who tackle it take an enormous amount of deduction to derive what they
claim to be Godel’s result. My formal proof takes about 7 steps.
(Parallel to it is a convincing logical argument that resembles Godel’s
original but is more tree-structured.)
When a paper claims to have generated a single famous theorem and gives
a complex (unintelligible) description, (1) it is absurd that a system
would generate only one theorem, (2) even if they claim elsewhere to
generate other theorems using the same system, the other related
theorems would have been created during the proof of the first theorem.
In my arxiv paper, you can see how a number of theorems are related by
sharing steps of deduction. (3) The simplest theorems are the formal
ones, if you merely abstract any complex system into the simpler one
that generates only the theorems of interest. This gives a high level
valid proof that relies on other results. This is what I present
above, where I rely on a number of results from the Theory of
Computation to greatly simplify many theorems of Logic.
All of this is in accordance with Occam’s Razor on the reuse of
existing results and the use of the simplest possible system to
represent (explain) something.
- Hide quoted text — Show quoted text -
> >>Select your favorite programming language, X.
> >>For any finite string, s, of 0s and 1s,
> >>define the X-complexity of s to be the length in bits (bytes, whatever)
> >>of the shortest X-program that produces s as output. Let’s denote the
> >>X-complexity of s by K_X(s). Now it’s clear that there’s a constant
> >>C such that for any string s, K_X(s) <= |s| + C, where |s| is the
> >>length of s, since we could always write a program like this, for
> >>s = ’000111010′, say:
> >> function_s() {
> >> print(’000111010′);
> >> }
> > No. That’s your first mistake (and is related to the various other
> > flaws in Chaitin’s Algorithmic Information Theory.) The length of
> > the representation of a literal within a programming language is a
> > function of the programming language.
> Unfortunately you are right by a slick mistake
What mistake? Rick makes no mistake in quoting Chaitin above. A quick
chronological check through Chaitin’s website uncovers a 1974 paper
describing what Rick is saying. In Information-Theoretic Computational
Complexity, IEEE Transactions on Information Theory IT-20 (1974), pp.
10-15, Chaitin writes,
"Now we would like to consider the most important properties of the
complexity of a string. First of all, the complexity of a string of
length n is less than n+c, because any string of length n can be
calculated by putting it directly into a program as a table. This
requires n bits, to which must be added c bits of instructions for
printing the table. In other words, if nothing betters occurs to us,
the string itself can be used as its definition, and this requires only
a few more bits than its length. Thus the complexity of each string of
length n is less than n+c." – Chaitin, 1974
> the OP made in his statement
The above description of X-complexity (written by Rick) is
self-contained, making no reference to the Original Post (by Brad). So
what are you talking about OP?
> and yes it involves symbol/word representations but I doubt
> you’ve really noticed that.
You say, "Yes, it involves . . .". So I just relayed to you the
notion of . . . But then you say "I doubt you’ve really noticed
that." (1) How can I relay a notion to you without having noticed
it? (2) What makes you doubt that I’ve really noticed it?
> And in general (apart from a density 0 set)
> he is right and you should know that.
He doesn’t mention sets (explicitly), saying,
(all Programming Languages X)
(exists Constant Number C)
(all Strings S)
K_X(s) <= |s| + C
Now where in the above assertion are you saying that he’s right and
where is he not right? Are you talking about the X or the C or the S
or what?
> > Specific Example: A Turing Machine requires many more than one bit or
> > character (it requires at least two tuples of 5 components) to write
> > each particular bit or character onto the tape.
> So? Would it suit you to include some constants in OP’s statements? In
> what manner does it ruin his argument?
I don’t know about the OP but the above equation K_X(s) <= |s| + C is
not established.
> > General Example: One programming language can use the same constructs
> > as another but use two-byte syntax instead of one-byte syntax in the
> > program and/or its internal storage.
> Gibberish. Count bits, will you? Think for a moment about constants and
> constant factors.
Rick is implying that there is no factor in the complexity of one
programming language vs. another, only a difference (the two values of
C.) I am showing that is not so. But simply the fact that the
equation is not established means any further conclusions using it are
not established.
> Well, enlighten us then what are the other miraculous options for
> program representations apart from ol’good bits that will allow us to
> surpass these "fallacious" theorems.
If you want to measure program size, then use the Godel number.
There’s no question about multiple programs having the same length.
(That factor alone got Chaitin in trouble years ago when his method for
generating the probability of a program halting created a
"probability" > 1 and he had to redefine it.)
What is the goal? (1) Define random? Look at statistics books and
remember you’re talking about an infinite series (so such terms as
"eventually" make sense) not Chaitin’s finite strings.
(2) Improve upon Godel’s Theorems by using a different paradox than
the Liar Paradox (if that makes any sense)? Berry’s Paradox of the
smallest/largest number/program requiring/outputting a certain number
[of words] tells us that the minimum/maximum program/number that
outputs/is output by a given number/program is not a recursive function
of that number/program. (All are equivalent.) (Consider the smallest
number requiring a million words other than using the given phrase, and
define them in terms of this number.) Chaitin is trying to tell us
that it is recursive, which is the opposite of the truth.
(Godel didn’t "use the Liar Paradox" any more than he "used
Russell’s Paradox". They are all siblings, not dependents.)
> Charie, Boo!
Oh, you scared me!
> > Chaitin has always had problems when people tried to formalize his
> > stuff, having to backpedal many times.
> At least he wrote some papers widely accepted by the community and
> currently considered fundamental. Is the CS community wrong in general?
Are you familiar with the writings of Raatikainen Panu? Belief in
Chaitin in arguably one of the 3 biggest mistakes in conventional
wisdom concerning theoretical Computer Science (Mathematics, Logic,
Computability, Recursion Theory, Program Synthesis and Analysis, etc.)
C-B
"Charlie-Boo" <ch…@aol.com> writes:
> Rosser’s Theorem can be proven by: "If a system is complete and
> consistent, then the unprovable sentences coincide with the refutable
> ones. However, the former is not recursively enumerable while the
> latter is, so a consistent system must not be complete. qed" Who has
> provided this or a simpler proof?
Turing (1936), and of course many others. So where, do you think,
does the interest of Rosser’s proof lie, as compared to this argument?
> This includes a short proof of Godel’s 1st. Incompleteness Theorem
> based on w-consistency,
Gödel had good reasons for introducing the concept of
omega-consistency, but it’s really a highly impenetrable condition,
and today there is no reason not to use the very much simpler
(and weaker) concept of Sigma-1-soundness (or 1-consistency).
> Are you familiar with the writings of Raatikainen Panu?
Panu Raatikainen’s criticism concerns the claims made by Chaitin and
others regarding the interpretation and significance of Chaitin’s
work. He does not assert that anything in that work is logically or
mathematically incorrect.
Torkel Franzen wrote:
> "Charlie-Boo" <ch…@aol.com> writes:
> > Rosser’s Theorem can be proven by: "If a system is complete and
> > consistent, then the unprovable sentences coincide with the refutable
> > ones. However, the former is not recursively enumerable while the
> > latter is, so a consistent system must not be complete. qed" Who has
> > provided this or a simpler proof?
> Turing (1936)
No, Turing does not provide this proof (or one as short and simple.)
If you want to say that my proof can be derived from Turing’s
principles, then I agree – that is what I did. But Turing himself
makes no reference to the refutable sentences being r.e. vs. the
unprovable sentences that are not r.e. etc. (Do you agree?)
> and of course many others.
References (including page numbers which refer to the contrast between
the refutable and unprovable sentences), please. Does that include the
work of Smullyan, Rogers, Floyd or Boolos?
> So where, do you think,
> does the interest of Rosser’s proof lie, as compared to this argument?
I’m not sure what you mean. If you are talking about the value of a
simple proof or reusing existing results, I would cite Occam’s Razor
(not that it really needs to be explained.)
> > This includes a short proof of Godel’s 1st. Incompleteness Theorem
> > based on w-consistency,
> Gödel had good reasons for introducing the concept of
> omega-consistency
Not really. Omega-consistency is introduced just to complete his
proof. He wanted to eliminate a certain condition, so he just coined
the term "Omega-consistent" and said to assume that it holds.
There is no intuitive appeal.
If one shows that soundness => incompleteness, then we may consider the
fact, "My system is sound – for good reason, so there are sentences
that I will never decide using it. I’ll be darned!" However,
there is no similar conclusion one may make from Omega-consistent =>
incomplete. It is what programmers call a "kludge" – a rule added
just to cover one case.
I would argue that the lack of an intuitive appeal to Omega-consistency
calls into question the value of this theorem. It is as if one came up
with a condition C equivalent to incompleteness and then
"concluded" that C => incompleteness. What does that get you?
> but it’s really a highly impenetrable condition,
> and today there is no reason not to use the very much simpler
> (and weaker) concept of Sigma-1-soundness (or 1-consistency).
Each theorem has implicit assumptions concerning its logic that make it
more or less applicable than others. For example, Rosser’s result is
considered stronger than Godel’s, but requires the existence of an
expression for less than suitably axiomatized, which while common is
not actually required in other proofs.
> > Are you familiar with the writings of Raatikainen Panu?
> Panu Raatikainen’s criticism concerns the claims made by Chaitin and
> others regarding the interpretation and significance of Chaitin’s
> work. He does not assert that anything in that work is logically or
> mathematically incorrect.
See:
http://64.233.167.104/search?q=cache:Dm_GZrNQfBEJ:www.ams.org/notices…
For example: "Chaitin interprets his own variants of incompleteness
theorems as follows: "The general flavor of my work is like this. You
compare the complexity of the axioms with the complexity of the result
you’re trying to derive, and if the result is more complex than the
axioms, then you can’t get it from those axioms" (The Unknowable, p.
24). Or, in other words: "my approach makes incompleteness more
natural, because you see how what you can do depends on the axioms. The
more complex the axioms, the better you can do" (The Unknowable, p.
26).
But appearances notwithstanding, this is simply wrong. In fact, there
is no direct dependence between the complexity of an axiom system and
its power to prove theorems. On the one hand, there are extremely
complex systems of axioms that are very weak and enable one to prove
only trivial theorems. Consider, for example, an enormously complex
finite collection of axioms with the form n < n + 1; even the simple
theory consisting of the single generalization "for all x, x < x + 1"
can prove more. On the other hand, there exist very simple and compact
axiom systems that are sufficient for the development of all known
mathematics (e.g., the axioms of set theory) and that can in particular
decide many more cases of program-size complexity than some extremely
complex but weak axiom systems (such as the one above). Moreover, it is
possible for two theories to differ considerably in strength or
complexity but nevertheless be able to decide exactly the same facts
about program-size complexity and have the same Chaitinian finite limit
c [12].
Analogously, Chaitin’s claim with respect to ? that "an N-bit formal
axiomatic system can determine at most N bits of ?" (The Unknowable, p.
90) is again not true for related reasons [13]."
(Add to these refutations the fact that any system with an infinite
number of theorems will have no upper bound to the complexity of its
theorems.)
C-B
"Charlie-Boo" <ch…@aol.com> writes:
> No, Turing does not provide this proof (or one as short and simple.)
Read his paper.
> References (including page numbers which refer to the contrast between
> the refutable and unprovable sentences), please.
Acquaint yourself with the literature.
> I’m not sure what you mean.
I mean, what is the significant difference between the proof of
incompleteness from the recursive undecidability of T and Rosser’s
proof?
> Not really. Omega-consistency is introduced just to complete his
> proof.
A very good reason.
> For example, Rosser’s result is
> considered stronger than Godel’s,
They are of incomparable strength when formulated generally. Gödel’s
proof is better formulated in terms of 1-consistency.
> See:
So?
Torkel Franzen & Charlie-Boo wrote:
> > No, Turing does not provide this proof (or one as short and simple.)
> Read his paper.
There is nothing in the paper about the unprovable sentences not being
r.e. in contrast to the refutable ones being r.e. The paper is all
about recursive undecidability, of course, but it does not contain my
formulation of a proof of Rosser’s result. You have not substantiated
your claim nor even challenged my refutation.
> > References (including page numbers which refer to the contrast between
> > the refutable and unprovable sentences), please.
> Acquaint yourself with the literature.
Well, I read your two books on the subject, but neither of them gives
Rosser’s or the omega-consistency proofs, so that didn’t do me any
good. Admitedly that was my mistake, not consulting a state-of-the-art
reference.
You have not substantiated your claim nor even challenged my
refutation.
> > I’m not sure what you mean.
> I mean, what is the significant difference between the proof of
> incompleteness from the recursive undecidability of T and Rosser’s
> proof?
12 pages
> > Not really. Omega-consistency is introduced just to complete his
> > proof.
> A very good reason.
Introducing a premise only to finish a proof is a very lousy reason.
It has no intuitive or practical significance. It is a mere
reconstitution of the conclusion sought. The difference between the
premise and the conclusion may be trivial.
> > For example, Rosser’s result is
> > considered stronger than Godel’s,
> They are of incomparable strength when formulated generally. Gödel’s
> proof is better formulated in terms of 1-consistency.
Yes, that was my point, although I’m not sure what you mean by
"formulated generally". I reached my conclusion by formulating
them rigorously. But all of this seems to contradict your statement,
"there is no reason not to use the very much simpler (and weaker)
concept of Sigma-1-soundness (or 1-consistency)".
> > See:
> So?
You wrote, "Panu Raatikainen does not assert that anything in that
work is logically or mathematically incorrect." However, he states
that, "(Chaitin) is simply wrong. In fact, there is no direct
dependence between the complexity of an axiom system and its power to
prove theorems." and "Chaitin’s claim with respect to Omega that
"an N-bit formal axiomatic system can determine at most N bits of
Omega" (The Unknowable, p. 90) is again not true for related
reasons.", which contradicts your claim.
Now who really needs to aquaint themselves with the literature?
C-B
"Charlie-Boo" <ch…@aol.com> writes:
> You have not substantiated
> your claim nor even challenged my refutation.
You need to read Turing’s paper a bit more carefully.
> Well, I read your two books on the subject, but neither of them gives
> Rosser’s or the omega-consistency proofs, so that didn’t do me any
> good. Admitedly that was my mistake, not consulting a state-of-the-art
> reference.
It’s unclear what you mean by "read", but no book is suitable for
everybody. If you want to acquire a basic grasp of the subject, I
suggest you begin by working through (not "reading" in your sense)
Smullyan’s "Gödel’s incompleteness theorems".
> > I mean, what is the significant difference between the proof of
> > incompleteness from the recursive undecidability of T and Rosser’s
> > proof?
> 12 pages
You need to think a bit more about this.
> But all of this seems to contradict your statement,
> "there is no reason not to use the very much simpler (and weaker)
> concept of Sigma-1-soundness (or 1-consistency)".
Then you need to think about this a bit more.
> You wrote, "Panu Raatikainen does not assert that anything in that
> work is logically or mathematically incorrect." However, he states
> that, "(Chaitin) is simply wrong. In fact, there is no direct
> dependence between the complexity of an axiom system and its power to
> prove theorems." and "Chaitin’s claim with respect to Omega that
> "an N-bit formal axiomatic system can determine at most N bits of
> Omega" (The Unknowable, p. 90) is again not true for related
> reasons.", which contradicts your claim.
These statements of Raatikainen’s concern claims about the
interpretation and significance of theorems proved by Chaitin.
You will find no assertion by Raatikainen that any mathematical
theorem stated and proved by Chaitin is incorrect.
Torkel Franzen & Charlie-Boo write:
> > You have not substantiated
> > your claim nor even challenged my refutation.
> You need to read Turing’s paper a bit more carefully.
You are merely attacking the messenger and continue to make
unsubstantiated statements.
The truth of the matter is that Turing makes no reference to the
refutable sentences being different from the unprovable ones (because
the former set is r.e. and the latter is not) and being smug does not
cover up the fact that neither you nor anyone else can point to a
passage where he does.
> > Well, I read your two books on the subject, but neither of them gives
> > Rosser’s or the omega-consistency proofs, so that didn’t do me any
> > good. Admitedly that was my mistake, not consulting a state-of-the-art
> > reference.
> It’s unclear what you mean by "read", but no book is suitable for
> everybody.
That latter fact doesn’t seem to hinder other authors from writing
state-of-the-art texts.
> If you want to acquire a basic grasp of the subject, I
> suggest you begin by working through (not "reading" in your sense)
> Smullyan’s "Gödel’s incompleteness theorems".
You keep saying that, but I remind you that I recently presented to you
a transcript of Smullyan’s proof of Rosser’s result:
http://groups.google.com/group/sci.logic/msg/0454e3bb403aad73
as an example of the complexity of published expositions. This only
confirms my contention that standard treatments are much more complex
than my 2 sentence proof. If you’re trying to prove me wrong, I
suggest you come up with a valid example. (I quoted from Theory of
Formal Systems because the presentation is more consolidated than in
Godel’s Incompleteness Theorems, which is likewise much more complex
than my simple proof.)
> > > I mean, what is the significant difference between the proof of
> > > incompleteness from the recursive undecidability of T and Rosser’s
> > > proof?
> > 12 pages
> You need to think a bit more about this.
Do you believe in Occam’s Razor, "what can be done with less is done
in vain with more."?
> > But all of this seems to contradict your statement,
> > "there is no reason not to use the very much simpler (and weaker)
> > concept of Sigma-1-soundness (or 1-consistency)".
> Then you need to think about this a bit more.
My concern is consistency.
> > You wrote, "Panu Raatikainen does not assert that anything in that
> > work is logically or mathematically incorrect." However, he states
> > that, "(Chaitin) is simply wrong. In fact, there is no direct
> > dependence between the complexity of an axiom system and its power to
> > prove theorems." and "Chaitin’s claim with respect to Omega that
> > "an N-bit formal axiomatic system can determine at most N bits of
> > Omega" (The Unknowable, p. 90) is again not true for related
> > reasons.", which contradicts your claim.
> These statements of Raatikainen’s concern claims about the
> interpretation and significance of theorems proved by Chaitin.
> You will find no assertion by Raatikainen that any mathematical
> theorem stated and proved by Chaitin is incorrect.
Where does he mention "interpretation" or "significance" in the
above? He says, "Chaitin is simply wrong." and "Chaitin’s
claim is not true." How could one be any more clear in stating that
something is incorrect?
BTW Do you believe the above two assertions made by Chaitin?
C-B
"Charlie-Boo" <ch…@aol.com> writes:
[...]
It’s a simple observation that a complete recursively axiomatizable
theory is decidable, and hence that an undecidable recursively
axiomatizable theory is incomplete. Surely you don’t believe that
you’re the first to make this observation? The fact that you can’t
find it in Turing’s paper is perhaps indicative of a general
reading problem.
You also appear resolute in not wishing to learn anything, as
manifested in the recent exchange on intuitionistic propositional
logic as well as in your present comments.
Torkel Franzen & Charlie-Boo write:
> It’s a simple observation that a complete recursively axiomatizable
> theory is decidable, and hence that an undecidable recursively
> axiomatizable theory is incomplete. Surely you don’t believe that
> you’re the first to make this observation? The fact that you can’t
> find it in Turing’s paper is perhaps indicative of a general
> reading problem.
Carefully compare Turing’s proof of Rosser’s result to mine. You
are quoting Turing’s proof but that is not my proof.
This debate has been whether Turing gave the same proof as I, not
whether or not he proved the result at all.
[personal attack snipped]
C-B
"Charlie-Boo" <ch…@aol.com> writes:
> Carefully compare Turing’s proof of Rosser’s result to mine. You
> are quoting Turing’s proof but that is not my proof.
What I am quoting is the simple observation that a complete
recursively axiomatizable theory is incomplete. What do you believe
yourself to have added to this?
Rosser’s result, by the way, is a different one.
"Charlie-Boo" <ch…@aol.com> writes:
> Carefully compare Turing’s proof of Rosser’s result to mine. You
> are quoting Turing’s proof but that is not my proof.
What I am quoting is the simple observation that an undecidable
recursively axiomatizable theory is incomplete. What do you believe
yourself to have added to this?
Rosser’s result, by the way, is a different one.
Torkel Franzen & Charlie-Boo write:
> > Carefully compare Turing’s proof of Rosser’s result to mine. You
> > are quoting Turing’s proof but that is not my proof.
> What I am quoting is the simple observation that a complete
> recursively axiomatizable theory is incomplete. What do you believe
> yourself to have added to this?
Consistency in my statements.
> Rosser’s result, by the way, is a different one.
I certainly hope so.
C-B
(Note to reader: What does the above odd statement by Torkel actually
amount to?)