Catch-Em-Turing - Revision history

Polygon: Added references section

2026-11-04T20:07:03Z

Added references section

← Older revision		Revision as of 20:07, 4 November 2026
Line 186:		Line 186:

	The finite search space makes exhaustive enumeration theoretically possible for every fixed pair (n,k), although the number of machines grows extremely rapidly.		The finite search space makes exhaustive enumeration theoretically possible for every fixed pair (n,k), although the number of machines grows extremely rapidly.

			== References ==

	[[Category:Functions]]		[[Category:Functions]]

NathFR76: i add some CET(n) champion and i corrected some text

2026-11-04T19:23:40Z

i add some CET(n) champion and i corrected some text

← Older revision		Revision as of 19:23, 4 November 2026
Line 2:		Line 2:
	https://discord.com/channels/960643023006490684/1377330731222564904</ref> on bbwiki discord.		https://discord.com/channels/960643023006490684/1377330731222564904</ref> on bbwiki discord.

	It is a ~~different angle~~ of Busy ~~beaver because~~ in ~~the~~ tape ~~you have not one like Busy beaver but two agent~~.		Catch-Em-Turing is a variant of the Busy Beaver problem in which two independent agents operate simultaneously on a shared tape, rather than a single Turing machine head.

	== Definition ==		== Definition ==
Line 84:		Line 84:
	Exhaustive Research		Exhaustive Research
	\|}		\|}
			'''Notes:'''

			* Exact values are indicated explicitly.
			* A value preceded by ≥ represents a proven lower bound, not necessarily the exact value of the corresponding function.
			* Each champion is a machine that has been verified to reach the listed number of steps before satisfying its halting condition.
			* The discoverer column identifies the person or research effort responsible for finding the machine.

	== Extension ==		== Extension ==
Line 89:		Line 95:
	A extension of CET(n) by [[User:NathFR76\|NathFR76]] for n agent is called Multi Catch-Em-Turing, or MCET(n).		A extension of CET(n) by [[User:NathFR76\|NathFR76]] for n agent is called Multi Catch-Em-Turing, or MCET(n).

	~~Agent~~ position ~~in configuration~~ is:		For each integer n ≥ 1, an MCET(n) machine consists of:
	* Agent 1 ~~starts~~ at position 0.
	* Agent 2 ~~starts~~ at position 2.		* Exactly n agents.
	* Agent 3 ~~starts~~ at position 4.		* Each agent has exactly n states.
	* ~~Agent 4 starts at position 6~~.		* Each agent has its own transition table.
	* ...		* All agents operate on the same infinite tape.
	* Agent i starts at position 2(i-1).		* All agents position is for i index the position is 2(i-1) (so: Agent 1 is at position 0, Agent 2 is at position 2, Agent 3 is at position 4, ...)
			* The tape alphabet is binary, containing the symbols 0 and 1.
			* All agents begin in their initial state, state 0.

			At each step:

	If multiple agents attempt to write to the same cell during the same step, the agent with the lowest index has priority.		* Every agent reads the symbol in its current tape cell from the tape configuration at the beginning of that step.
			* Each agent independently determines its transition.
			* All writes are applied simultaneously. If multiple agents attempt to write to the same cell during the same step, the agent with the lowest index has priority.
			* All agents then move one cell left or right and update their states simultaneously.

	~~And the halt condition is~~ when all n agents occupy the same ~~position~~ at the same time. ~~So for MCET(3), all 3 agents must collide on the same cell~~.		An MCET(n) machine halts only when all n agents occupy the same tape cell at the same time. There is no individual HALT state.

	== MCET Champions ==		== MCET Champions ==
Line 117:		Line 130:
	Like CET(2)		Like CET(2)
	\|-		\|-
	\| MCET(3) \|\| ≥ 12,~~733~~ \|\| Agent 1: ~~1RC0RB_1RC1LB_1LA0LC~~ Agent 2: ~~0RA0RC_0LC1LA_1LB0RB~~ Agent 3: ~~1LA0RC_1LB1LA_0LA1RB~~		\| MCET(3) \|\| ≥ 4,239,504 \|\| Agent 1 : 1LC1LA_1RA1RB_0RB0RA
	\|\| ~~[[User:NathFR76\|NathFR76]]~~		Agent 2 : 1LC1LB_1RB0RA_0LC0RA
			Agent 3 : 0LA1RB_0RC1RB_0RA1RC
			\|\| roromachine14
	Exhaustive Research		Exhaustive Research
	\|}		\|}
Line 135:		Line 150:
	Exhaustive Research		Exhaustive Research
	\|}		\|}
			'''Notes:'''
			* Exact values are indicated explicitly.
			* A value preceded by ≥ represents a proven lower bound, not necessarily the exact value of the corresponding function.
			* Each champion is a machine that has been verified to reach the listed number of steps before satisfying its halting condition.
			* The discoverer column identifies the person or research effort responsible for finding the machine.

			== Computational complexity and finite search space ==
			For fixed values of n and k, the number of possible CET and MCET transition tables is finite.

			Each transition is determined by three choices:

			* The symbol to write: k possibilities.
			* The movement direction: 2 possibilities (Left or Right).
			* The next state: n possibilities.

			Therefore, each state-symbol pair has exactly 2kn possible transitions.

			Each agent has n states and k possible input symbols, resulting in nk transition entries per agent.

			=== CET(n,k) ===
			A CET machine contains exactly two agents, giving a total of 2nk transition entries.

			Therefore, the total number of possible transition tables is:

			<math>\mathrm{CET}(n,k) = (2kn)^{2nk}</math>

			=== MCET(n,k) ===
			An MCET machine contains exactly n agents, giving a total of n^2k transition entries.

			Therefore, the total number of possible transition tables is:

			<math>\mathrm{MCET}(n,k) = (2kn)^{n^2k}</math>

			These counts assume labelled agents, deterministic transition tables, and no individual halting state. Machines are counted as distinct whenever at least one transition entry differs.

			The finite search space makes exhaustive enumeration theoretically possible for every fixed pair (n,k), although the number of machines grows extremely rapidly.

	[[Category:Functions]]		[[Category:Functions]]

