User:Salpynx/BB thoughts

• Weak: A bb(n+1, m) program cannot possibly be encoded for a (s, m) UTM by a (n-s, m) Turing machine. (definitely true)
• Strong: A bb(n, m) program cannot possibly be encoded for a (s, m) UTM by a (n-s, m) Turing machine. (possibly true?)

(n > s)

Trivially, a full description cannot be encoded directly, but this is stating that a (n-s, m) cannot possibly generate the bb(n, m) source code by any means of compression.

At some (s, m) we could create a UTM which reads and executes efficiently encoded descriptions of busy beaver candidates as UID strings -- a winning bb(n) UID representation cannot be generated by any (n-s, m) Turing machine.

Example

(with unrealistically low and made up numbers): If 174440041 represented the source code for a bb(n, m) winner that could be run on a (s, m) Turing machine, that number, 174440041, could not be produced by any means from a (n-s, m) Turing machine.

Reason

If it could, we could combine the two machines to produce an (n, m) Machine which contains the (n-s, m) code generator, and the (s, m) UTM, which would be able to run the bb(n+1) program. This would mean bb(n) == bb(n+1), which is inconsistent. (bb should be strictly increasing; bb(n+1) should at least be able to use the one additional state to add an extra 1 to the tape after bb(n) would have halted, assuming there is always an adjacent 0 when the program halts. Is that guaranteed? If not, there still seems like there should be a reason

In the second case, the (n, m) combined source generator and UTM runs the bb(n, m) winner, which would be itself. bbn_generator(n-s, m) + UTM(s, m) = bb(n, m)

• TODO: investigate why this isn't possible. On the surface it seems like it could work somehow, because bb(n,m) == bb(n, m) is not a contradiction. It seems unlikely because a fraction of itself (n-s states) would have to encode all of itself (n states).

Could we reduce this further? What is the cutoff? Should we expect a bb(s, m) UTM be able to run a bb(n-1, m) winner that can be generated by a (n-s, m) machine? That would produce a bb(n-1) winner that can be represented as a (n, m) machine. We know that is possible, we can create those trivially by adding a noop state to bb(n-1). Should we expect a (n-s, m) generator + (s, m) UTM to BE bb(n-1) with a single extra state?

(if we need a default value of m, use m = 2, but this will apply for number of symbols m.)

Why is this potentially useful?

This provides a way to eliminate high n BB candidates from being BB winners. Demonstrating its representation for an (s, m) UTM can be generated by an (n-s, m) TM proves it cannot be a winner, regardless of how the program actually behaves.