A bound on the shift function in terms of the Busy Beaver function
Bryant A. Julstrom · ACM SIGACT News · 1992
The Busy Beaver function Σ( n ) is the maximum number of 1's a halting n-state Turing machine may leave on an initially blank tape. The shift function S ( n ) is the maximum number of moves such a machine may make before it halts. This paper shows that S ( n ) < Σ(20n), then uses this result to prove that both Σ( n and S ( n ) are non-computable and their non-computability is equivalent to the undecidability of the halting problem. Demonstrations that several other functions are also non-computable apply a construction used in the proof of the bound on S ( n ).