Bouncer - Revision history

Polygon: /* History */ fixed name

2026-03-02T18:56:49Z

History: fixed name

← Older revision		Revision as of 18:56, 2 March 2026
Line 22:		Line 22:

	== History ==		== History ==
	* In November 2022, a [[decider]] for bouncers is first created by Tony ~~Guilyfoyle~~.<ref>https://github.com/TonyGuil/bbchallenge/tree/main/Bouncers</ref>		* 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>

Polygon: Added Category:Deciders (consistency with page for Cyclers)

2026-03-02T18:16:49Z

Added Category:Deciders (consistency with page for Cyclers)

← Older revision		Revision as of 18:16, 2 March 2026
Line 30:		Line 30:

	[[Category:Zoology]]		[[Category:Zoology]]
			[[Category:Deciders]]

Polygon: Added history section

2026-03-02T16:25:03Z

Added history section

← Older revision		Revision as of 16:25, 2 March 2026
Line 21:		Line 21:
	In particular, we have<blockquote>'''B'''<sub>n</sub>: <code>A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup></code>,</blockquote>which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''<sub>n</sub>)<sup>n≥0</sup>. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.		In particular, we have<blockquote>'''B'''<sub>n</sub>: <code>A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup></code>,</blockquote>which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''<sub>n</sub>)<sup>n≥0</sup>. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.

	== ~~See also~~ ==		== History ==
			* In November 2022, a [[decider]] for bouncers is first created by Tony Guilyfoyle.<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 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 May 2024, the decider is again reproduced by [[User:Cosmo\|Tristan Stérin]].<ref>https://github.com/bbchallenge/bbchallenge-deciders/tree/main/decider-bouncers-reproduction</ref> and then added to bbchallenge's deciders write-up, becoming [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7].

	* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 7] of bbchallenge's deciders write-up.		== References ==

	[[Category:Zoology]]		[[Category:Zoology]]

Polygon: Used Template:Stub

2025-08-10T22:29:52Z

Used Template:Stub

← Older revision		Revision as of 22:29, 10 August 2025
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.]]{{Stub}}
	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.		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.

Line 26:		Line 26:

	[[Category:Zoology]]		[[Category:Zoology]]
	~~[[Category:Stub]]~~

