Re: Largest provable BB(N)?
From: KRamsay (kramsay_at_aol.com)
Date: 11/01/04
- Next message: Arturo Magidin: "Re: Sylow problem"
- Previous message: KRamsay: "Re: Largest provable BB(N)?"
- Maybe in reply to: KRamsay: "Re: Largest provable BB(N)?"
- Messages sorted by: [ date ] [ thread ]
Date: 01 Nov 2004 04:57:04 GMT
In article <41811ade.274398895@news.eircom.net>, wallacethinmintr@eircom.net
(Russell Wallace) writes:
|Does anyone know whether there's a reasonable guess as to the largest
|value for which the value of the busy-beaver function BB(N) is
|provable?
I don't know whether there is a reasonable guess or not. It depends on
how close and how reasonable you want, I suppose.
|Specifically: This would require a proof of non-halting for all the
|N-state Turing machines that don't halt; so presumably there's an N
|such that there's an N+1-state Turing machine whose non-halting cannot
|be proven.
If you define BB in terms of number of steps needed to halt, this is
essentially true. To determine which of them halt, knowing the maximum
number of steps any of them take to halt, just requires running each
of them at least that long. I've seen BB defined in terms of the number
of 1s left on the tape, however. It's not clear to me how to show your
statement is correct with that definition. We could be unable to tell
whether a machine is going to halt, but know that if it does, it will
erase its tape first, and thus eliminate it as a candidate. I bet it's
still true with that definition, though.
|And by "provable" I mean within the scope of known mathematics... is
|Zermelo-Fraenkel set theory the most powerful axiomatic system we
|have? Is there any prospect that something more powerful might be
|discovered in the future?
People usually, by the way, accept the axiom of choice (AC), and ZF
is taken not to include AC. In this case, though, the distinction
between ZF and ZF+AC=ZFC is irrelevant; ZF can prove the halting
and nonhalting of exactly the same Turing machines as ZFC can.
There are stronger systems that set theorists like, more or less.
Some of their favorite additional axioms are known as "higher axioms
of infinity", that appear to say, essentially, that some very big
kind of set exists.
For example, the measurable cardinal axiom (MC) says that there exists
an uncountable set M and a family F of subsets having the following
properties. M is in F. If S is in F and S is a subset of T, then T is
also in F. If G is a family of subsets of M disjoint from F, and the
cardinality of G is less than the cardinality of M, then the union of
the members of G is also not in F. For each m in M, the set {m} is not
in F. There's a sense in which such a set would have to be really huge.
It's impossible to prove in ZFC that such a set exists, of course.
If a set theorist proves that if MC is true, then some result in set
theory is true, that is considered basically adequate to establish that
the result is true, although I believe it is still customary to state
the result in a form which lets the reader know that MC was assumed.
There is a "ladder" of higher axioms of infinity of varying strengths,
some weaker than MC and some stronger than MC.
It's possible that ZF+MC or something like that could prove the value
of BB(n) for some n for which ZF could not. Since the consistency of
ZF is a theorem of ZF+MC (and by Goedel's second incompleteness theorem,
is a theorem of ZF only if ZF is inconsistent), there do exist Turing
machines that can be proven not to halt in ZF+MC, but not in ZF. I would
guess that the maximum n for which the value of BB(n) is a theorem of
ZF+MC is not very much larger than that for ZF. Especially, though, I
doubt anybody reading this has a refined enough idea of the difference
between ZF, ZF+MC, and so on for it to be very relevant to what _we_
have to say.
Suppose for example you decided to try what Tim Chow mentioned, and
write a Turing machine program that halts if and only if ZF is inconsistent.
Writing one that halted if and only if ZF+MC is inconsistent would take
more effort, and the resulting machine might be somewhat longer. But it
would only increase it somewhat. There are other, stronger axioms than
MC that might not even be as complicated. Once you had crammed it into
the smallest number of states you could, I don't know very well how long
the result would be.
This could provide you with decades of entertainment, if you really liked
doing it. You would want to investigate one of Harvey Friedman's research
programs, where he has been trying to produce examples of mathematical
statements that are as close to "ordinary, normal" mathematics, but which
need strong axioms of infinity to prove. Writing a program that searches
for proofs of 1=0 in ZF (on a Turing machine!) would be fairly tedious.
You need not just the axioms, but the deductive rules of first-order logic.
But his examples come much closer to being ordinary "combinatorial"
questions. The shortest program we could write, which doesn't halt, but
can't be proven not to halt in ZF, would probably have to be based on
something cute, more on the lines of what he's doing.
It is difficult to get "nice" statements independent of ZF that can be
shown to be equivalent to the non-halting of a Turing machine, but one
of his goals is to bring his statements down to as elementary a level
as he can.
|I imagine the actual value of N isn't known, but has anyone made an
|informed guess as to whether it might be 10, 20, 50 or so?
I don't know how informed you would say I am. I did a PhD in number
theory, and have had an interest in mathematical logic for a long time.
My main weakness in this game, I think, is just not being very familiar
with how many states Turing machines need to do various things.
My gut reaction is that it would be somewhat amazing if the value of BB(50)
were provable in ZF, even using the strongest axiom of infinity that is
consistent with ZF. (If an axiom X is inconsistent with ZF, then ZF+X
proves anything. If X is consistent with ZF, then even if it is incorrect,
the values of BB that can be proven in ZF+X are correct.) I would lean
toward the value of BB(20) also being unprovable. I'm not so sure about
BB(10).
It's interesting to introspect on this. The difficulty, in more than one
respect, is that our ability to exhaustively search is limited. So when we
ask ourselves what the ultimate extreme cases are, we are left with loose
guesses that are hard to justify.
On the one hand, we can only search for proofs so far:
There's a lot of stuff that we can prove more or less straightforwardly.
Then there are some very simple, very hard problems. The fact that we have
not succeeded yet doesn't give us a very good idea of how likely it is that
a proof exists. For instance, since ancient Greek times it's been unknown
whether there is an odd perfect number, i.e. a positive odd integer n such
that the sum of the positive integers dividing n evenly is 2n. I betcha you
could find a slick way of "cram-coding" a crude search for an odd perfect
number into not-so-large a Turing machine. Don't bother with binary
calculations-- just represent the numbers with tallies on the tape,
and so on. We think there aren't any, which would mean the machine runs
indefinitely. We even think we could, someday, prove that there aren't
any. But that's just a kind of impression. Until and unless the problem
is essentially solved (reduced to a bounded number of cases), there's
unlikely to be any guarantee that it can be proven in ZF.
If that one topples, then there still is the Goldbach conjecture, that
each even integer >2 is the sum of two primes-- probably also possible
to cram-code into something modest in length.
I once read an author who opined (pulling a conjecture out of thin air,
I suppose) that whether there exists an n>0 such that the integer part
of 10^n*pi is a perfect square is probably independent of ZF. I'm not so
sure I agree. I don't think it's the kind of problem that people would
want to work on.
On individual conjectures of "ordinary" mathematics, unlike such things
as the consistency of ZF, my impression (hard to justify in any way)
is that it's somewhat unlikely that they really lack a proof in ZF. It
could easily turn out to be stupendously hard for us to find one, even
if there was one.
Balancing this on the other hand, though, we only search through the
possible Turing machines so far:
The Turing machines with 20 states are a vast sea of possibilities. When
we set out to write code, we ordinarily are making some minimal effort at
intelligibility. We are not ordinarily exposed to genuinely "random"
code. We are even less likely to see the kind of code that, out of this
huge sea of possibilities, is least amenable to rigorous analysis.
The best available candidates for BB(6) and BB(7) were, as I recall,
considered somewhat hard to understand.
My intuition is that it doesn't need to permit many more than 6 or 7
states before one starts getting a few very "arbitrary" machines that
run forever, but for which there is nothing that one would call an
"explanation" why they do. I also suspect we won't ever know exactly
how many states it takes.
What I think is maybe more cool, though, is the thought that there are
(I would guess) small machines that can be proven not to halt, but only
with astronomically long proofs.
Keith Ramsay
- Next message: Arturo Magidin: "Re: Sylow problem"
- Previous message: KRamsay: "Re: Largest provable BB(N)?"
- Maybe in reply to: KRamsay: "Re: Largest provable BB(N)?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
