Catch-Em-Turing

The Catch-Em-Turing (CET) function is a variant of the Busy Beaver function proposed by NathFR76 in the beginning of November 2026 in forum-general on bbwiki discord.

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

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

Domain	Max Steps	Champions	Discoverer
CET(1)	1	Agent 1: 1RA--- (bbch) Agent 2: 1LA--- (bbch)	NathFR76 Brute Force Research
CET(2)	97	Agent 1: 1LB0LB_1RB0LA (bbch) Agent 2: 1RB1LA_1LA1RB (bbch)	NathFR76 Brute Force Research
CET(3)	> $10^{10^{2.8244\times 10^{13}}}$	Agent 1: 1LB---_1LC1RB_0RB0LC (bbch) Agent 2: 1RB0LB_0RC0LA_1LB1RC (bbch)	roromachine14 Shift Overflow Counter Searching

For 3 symbols

Domain	Max Steps	Champions	Discoverer
CET(2,3)	≥ 1,528,952,999	Agent 1: 1RB0RA2LB_2LA2RB1LB (bbch) Agent 2: 2RB0RA2RB_2LB1RA0RB (bbch)	roromachine14 TNF 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

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

For each integer n ≥ 1, an MCET(n) machine consists of:

• Exactly n agents.
• Each agent has exactly n states.
• Each agent has its own transition table.
• All agents operate on the same infinite tape.
• 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:

• 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.

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

This is the MCET(n) table.

Domain	Max Steps	Champions	Discoverer
MCET(1)	1	Agent 1: 1RA---	NathFR76 Is like BB(1)
MCET(2)	97	Agent 1: 1LB0LB_1RB0LA Agent 2: 1RB1LA_1LA1RB	NathFR76 Like CET(2)
MCET(3)	≥ 4,032,363,281	Agent 1 : 0LB1RB_0LC0RA_1RC0LC Agent 2 : 0LC1RC_0LA1LC_1RA1RB Agent 3 : 1RB0LC_1RC1RB_1LA1RC	NathFR76 Simulated Annealing Research

For 3 symbols

Domain	Max Steps	Champions	Discoverer
MCET(3,3)	≥ 769,546,012	Agent 1: 1LB2RC1LA_0LC2LB2RC_2RA2RC0LA Agent 2: 1LC0RC0LA_2LB1LA0RB_2RC2RC0RB Agent 3: 2LC1LA2LC_1LA1RC2RA_0RA0RC0RC	67 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:

$\mathrm{C}\mathrm{E}\mathrm{T}(n,k)=(2kn{)}^{2nk}$

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:

$\mathrm{M}\mathrm{C}\mathrm{E}\mathrm{T}(n,k)=(2kn{)}^{n^{2}k}$

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.

CET(3) Champion Analysis

Star used Claude to verify the runtime of this machine, obtaining approximately <math>4.39\times10^{414}</math>$4.39\times 10^{414}$ steps.

Machine:

• Agent 1: 0LB---_1LC1RB_0RB0LC
• Agent 2: 0RB0LC_1RC1LB_1LB1RA

The machine halts after exactly $\frac{2^{1379}+16483}{3}$ > $4.39\times 10^{414}$ steps.

Analysis

The machine uses an exponential counter mechanism combined with a moving agent acting as a clock. The counter undergoes successive transformations, resulting in an extraordinarily large runtime.

sheep independently derived the counter rules and the exact step-count formula. Claude's accelerated simulation reportedly reproduced the result and matched the intermediate configurations of sheep's analysis.

The transition marked --- is never reached and does not affect the computation.

sheep's analysis

Agent 1:

B>1^n --(n)--> 1^n 1^n<C --(n)--> <C 0^n 0<C 1^n 0 --(2n + 2)--> 0<C 0^n 1 0<C 0^n --(2^(n + 2) - 2n - 4)--> 0<C 1^n

Agent 2:

0 b>$ --(8n)--> 1^2n 0 b>$ 1 a>1 $ --(8n)--> 1^2n 1 a>1 $

Simulation:

step 46: $<C 0^10 1^4 0 b>$ --(4072)--> $<C 1^1032 0 b>$ --(sim 8)--> $ 1^7 B>1^1027 0 b>$ = $ 1^7 B>1^1368 1^-341 0 b>$ --(1368)--> $ 1^1375 B>1 0 b>$ --(sim 13)--> $ 1^1365<C 0^10 1^4 0 b>$ --(1360)--> $ 1^5<C 0^1370 1^344 0 b>$ --(sim 5)--> $<C 0^1375 1^345 1 a>1 $ --(2^1377 - 2754)--> $<C 1^(2^1375 + 1031) b>011 $ --(sim 2)--> $ 1 B>1^(2^1375 + 1031) 1 a>1 $ = $ 1 B>1^((2^1377 + 4120)/3) 1^-((2^1375 + 1027)/3) 1 a>1 $ --((2^1377 + 4120)/3)--> $ 1^((2^1377 + 4123)/3) B>1 1 a>1 $ --(sim 1)--> $ 1^((2^1377 + 4126)/3) B>1<C $ (HALT)

Final step count:

$\frac{2^{1379}+16483}{3}$

Note: sheep's analysis is from Discord.