Sligocki: link to transcript (doesn't exist yet) since it's a jargony term

2024-11-13T17:15:38Z

link to transcript (doesn't exist yet) since it's a jargony term

← Older revision		Revision as of 17:15, 13 November 2024
Line 6:		Line 6:

	=== Analysis ===		=== Analysis ===
	'''Transcript''': (A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>)<sup>n≥0</sup>.		'''[[Transcript]]''': (A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>)<sup>n≥0</sup>.

	The derivation of this transcript is as follows.		The derivation of this transcript is as follows.

Icy: Brevity

2024-11-13T15:03:23Z

Brevity

← Older revision		Revision as of 15:03, 13 November 2024
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 fashion, 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 [[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 ==		== Example ==

Icy: /* Example */ Added transcript

2024-11-13T15:00:45Z

Example: Added transcript

← Older revision		Revision as of 15:00, 13 November 2024
Line 6:		Line 6:

	=== Analysis ===		=== Analysis ===
			'''Transcript''': (A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>)<sup>n≥0</sup>.

			The derivation of this transcript is as follows.

	'''Shift rules:'''		'''Shift rules:'''

Line 15:		Line 19:
	* '''B'''<sub>n</sub> := A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>: <code>A 00(10<sup>2n</sup>)>00 →[8n+8] A (10<sup>2(n+1)</sup>)></code>		* '''B'''<sub>n</sub> := A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>: <code>A 00(10<sup>2n</sup>)>00 →[8n+8] A (10<sup>2(n+1)</sup>)></code>

	In particular, we have		In particular, we have<blockquote>'''B'''<sub>n</sub>: <code>A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup></code>,</blockquote>which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''<sub>n</sub>)<sup>n≥0</sup>. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.

	'''B'''<sub>n</sub>: <code>A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup></code>,

	which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''<sub>n</sub>)<sup>n≥0</sup>~~. This shows that <code>1RB0LB_1LA0RA</code> is a bouncer~~. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.

	== See also ==		== See also ==

Icy: /* Example */

2024-11-13T14:23:31Z

Example

← Older revision		Revision as of 14:23, 13 November 2024
Line 8:		Line 8:
	'''Shift rules:'''		'''Shift rules:'''

	* <code>~~B0 A1:~~ B 10< →[2] B <01</code>		* B0 A1: <code>B 10< →[2] B <01</code>,
	* <code>~~A0 B1:~~ A >10 →[2] A 01></code>		* A0 B1: <code>A >10 →[2] A 01></code>.

	'''Bounce rule:'''		'''Bounce rule:'''

	* ~~<code>~~'''B'''<sub>n</sub> := A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>: A 00(10<sup>2n</sup>)>00 →[8n+8] A (10<sup>2(n+1)</sup>)></code>		* '''B'''<sub>n</sub> := A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>: <code>A 00(10<sup>2n</sup>)>00 →[8n+8] A (10<sup>2(n+1)</sup>)></code>

	In particular,		In particular, we have
	'''B'''<sub>n</sub>: A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup>
	~~thus proving~~ by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is ~~<code>~~('''B'''<sub>n</sub>)<sup>n≥0</sup>~~</code>, which~~ shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.		'''B'''<sub>n</sub>: <code>A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup></code>,

			which by induction proves that the transcript of <code>1RB0LB_1LA0RA</code> on the all-zeros tape is ('''B'''<sub>n</sub>)<sup>n≥0</sup>. This shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.

	== See also ==		== See also ==

Icy: /* Example */ forgot head

2024-11-13T14:18:45Z

Example: forgot head

← Older revision		Revision as of 14:18, 13 November 2024
Line 16:		Line 16:

	In particular,		In particular,
	'''B'''<sub>n</sub>: A 0<sup>∞</sup>(10<sup>2n</sup>)0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)0<sup>∞</sup>		'''B'''<sub>n</sub>: A 0<sup>∞</sup>(10<sup>2n</sup>)>0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)>0<sup>∞</sup>
	thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''<sub>n</sub>)<sup>n≥0</sup></code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.		thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''<sub>n</sub>)<sup>n≥0</sup></code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.

Icy: /* Analysis */ Added number of steps

2024-11-13T14:17:04Z

Analysis: Added number of steps

← Older revision		Revision as of 14:17, 13 November 2024
Line 13:		Line 13:
	'''Bounce rule:'''		'''Bounce rule:'''

	* <code>'''B'''<sub>n</sub> := A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>: A 00(10<sup>2n</sup>)>00 → A (10<sup>2(n+1)</sup>)></code>		* <code>'''B'''<sub>n</sub> := A0 (B0 A1)<sup>2n+1</sup> B0 (A0 B1)<sup>2n+2</sup>: A 00(10<sup>2n</sup>)>00 →[8n+8] A (10<sup>2(n+1)</sup>)></code>

	In particular,		In particular,
	'''B'''<sub>n</sub>: A 0<sup>∞</sup>(10<sup>2n</sup>)0<sup>∞</sup> → 0<sup>∞</sup>(10<sup>2(n+1)</sup>)0<sup>∞</sup>		'''B'''<sub>n</sub>: A 0<sup>∞</sup>(10<sup>2n</sup>)0<sup>∞</sup> →[8n+8] 0<sup>∞</sup>(10<sup>2(n+1)</sup>)0<sup>∞</sup>
	thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''<sub>n</sub>)<sup>n≥0</sup></code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer.		thus proving by induction that the transcript of <code>1RB0LB_1LA0RA</code> on the all zeros tape is <code>('''B'''<sub>n</sub>)<sup>n≥0</sup></code>, which shows that <code>1RB0LB_1LA0RA</code> is a bouncer. Moreover, we have shown that there are 8''n'' + 8 steps between the ''n''<sup>th</sup> and the (''n''+1)<sup>st</sup> bounce.

	== See also ==		== See also ==