NathFR76: Add The Catch Em Turing function

2026-11-04T13:50:06Z

Add The Catch Em Turing function

New page

The '''Catch-Em-Turing''' (CET) function is a variant of the Busy Beaver function proposed by [[User:NathFR76|NathFR76]] in the beginning of November 2026 in forum-general<ref>In forum-general: Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post
https://discord.com/channels/960643023006490684/1377330731222564904</ref> on bbwiki discord.

It is a different angle of Busy beaver because in the tape you have not one like Busy beaver but two agent.

== Definition ==

The Catch-Em-Turing system is a computational model inspired by [[Turing machine]] and the [[Busy Beaver]] problem.

For each integer n ≥ 1, a CET(n) machine consists of:
* Exactly 2 agents.
* Each agent has exactly n states.
* Each agent has its own transition table.
* Both agents execute their transitions simultaneously.

For Configuration:
* The tape is infinite in both directions.
* Initially, every cell contains the symbol 0.
* The agents are numbered Agent 1 and Agent 2.
* Agent 1 starts at position 0.
* Agent 2 starts at position 2.
* Both agents begin in their respective initial states.

At each step, each agent:
* Reads the symbol in the cell it currently occupies.
* Writes a symbol on that cell.
* Moves one cell to the left or right.
* Changes its state according to its transition table.
The agents perform these operations simultaneously.

A CET machine halts only when both agents occupy the same tape cell at the same time.
There is no individual HALT state. The collision between the two agents is the sole halting condition.
If the agents never collide, the machine does not halt.

The CET function is:

CET(n) = '''max number of steps before collision'''

CET(n) measures the maximum number of steps that two n-state agents can execute before meeting on the same tape cell.

== Growth rate ==

it's seem to see that CET(n) ≥ BB(n) by multiple agent with 2 different transition table before halt by collision.

And it's seem to see that for n states et k symbols, CET(n,k) ≥ BBB(n,k) if the champion is a translated cycler, which BBB is a reference to [[Beeping Busy Beaver]].

== CET Champions ==
This is the CET(n) table. for 2 symbols

{| class="wikitable"
|-
! Domain !! Max Steps !! Champions !! Discoverer
|-
| CET(1) || 1 || Agent 1: 1RA---
Agent 2: 1LA---
|| [[User:NathFR76|NathFR76]]
Brute Force Research
|-
| CET(2) || 97 || Agent 1: 1LB0LB_1RB0LA
Agent 2: 1RB1LA_1LA1RB
|| [[User:NathFR76|NathFR76]]
Brute Force Research
|-
| CET(3) || ≥ 3,746,207 || Agent 1: 1LC1LA_1LA0LC_1RC0LB
Agent 2: 0LB0RA_1RA1LB_0RA0LB
|| roromachine14
Exhaustive Research
|-
| CET(4) || ≥ 65,579,412 || Agent 1: 0LC0RA_0LD0RA_0LB0RA_0RA0RA
Agent 2: 1RB1LD_1RC1RB_1LC1LA_0RC0RD
|| roromachine14
Exhaustive Research
|}

For 3 symbols

{| class="wikitable"
|-
! Domain !! Max Steps !! Champions !! Discoverer
|-
| CET(2,3) || ≥ 20,350 || Agent 1: 2LB1LA2LA_2RB2LA0LB
Agent 2: 1RB0LB1RB_2LA2LA1RA
|| roromachine14
Exhaustive Research
|}

== Extension ==

A extension of CET(n) by [[User:NathFR76|NathFR76]] for n agent is called Multi Catch-Em-Turing, or MCET(n).

Agent position in configuration is:
* Agent 1 starts at position 0.
* Agent 2 starts at position 2.
* Agent 3 starts at position 4.
* Agent 4 starts at position 6.
* ...
* Agent i starts at position 2(i-1).

If multiple agents attempt to write to the same cell during the same step, the agent with the lowest index has priority.

And the halt condition is when all n agents occupy the same position at the same time. So for MCET(3), all 3 agents must collide on the same cell.

== MCET Champions ==
This is the MCET(n) table.

{| class="wikitable"
|-
! Domain !! Max Steps !! Champions !! Discoverer
|-
| MCET(1) || 1 || Agent 1: 1RA---
|| [[User:NathFR76|NathFR76]]
Is like BB(1)
|-
| MCET(2) || 97 || Agent 1: 1LB0LB_1RB0LA
Agent 2: 1RB1LA_1LA1RB
|| [[User:NathFR76|NathFR76]]
Like CET(2)
|-
| MCET(3) || ≥ 12,733 || Agent 1: 1RC0RB_1RC1LB_1LA0LC Agent 2: 0RA0RC_0LC1LA_1LB0RB Agent 3: 1LA0RC_1LB1LA_0LA1RB
|| [[User:NathFR76|NathFR76]]
Exhaustive Research
|}

For 3 symbols

{| class="wikitable"
|-
! Domain !! Max Steps !! Champions !! Discoverer
|-
| MCET(3,3) || ≥ 34,399 || Agent 1: 2RB2RC1LA_0LA2RA2RB_0LA2RA0LA
Agent 2: 2LC1RC0RA_1LA0RA1LA_0LA2RB

Agent 3: 2RB2LC2RC_0RC1RC2RB_1RC2RA2RC
|| [[User:NathFR76|NathFR76]]
Exhaustive Research
|}

[[Category:Functions]]