Catch-Em-Turing: Difference between revisions
No edit summary |
|||
| Line 67: | Line 67: | ||
Shift Overflow Counter Searching | Shift Overflow Counter Searching | ||
|- | |- | ||
|CET(4) | | CET(4) ||><math>10\uparrow\uparrow14</math>|| Agent 1: {{TM|0LB1LB_1LC1RB_0RD0LC_1RA0LD|non_halt}} | ||
||><math>10\uparrow\uparrow14</math> | |||
||Agent 1: {{TM|0LB1LB_1LC1RB_0RD0LC_1RA0LD|non_halt}} | |||
Agent 2: {{TM|1LB1LC_1RC0RA_1RA0RD_1RB0LA|non_halt}} | Agent 2: {{TM|1LB1LC_1RC0RA_1RA0RD_1RB0LA|non_halt}} | ||
||[[User:Axolotldailyweek|Axolotldailyweek]] | || [[User:Axolotldailyweek|Axolotldailyweek]] | ||
AI Searching via Possible Shift Overflow Counter Searching | AI Searching via Possible Shift Overflow Counter Searching | ||
||} | ||} | ||
Revision as of 01:25, 14 November 2026
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[1] 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: |
NathFR76
Brute Force Research | |||||||||||||||||||||||||||||||||
| CET(2) | 97 | Agent 1: 1LB0LB_1RB0LA (bbch)
Agent 2: |
NathFR76
Brute Force Research | |||||||||||||||||||||||||||||||||
| CET(3) | > | Agent 1: 1LB---_1LC1RB_0RB0LC (bbch)
Agent 2: |
roromachine14
Shift Overflow Counter Searching | |||||||||||||||||||||||||||||||||
| CET(4) | > | Agent 1: 0LB1LB_1LC1RB_0RD0LC_1RA0LD (bbch)
Agent 2: |
Axolotldailyweek
AI Searching via Possible Shift Overflow Counter Searching |
}
For 3 symbols
Notes:
ExtensionA 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:
At each step:
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 ChampionsThis is the MCET(n) table.
For 3 symbols
Notes:
Computational complexity and finite search spaceFor fixed values of n and k, the number of possible CET and MCET transition tables is finite. Each transition is determined by three choices:
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:
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:
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. References |
- ↑ In forum-general: Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post https://discord.com/channels/960643023006490684/1377330731222564904