I’m asking ’cause I want to know
Is there an algorithm to decide whether the nth Busy Beaver number is even or odd? Or is this problem r.e.-complete? Or might it have intermediate Turing degree?
(For readers with social lives: “Busy Beaver” is not what you think. As discussed in this Wikipedia article and this old essay of mine, it’s the maximum number of 1’s that an n-state, 2-symbol Turing machine could write on an initially blank tape before halting.)
Follow
Comment #1 January 8th, 2006 at 5:14 pm
I’ve wondered this as well.
We can demonstrate via diagonalization that it’s impossible to have a machine reliably state ‘if this machine halts, then it does so in an even/odd number of steps’. My engineering brain puts two and two together and says that if we can’t find the busy beaver number, and if we can’t determine whether a given machine halts in an even or odd number of steps, then of course we can’t determine the combination of the two. That is, of course, non-rigorous claptrap, and should be ignored.
With a poor turing machine construction the answer is trivial. For example, one can generate an encoding which always takes an odd number of steps to halt. For diagonalization to work the machine needs to be able to decide for itself whether it wants to halt in an even or odd number of steps (the standard turing machine construction has this property, of course, I’m talking about general ‘turing machine constructions’ which almost always have equivalent properties due to being a mere constant factor off from each other, but the difference matters in this case).
Comment #2 January 8th, 2006 at 6:59 pm
For some reason I prefer the version of busy beaver that finds the longest running program which halts.
OEIS sequence.
I would conjecture most instances this version are odd, and more strongly have “few” prime factors.
So other than an oracle to the halting problem (by seeing if your program outruns the busy beaver), what other fun things can you do with this sequence?
Comment #3 January 8th, 2006 at 7:20 pm
“With a poor turing machine construction the answer is trivial. For example, one can generate an encoding which always takes an odd number of steps to halt.”
Yeah, I thought of that too. This is one of the few (interesting) problems I know of where Turing machine encoding details might actually be relevant…
Comment #4 January 8th, 2006 at 7:23 pm
“So other than an oracle to the halting problem (by seeing if your program outruns the busy beaver), what other fun things can you do with this sequence?”
Well, if you can solve the halting problem, you can compute the Busy Beaver sequence, so the two problems are equivalent (in terms of Turing degree).
Comment #5 January 8th, 2006 at 7:27 pm
“For some reason I prefer the version of busy beaver that finds the longest running program which halts.”
I do too. It’s much simpler conceptually (e.g. the proof that it outgrows any computable sequence is one or two sentences).
Of course, it’d be interesting to answer the odd/even question for either version. It’d especially be interesting if they had different answers…
Comment #6 January 9th, 2006 at 12:23 am
Note that with standard turing machines it’s possible to stamp out a 1 or not on the last turn, a part of the state machine which has no effect on the rest of the machine’s running. As a result, if the busy beaver with maximum runtime for n happens to stop on a 0, then it will be a tie between two very similar machines, one of which spits out an odd number of 1s and the other of which spits out an even number of 1s.
This is of course mixing and matching busy beaver concepts (maximum runtime vs. maximum number of 1s), but it does show something about the importance of encodings.
Comment #7 January 9th, 2006 at 1:41 pm
Bram points out that for some machine constructions the problem is trivially decidable. I’d like to offer a machine model for which the problem is trivially r.e.-complete.
Fix a standard enumeration E1 of input-free Turing machines; what if we specify another enumeration E2 by simply having all “n-state” E2 machines simulate the nth E1 machine, outputting 1 if it ever halts? If it does, BB(n) = 1 (mod 2) for BB defined relative to E2, otherwise it equals 0 (mod 2). Thus one can use
BB(n) mod 2 for E2 to solve the halting problem for E1.
If E2 seems unsatisfactory as an enumeration–e.g.,
i) BB(n) for E2 doesn’t have growth recursively related to BB(n) for other machine models),
ii) these E2 programs don’t output all strings;
iii) even if ii) is met, the descriptive complexity of strings relative to E2 should be close to descriptive complexity in E1;
I can suggest some fixes. (for i, use dovetailed simulations of E1 machines to generate large E2 outputs, while keeping the parity of 1’s of outputs chained to the nth machine’s halting behavior; for ii and iii, introduce a designated subset of ‘shorter-output’ E2 programs to generate all strings–with compression occuring–without affecting BB.)
What else is desired (other than that the enumeration be ‘non-contrived’)?
Comment #8 January 9th, 2006 at 2:50 pm
Scott’s/bram’s question is related to one I had that motivated my senior thesis this year. I was curious how inevitable it would be that an incomputable function like BB would have a ‘hard-core bit’–maybe not exactly the parity of its 1’s, but some decision-problem ‘digest’ of the function that’s also incomputable.
So, contrapositively, suppose a function f has no hard-core bits in the following sense: for any decision problem D(x) that is computable given the pair (x, f(x)), D(x) is computable given x alone.
Does it follow that f is computable?
See my page for the answer and generalizations.
PS Anyone know how to post a non-image file on blogger.com? I have an updated thesis I want to put up but don’t have home-accessible webspace. Thanks!
Comment #9 January 9th, 2006 at 2:54 pm
by ‘the parity of its 1s’, I meant ‘its parity’.
Comment #10 January 9th, 2006 at 3:21 pm
Andy: Thanks for the comments and for the pointer to your thesis! I’ll take a look.
As long as you’re writing research papers, I’d recommend getting some real webspace (not blogger.com) to put them on.
You’re at Berkeley now?
Comment #11 January 10th, 2006 at 1:12 am
Andy, why don’t you post your thesis at the Electronic Colloquium for Computational Complexity or on arxiv.org ? Then you can update as many times as you like.
Comment #12 January 11th, 2006 at 4:16 pm
Thanks for the advice, guys; I was nervous about posting on arxiv but will do so once I get my advisor’s signoff.
It occurs to me that, if you buy the basic scheme I described, you can have the n-state machines of E2 simulate, instead of the nth E1 machine, some fixed machine M on input n. That way, if M accepts a language of intermediate Turing-degree, the last bit of BB for E2 will have the same degree.
Does anyone have a favorite write-up of the Friedberg-Muchnik proof for building these degrees and/or further developments in computability? Should complexity theorists be versed in advanced computability work?
Comment #13 January 12th, 2006 at 3:20 am
Hi Andy,
“Does anyone have a favorite write-up of the Friedberg-Muchnik proof for building these degrees and/or further developments in computability?”
The book Gems of Theoretical Computer Science has a proof of the Friedberg-Muchnik Theorem that I was eventually able to understand. Also, Richard Shore has a nice survey of more recent work. If you want to go deeper than that, you’re on your own, dude. 🙂
“Should complexity theorists be versed in advanced computability work?”
Sure, I guess! Ideally, they should also be versed in gardening, Lithuanian, and Mayan archaeology. 🙂
(Seriously: Any area of math can give you useful tools for complexity, and many of the basic notions of complexity, like diagonalization and oracles, come directly from computability. On the other hand, I suspect that most complexity theorists working today never learned computability beyond the undergrad level.)