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 non-halting 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.

Example

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

Analysis

Transcript: (A0 (B0 A1)²ⁿ⁺¹ B0 (A0 B1)²ⁿ⁺²)^n≥0.

The derivation of this transcript is as follows.

Shift rules:

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

Bounce rule:

• B_n := A0 (B0 A1)²ⁿ⁺¹ B0 (A0 B1)²ⁿ⁺²: A 00(102n)>00 →[8n+8] A (102(n+1))>

In particular, we have

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

which by induction proves that the transcript of 1RB0LB_1LA0RA on the all-zeros tape is (B_n)^n≥0. 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.