Beeping Busy Beavers and twin prime conjecture

[Andrey Akinshin]

Hello everyone!

Recently I came up with an idea of how to use Beeping Busy Beavers to show that the twin prime conjecture could be proven or disproven. The corresponding blog post could be found here: https://aakinshin.net/posts/bbb-twin-primes/

I'm not completely sure if this idea is actually novel and correct, so I would appreciate any feedback on it.

Andrey.

[Nicholas Drozd]

That's a nice explanation. If you haven't heard of it, I suggest looking up the arithmetic hierarchy, which separates problems based on difficulty. Goldbach's conjecture is an example of a "sigma 1" problem, requiring a single instance of something to be found from an infinite search space. The twin prime conjecture is an example of a "sigma 2" problem, requiring, as you say, an infinite number of solutions.

BB is complete for sigma 1 and BBB is complete for sigma 2. Similarly, BB is equivalent to the halting problem, while BBB is equivalent to the quasihalting problem.

It's interesting that the algorithm for solving GC requires one value for BB, but the algorithm for solving TPC requires a value for BBB and also a value for BB. What's the deal with this extra hanging chad?

For GC, we run the program for BB(n) steps, then see if the program has halted or not. This is computable, so no further invocations of magic functions are required. This is important, so I'll say it again: checking whether the program is currently halted or not is computable. (In fact, it's very easy.)

But with TPC, the situation is different. We run the program for BBB(n) steps, and then what? We want to know if the program has quasihalted or not. Has it? The trick here is that checking whether a program is currently quasihalted or not is not computable in general. And so the extra BB invocation is required to verify whether the program has quasihalted or not.

Another way to put it is that haltedness -- whether a program is currently halted -- is decidable, while quasihaltedness is not. It's not decidable, so it requires an invocation of BB (equivalent to the halting problem) to figure it out.

That's the general case. However, in many particular instances the extra invocation of BB is not required. This is because some quasihalting programs can indeed be proved to quasihalt, and this can even be easy to do. For example, there is a behavior known as "spinning out". This is where the machine is scanning a blank cell directly to the left (or right) of all the marks on the tape, and the next state is the same as the current state, and the shift instruction is to the left (or right). It's obvious that a machine in such a configuration will get stuck in that same state forever, and therefore the machine provably quasihalts.

Every known BBB champion exhibits this behavior. But there must be BBB champions that do not spin out, because otherwise BBB would be sigma 1, which it isn't. What's the first n such that the BBB(n) machine doesn't spin out?

The fact that all the known BBB machines spin out is somewhat suspicious. It could be that we have the values we have because spinning out is an easy behavior to detect. More complicated behaviors are harder to detect, and consequently we haven't detected them. (That's not totally true; Shawn managed to find a few long-running non-spin-out quasihalters.)

This kind of reasoning can be generalized to argue that our whole picture of long-running programs is probably wrong. As far as anyone knows, the longest-running programs implement Collatz-like functions. But any machines that have been found are of a findable nature, and therefore trivial in the grand scheme of things. What can be said about the programs that we can't find?

[Bruce Smith]

I think your argument does not show that TPC could be proven or disproven, since your argument assumes BBB(n1) is known. But knowing that value *requires* first proving or disproving TPC (which is what your argument actually shows).

- Bruce Smith

[Shawn Ligocki]

Bruce, I think your statement and Andrey's statement are both valid ways to look at this. I interpret Andrey's as "If we somehow found some TM wizardry to prove BBB(n1) we could use that to prove the TPC". And I interpret your statement to be that one small piece of proving BBB(n1) is showing that this one very specific TM quasihalts or not. And that can only be done by proving TPC. I think these are both reasonable points of view.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/a7dc49ea-b0f0-4927-8765-271f792fff17n%40googlegroups.com.

[Bruce Smith]

> I think these are both reasonable points of view.

They are. I interpreted his post as making a stronger statement -- "what we know right now is sufficient to rule out the possibility that TPC is neither provable nor refutable, and this blog post does that". And that is not correct. Since he asked for feedback on whether that is correct, I provided it. That is not meant to imply the blog post is not interesting!

- Bruce