Bouncer: Difference between revisions
Jump to navigation
Jump to search
Added history section |
m →History: fixed name |
||
| (One intermediate revision by the same user not shown) | |||
| Line 22: | Line 22: | ||
== History == | == History == | ||
* In November 2022, a [[decider]] for bouncers is first created by Tony | * In November 2022, a [[decider]] for bouncers is first created by Tony Guilfoyle.<ref>https://github.com/TonyGuil/bbchallenge/tree/main/Bouncers</ref> | ||
* In May 2023, savask<ref>https://discord.com/channels/960643023006490684/1028745661459472484/1107257989716516954</ref> and lijil<ref>https://discord.com/channels/960643023006490684/1028745661459472484/1109496975545602098</ref> reproduce the decider. | * In May 2023, savask<ref>https://discord.com/channels/960643023006490684/1028745661459472484/1107257989716516954</ref> and lijil<ref>https://discord.com/channels/960643023006490684/1028745661459472484/1109496975545602098</ref> reproduce the decider. | ||
* In September 2023, meithecatte again optimizes and formally verifies the decider for bouncers.<ref>https://github.com/meithecatte/busycoq/blob/master/verify/Bouncers.v</ref> | * In September 2023, meithecatte again optimizes and formally verifies the decider for bouncers.<ref>https://github.com/meithecatte/busycoq/blob/master/verify/Bouncers.v</ref> | ||
| Line 30: | Line 30: | ||
[[Category:Zoology]] | [[Category:Zoology]] | ||
[[Category:Deciders]] | |||
Latest revision as of 18:56, 2 March 2026
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)2n+1 B0 (A0 B1)2n+2)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:
- Bn := A0 (B0 A1)2n+1 B0 (A0 B1)2n+2:
A 00(102n)>00 →[8n+8] A (102(n+1))>
In particular, we have
Bn:
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 (Bn)n≥0. Moreover, we have shown that there are 8n + 8 steps between the nth and the (n+1)st bounce.
History
- In November 2022, a decider for bouncers is first created by Tony Guilfoyle.[1]
- In May 2023, savask[2] and lijil[3] reproduce the decider.
- In September 2023, meithecatte again optimizes and formally verifies the decider for bouncers.[4]
- In May 2024, the decider is again reproduced by Tristan Stérin.[5] and then added to bbchallenge's deciders write-up, becoming Section 7.
References
- ↑ https://github.com/TonyGuil/bbchallenge/tree/main/Bouncers
- ↑ https://discord.com/channels/960643023006490684/1028745661459472484/1107257989716516954
- ↑ https://discord.com/channels/960643023006490684/1028745661459472484/1109496975545602098
- ↑ https://github.com/meithecatte/busycoq/blob/master/verify/Bouncers.v
- ↑ https://github.com/bbchallenge/bbchallenge-deciders/tree/main/decider-bouncers-reproduction