Bouncer

A close-up of the bouncer 1RB0LB_1LA0RA (bbch) with 2 states, the smallest number of states for which a bouncer can appear.

A bouncer is a Turing machine whose tape head, roughly speaking, alternates back and forth between the two edges of the tape in a linear fashion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of non-halting Turing machines.

Example

1RB0LB_1LA0RA (bbch) is an example of a bouncer, and its spacetime diagram is shown in the picture on the right.

Analysis

Shift rules:

• B0 A1: B 10< →[2] B <01
• A0 B1: A >10 →[2] A 01>

Bounce rule:

• Bn := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2: A 00(102n)>00 →[8n+8] A (102(n+1))>

In particular,

Bn: A 0∞(102n)>0∞ →[8n+8] 0∞(102(n+1))>0∞

thus proving by induction that the transcript of 1RB0LB_1LA0RA on the all zeros tape is (Bn)n≥0, which shows that 1RB0LB_1LA0RA is a bouncer. Moreover, we have shown that there are 8n + 8 steps between the n^th and the (n+1)^st bounce.

See also

• Section 7 of bbchallenge's deciders write-up.