Bouncer: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} with 2 states, the smallest number of states for which a bouncer can appear.]] | [[File:1RB0LB 1LA0RA.png|alt=1RB0LB_1LA0RA|thumb|A close-up of the bouncer {{TM|1RB0LB_1LA0RA}} 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 fasion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]]. | 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 fasion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of [[Non-halting Turing machine|non-halting Turing machines]]. | ||
See [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up. | |||
[[Category:Zoology]] | [[Category:Zoology]] | ||
[[Category:Stub]] | [[Category:Stub]] | ||
Revision as of 20:27, 11 November 2024
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 fasion, growing the tape along one or both edges with each iteration. A bouncer is a possible classification of non-halting Turing machines.
See Section 7 of bbchallenge's deciders write-up.