BusyBeaverWiki - User contributions [en]

Catch-Em-Turing

2026-11-04T19:23:40Z

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

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.

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

{| 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
|}
'''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 [[User:NathFR76|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.

{| 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) || ≥ 4,239,504 || Agent 1 : 1LC1LA_1RA1RB_0RB0RA
Agent 2 : 1LC1LB_1RB0RA_0LC0RA
Agent 3 : 0LA1RB_0RC1RB_0RA1RC
|| roromachine14
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
|}
'''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]]

Catch-Em-Turing

2026-11-04T13:50:06Z

NathFR76: Add The Catch Em Turing function

User:NathFR76

2026-11-04T09:39:09Z

NathFR76: i add a conjecture between CET(n,k) and BBB(n,k)

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 65,579,412
|
|
|-
!3-symbol
|≥ 20,350
|≥ 10^^6.74
|
|
|
|-
!4-symbol
|≥ <math>2 \times 10^{23}</math>
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 65,579,412

Agent 1: ((0, LEFT, 2), (0, RIGHT, 0), (0, LEFT, 3), (0, RIGHT, 0), (0, LEFT, 1), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3))

CET(2,3) ≥ 20,350

Agent 1: ((2, LEFT, 1), (1, LEFT, 0), (2, LEFT, 0), (2, RIGHT, 1), (2, LEFT, 0), (0, LEFT, 1))

Agent 2: ((1, RIGHT, 1), (0, LEFT, 1), (1, RIGHT, 1), (2, LEFT, 0), (2, LEFT, 0), (1, RIGHT, 0))

CET(2,4) ≥ <math>2 \times 10^{23}</math> (By BBB(2,4) champion translated cyclic)

CET(3,3) ≥ 10^^6.74 (By BBB(3,3) champion translated cyclic)

Conjecture: CET(n,k) ≥ BBB(n,k) if BBB(n,k) champion is a translated cyclic

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 65,579,412 by '''Roromachine14'''

User:NathFR76

2026-11-03T18:16:36Z

NathFR76: New champion for CET(2,3)

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 65,579,412
|
|
|-
!3-symbol
|≥ 20,350
|≥ 10^^6.74
|
|
|
|-
!4-symbol
|≥ <math>2 \times 10^{23}</math>
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 65,579,412

Agent 1: ((0, LEFT, 2), (0, RIGHT, 0), (0, LEFT, 3), (0, RIGHT, 0), (0, LEFT, 1), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3))

CET(2,3) ≥ 20,350

Agent 1: ((2, LEFT, 1), (1, LEFT, 0), (2, LEFT, 0), (2, RIGHT, 1), (2, LEFT, 0), (0, LEFT, 1))

Agent 2: ((1, RIGHT, 1), (0, LEFT, 1), (1, RIGHT, 1), (2, LEFT, 0), (2, LEFT, 0), (1, RIGHT, 0))

CET(2,4) ≥ <math>2 \times 10^{23}</math> (By BBB(2,4) champion translated cycling)

CET(3,3) ≥ 10^^6.74 (By BBB(3,3) champion translated cycling)

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 65,579,412 by '''Roromachine14'''

User:NathFR76

2026-11-03T18:11:52Z

NathFR76: new champions for CET(4)

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 65,579,412
|
|
|-
!3-symbol
|≥ 8,786
|≥ 10^^6.74
|
|
|
|-
!4-symbol
|≥ <math>2 \times 10^{23}</math>
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 65,579,412

Agent 1: ((0, LEFT, 2), (0, RIGHT, 0), (0, LEFT, 3), (0, RIGHT, 0), (0, LEFT, 1), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3))

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

CET(2,4) ≥ <math>2 \times 10^{23}</math> (By BBB(2,4) champion translated cycling)

CET(3,3) ≥ 10^^6.74 (By BBB(3,3) champion translated cycling)

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 65,579,412 by '''Roromachine14'''

User:NathFR76

2026-11-03T17:45:54Z

NathFR76:

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 49,184,559
|
|
|-
!3-symbol
|≥ 8,786
|≥ 10^^6.74
|
|
|
|-
!4-symbol
|≥ <math>2 \times 10^{23}</math>
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 49,184,559

Agent 1: (0, LEFT, 1), (0, LEFT, 2), (0, LEFT, 3), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3)

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

CET(2,4) ≥<math>2 \times 10^{23}</math> (By BBB(2,4) champion translated cycling)

CET(3,3) ≥ 10^^6.74 (By BBB(3,3) champion translated cycling)

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 49,184,559 by '''Roromachine14'''

User:NathFR76

2026-11-03T17:45:21Z

NathFR76: i changed some incorrect values

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 49,184,559
|
|
|-
!3-symbol
|≥ 8,786
|≥ 10^^6.74
|
|
|
|-
!4-symbol
|≥ <math>2 \times 10^{23}</math>
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 49,184,559

Agent 1: (0, LEFT, 1), (0, LEFT, 2), (0, LEFT, 3), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3)

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

CET(2,4) ≥
{| class="wikitable"
|≥ <math>2 \times 10^{23}</math>
|}
(By BBB(2,4) champion translated cycling)

CET(3,3) ≥ 10^^6.74 (By BBB(3,3) champion translated cycling)

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 49,184,559 by '''Roromachine14'''

User:NathFR76

2026-11-03T17:40:40Z

NathFR76: i add detail

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 49,184,559
|
|
|-
!3-symbol
|≥ 8,786
|≥ 10^^6.87
|
|
|
|-
!4-symbol
|≥ 4.115*10^23
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 49,184,559

Agent 1: (0, LEFT, 1), (0, LEFT, 2), (0, LEFT, 3), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3)

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

CET(2,4) ≥ 4.115*10^23 (By BBB(2,4) champion translated cycling)

CET(3,3) ≥ 10^^6.87 (By BBB(3,3) champion translated cycling)

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 49,184,559 by '''Roromachine14'''

User:NathFR76

2026-11-03T17:39:31Z

NathFR76: i add some CET(n) champion

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 49,184,559
|
|
|-
!3-symbol
|≥ 8,786
|≥ 10^^6.87
|
|
|
|-
!4-symbol
|≥ 4.115*10^23
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 49,184,559

Agent 1: (0, LEFT, 1), (0, LEFT, 2), (0, LEFT, 3), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3)

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

CET(2,4) ≥ 4.115*10^23 (By BBB(2,4) champion translated cycling)

CET(3,3) ≥ 10^^6.87 (By BBB(3,3) champion translated cycling)

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 49,184,559 by '''Roromachine14'''

User:NathFR76

2026-11-03T15:44:20Z

NathFR76:

Hi! My name is Nathan.

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 49,184,559
|
|
|-
!3-symbol
|≥ 8,786
|
|
|
|
|-
!4-symbol
|
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 49,184,559

Agent 1: (0, LEFT, 1), (0, LEFT, 2), (0, LEFT, 3), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3)

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

=== Discovered Champions ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 49,184,559 by '''Roromachine14'''

User:NathFR76

2026-11-03T15:43:23Z

NathFR76: i add another busy beaver like function named Catch Em Turing (CET(n)), it's a busy beaver with 2 agent in tape

Hi! My name is Nathan.

And i made Thutus function

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
!n
!Value
!Champion Initiate Term
!Champion Rule
|-
|0
|= 0
|
|
|-
|1
|= 1
|L1
|L1 x1 -> x1
|-
|2
|= 1
|L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
|3
|= 4
|L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2)
|-
|4
|≥ 522
|L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 -> (x1 x1) x1 L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
|5
|≥ fω+1(2^^6/2)
|L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1 L3 x1 x2 -> x1 (x1 x2) L4 x1 x2 -> x2 (x2 x1) L5 x1 x2 x3 -> x3 x2 x1
|-
|...
|
|
|
|-
|15
|> fω2^^18-1(2)
|L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1 L3 x1 x2 -> x1 L4 x1 x2 -> x1 x2 x2 L5 x1 x2 x3 -> x1 x3 x2 L6 x1 x2 x3 -> x1 (x2 x3) L7 x1 -> x1 L8 x1 -> x1 L9 x1 -> x1 L10 x1 -> x1 L11 x1 -> x1 L12 x1 -> x1 L13 x1 -> x1 L14 x1 -> x1 L15 x1 -> x1
|}

== CET(n) & MCET(n) Busy Beaver variant ==
in the [https://discord.com/channels/960643023006490684/1377330731222564904 Forumforum-general] in Catch Em Turing (CET(n)) (Busy Beaver with 2 agent) post

i've made a Busy beaver like but we have not 1 agent like Busy Beaver classic but 2 agent, it's start when this 2 agent are spaced by 2 cell, Agent 1: position 0 and Agent 2: position 2, each agent has a transition table and the halting condition is when all 2 agent are in the same cell, the machine stop. This function call Catch-Em-Turing (CET(n)).

1.1. Definition

The Catch-Em-Turing system is a computational model inspired by Turing machines 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.

1.2. Tape and Initial 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.

1.3. Agent Operations

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.

1.4. Halting Condition: Collision

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.

1.5. The CET Function

[

<nowiki>CET(n)=\max{\text{number of steps before collision}}</nowiki>

]

The maximum is taken over all possible CET(n) machines that eventually halt by collision.

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

2.1. Multi Catch-Em-Turing (MCET)

A generalized version is called Multi Catch-Em-Turing, or MCET(n).

CET(n) always uses exactly two agents and n states , whereas MCET(n) uses n agents and n states.

2.2. Writing Conflicts MCET(n)

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

MCET(n) halts 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.

=== Actual bound values for CET(n,k) (n for states and k for symbol) ===
{| class="wikitable"
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|= 97
|≥ 3,746,207
|≥ 49,184,559
|
|
|-
!3-symbol
|≥ 8,786
|
|
|
|
|-
!4-symbol
|
|
|
|
|
|-
!5-symbol
|
|
|
|
|
|-
!6-symbol
|
|
|
|
|
|}

=== Transition Table for some champions ===
CET(2) = 97

Agent 1: (1, LEFT, 1), (0, LEFT, 1), (1, RIGHT, 1), (0, LEFT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 0), (1, LEFT, 0), (1, RIGHT, 1)

CET(3) ≥ 3,746,207

Agent 1: ((1, LEFT, 2), (1, LEFT, 0), (1, LEFT, 0), (0, LEFT, 2), (1, RIGHT, 2), (0, LEFT, 1))

Agent 2: ((0, LEFT, 1), (0, RIGHT, 0), (1, RIGHT, 0), (1, LEFT, 1), (0, RIGHT, 0), (0, LEFT, 1))

CET(4) ≥ 49,184,559

Agent 1: (0, LEFT, 1), (0, LEFT, 2), (0, LEFT, 3), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0), (0, RIGHT, 0)

Agent 2: (1, RIGHT, 1), (1, LEFT, 3), (1, RIGHT, 2), (1, RIGHT, 1), (1, LEFT, 2), (1, LEFT, 0), (0, RIGHT, 2), (0, RIGHT, 3)

CET(2,3) ≥ 8,786

Agent 1: ((1, LEFT, 2), (0, LEFT, 1), (0 LEFT, 2), (1, RIGHT, 2), (0, LEFT, 0), (1, LEFT, 0))

Agent 2: ((1, RIGHT, 1), (1, LEFT, 0), (1 LEFT, 1), (0, LEFT, 2), (0, LEFT, 2), (0, RIGHT, 1))

=== Discovered Champions: ===
CET(0) = 0 by '''NathFR76'''

CET(1) = 1 by '''NathFR76'''

CET(2) = 97 by '''NathFR76'''

CET(3) ≥ 3,746,207 by '''Roromachine14'''<ref>it's discord pseudoname</ref>

CET(4) ≥ 49,184,559 by '''Roromachine14'''

User:NathFR76

2026-11-01T12:36:52Z

NathFR76: I add a function named Thutus in my user page because Δ⁵ recommended it

SKI Calculus

2026-11-01T11:57:18Z

NathFR76: I add a function named Thutus in SKI calculus

A '''SKI calculus''' program is a binary tree where the leaves are combinators, the three symbols <code>S</code>, <code>K</code>, <code>I</code>. Using parentheses to notate the tree, a simple example of a SKI program is <code>(((SK)S)((KI)S))</code>. We can omit parentheses by assuming they are left-binding by default, so we simplify our program to <code>SKS(KIS)</code>.

Like [[Lambda Calculus|lambda calculus]], SKI calculus has a process called beta-reduction. The tree can be evaluated according to any reducible redex.

Sfgx = fx(gx)

Kfx = f

Ix = x

Note that <code>xyz</code> represent any valid trees, not just single combinators. We repeat this process and we say it terminates if the combinator cannot be beta-reduced.

Busy Beaver for SKI calculus (Ξ₀) is a variation of the [[Busy Beaver for lambda calculus|Busy Beaver problem for lambda calculus]]. Ξ₀(n) is defined as the size of the largest output of a terminating program of size n.

== Champions ==
{| class="wikitable"
! n !! Value !! Champion
|-
| 0 || = 0 ||
|-
| 1 || = 1 || S
|-
| 2 || = 2 || SS
|-
| 3 || = 3 || SSS
|-
| 4 || = 4 || SSSS
|-
| 5 || = 6 || SSS(SS)
|-
| 6 || = 17 || SSS(SI)S
|-
| 7 || ≥ 41 || SSS(S(SS))S
|-
| 8 || ≥ 80 || SSK(S(SS)S)S
|-
| 9 || ≥ 1561 || S(SI)(SS)(SS)SS
|-
| 10 || ≥ 1562 || S(S(SI)(SS)(SS)SS)
|-
| 11 || ≥ 1563 || SS(S(SI)(SS)(SS)SS)
|-
| 12 || ≥ 2^2^513 × 8 - 2 || S(SI)(SSK)(S(S(KS)K)I)
|-
| 13 || > 2^^2^^2^258 || SI(SI)(SSK)(S(S(KS)K)I)
|-
| 14 || > 2^^2^^2^258 || SI(SI)(SSK)(S(S(KS)K)I)S
|-
| 15 || > 2^^2^^2^^34 || S(S(SI)I(SSK))I(S(S(KS)K)I)
|-
| 16 || > 2{3}19 || S(S(SI))I(S(SSK)(K(S(S(KS)K)I)))
|-
| 17 || > 2{4}2^^2^^258 || S(SS(SSS)I(SSK))I(S(S(KS)K)I)
|-
| 18 || > 2{4}2^^2^^258 || S(SS(SSS)I(SSK))I(S(S(KS)K)I)S
|-
| 19 || > 2{4}2{3}17 || SSI(SSK(S(S(KS)K)I))(S(K(S(SSK)))K)
|-
| 20 || > fω+1 (2^^7/2-1) > [[Graham's number]] || S(S(S(SI)))I(S(K(S(SS(K(K(S(S(KS)K)I))))))K)
|-
| ... || ||
|-
| 27 || > fω+2 (2^2^21) || SI(SI(SI(S(S(K(SS(KI))))I)))(S(K(S(SSK)))K)(S(S(KS)K)I)
|-
| 28 || > fω+2 (2^2^21) || S(SI(SI(SI(S(S(K(SS(KI))))I)))(S(K(S(SSK)))K)(S(S(KS)K)I))
|-
| 29 || > fω+3 (2^2^21) || SI(SI(SI(SI(S(S(K(SS(KI))))I))))(S(K(S(SSK)))K)(S(S(KS)K)I)
|-
| 30 || > fω+3 (2^2^21) || S(SI(SI(SI(SI(S(S(K(SS(KI))))I))))(S(K(S(SSK)))K)(S(S(KS)K)I))
|-
| 31 || > fω+4 (2^2^21) || SI(SI(SI(SI(SI(S(S(K(SS(KI))))I)))))(S(K(S(SSK)))K)(S(S(KS)K)I)
|-
| 32 || > fω+4 (2^2^21) || S(SI(SI(SI(SI(SI(S(S(K(SS(KI))))I)))))(S(K(S(SSK)))K)(S(S(KS)K)I))
|-
| ... || ||
|}

== SK calculus ==
We can remove the <code>I</code> combinator and replace it by <code>(SKS)</code>, <code>(SKK)</code> or any <code>(SKx)</code>. These terms have a straightforward binary encoding where (prefix) application is 1, K=00, and S=01. Since n combinators take n-1 applications to combine, their code length is 2n + n-1 = 3n-1 bits.

=== Champions for Ξ₀SK ===
{| class="wikitable"
! n !! bits !! Value !! Champion
|-
| 0 || -1 || = 0 ||
|-
| 1 || 2 || = 1 || S
|-
| 2 || 5 || = 2 || SS
|-
| 3 || 8 || = 3 || SSS
|-
| 4 || 11 || = 4 || SSSS
|-
| 5 || 14 || = 6 || SSS(SS)
|-
| 6 || 17 || = 10 || SSS(SS)S
|-
| 7 || 20 || = 41 || SSS(S(SS))S
|-
| 8 || 23 || ≥ 80 || SSK(S(SS)S)S
|-
| 9 || 26 || ≥ 169 || S(SS)(SS)(SS)SS
|-
| 10 || 29 || ≥ 1561 || SS(SS)(SSS)SSS
|-
| 11 || 32 || ≥ 1562 || S(SS(SS)(SSS)SSS)
|-
| 12 || 35 || ≥ 1563 || S(S(SS(SS)(SSS)SSS))
|-
| 13 || 38 || ≥ 7811 || S(SS)(SS)(SS(SS(SSS)))S
|-
| 14 || 41 || ≥ 2^2097156 × 13 - 2 || SSS(SSK)(SS(SK)(S(KS)K))
|-
| 15 || 44 || ≥ 2^2^2097156 × 3 - 2 || SSS(SSK)(SS(SK)(S(KS)K))S
|-
| 16 || 47 || > 2^2^2^8193 || S(SS(SS))(SSK)(SS(SK)(S(KS)K))
|-
| 17 || 50 || > 2^^2^^2^258 || SSS(S(SK))(SSK)(SS(SK)(S(KS)K))
|-
|... || ||
|-
| 22 || 65 || > 2{3}19 ||S(S(S(S(SK))))(S(SK))(S(SSK)(K(SS(SK)(S(KS)K)))
|-
| 23 || 68 || > 2{4}2{3}17 || SS(S(SK))(SSK(SS(SK)(S(KS)K)))(S(K(S(SSK)))K)
|-
| 24 || 71 || > 2{4}2{3}17 || S(SS(S(SK))(SSK(SS(SK)(S(KS)K)))(S(K(S(SSK)))K))
|-
| 25 || 74 || > 3{7}3 || SS(S(SK))(SSK(SS(SS(SK))(S(KS)K)))(S(K(S(SSK)))K)
|-
| 26 || 77 ||> fω+1(2^^7/2-1) > [[Graham's number]] ||S(S(S(S(SKS))))(SKS)(S(K(S(SS(K(K(SS(SK)(S(KS)K)))))))K)
|}
TODO: Champions analysis.

== BCKW calculus ==
BCKW calculus is a variation of SK calculus that replace the S combinator with 3 new combinators B, C and W.

Bfgx = f(gx)

Cfxy = fyx

Kfx = f

Wfx = fxx

=== Champions for Ξ₀BCKW ===
{| class="wikitable"
! n !! Value !! Champion
|-
| 0 || = 0 ||
|-
| 1 || = 1 || B
|-
| 2 || = 2 || BB
|-
| 3 || = 3 || BBB
|-
| 4 || = 11 || WW(WB)
|-
| 5 || = 47 || W(WW)(WB)
|-
| 6 || ≥ 2^256 × 6 - 1 ||WW(WC(WB))
|-
| 7 || > 2{3}17 || WW(C(WC)(WB))
|-
| 8 || > 2{3}2{3}17 || W(WW)(C(WC)(WB))
|-
| 9 || > 2{5}2{4}2{3}17 || WW(WB(C(WC))(WB))
|-
| 10 || > fω+1(2^^6/2-1) || WW(C(WB)(C(CC(WB))))
|-
| ... || ||
|-
| 15 || > fω2^^18-1(2) ||WW(C(WB)(B(BC(CC(WB)))(C(BC))))
|}

== Thutus calculus ==
Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

# Alphabet

For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols. Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule: L₁ x1 → x1. The arguments x1, x2, x3, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution. For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses. Arguments may be reused, rearranged, nested, or deleted. Examples: L₄ x1 x2 → x1 (x2 (x1 x1)) L₄ x1 x2 x3 → x3 (x1 x2)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus. An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) (also written as Ξ₀T) the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems. The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

=== Champions for T(n) / Ξ₀T ===
{| class="wikitable"
! n !! Value !! Champion Initiate Term
!Champion Rule
|-
| 0 || = 0 ||
|
|-
| 1 || = 1 || L1
|L1 x1 -> x1
|-
| 2 || = 1 || L1L2
|L1 x1 -> x1
L2 x1 -> x1 x1
|-
| 3 || = 4 || L2(L3L3)
|L1 x1 -> x1
L2 x1 -> x1 x1
L3 x1 x2 -> x1 (x1 x2)
|-
| 4 || ≥ 522 || L3(L3(L4L4))
|L1 x1 -> x1
L2 x1 -> x1 x1
L3 x1 -> (x1 x1) x1
L4 x1 x2 x3 -> x1 x2 (x2 x3)
|-
| 5 || ≥ fω+1(2^^6/2) || L1(L2(L4(L5L3))
|L1 x1 -> x1
L2 x1 -> x1 x1
L3 x1 x2 -> x1 (x1 x2)
L4 x1 x2 -> x2 (x2 x1)
L5 x1 x2 x3 -> x3 x2 x1
|-
| ... || ||
|
|-
| 15 || > fω2^^18-1(2) ||L4L4(L5(L4L6)(L6(L6L5(L5L5(L4L6)))(L5(L6L5))))
|L1 x1 -> x1
L2 x1 -> x1
L3 x1 x2 -> x1
L4 x1 x2 -> x1 x2 x2
L5 x1 x2 x3 -> x1 x3 x2
L6 x1 x2 x3 -> x1 (x2 x3)
L7 x1 -> x1
L8 x1 -> x1
L9 x1 -> x1
L10 x1 -> x1
L11 x1 -> x1
L12 x1 -> x1
L13 x1 -> x1
L14 x1 -> x1
L15 x1 -> x1
|}

== Oracles ==

We can extend Ξ₀ with oracles, making it stronger than BB. For example, we can add an oracle combinator O where Ofxy=x iff for all z fz is equivalent to z, and y otherwise. The resulting busy beaver, known as the Ξ function, is estimated to be faster-growing than oracle busy beavers with the oracle degree ≤ ω₁CK. In addition, Ξ is independent of True Arithmetic, requiring Δ¹₁ truth to fully decide. A further extension would be to add another oracle, O’, where O’fxy=x iff f is well-founded, and y otherwise, where a term is well-founded iff there is no infinitely nested outermost-redex oracle calls. The resulting busy beaver is called Ξ₂.

=== Champions for Ξ ===
{| class="wikitable"
! n !! Value !! Champion
|-
| 0 || = 0 ||
|-
| 1 || = 1 || S
|-
| 2 || = 2 || SS
|-
| 3 || = 3 || SSS
|-
| 4 || = 4 || SSSS
|-
| 5 || = 6 || SSS(SS)
|-
| 6 || = 17 || SSS(SI)S
|}

== See Also ==
* [https://web.archive.org/web/20250217071017/https://komiamiko.me/math/ordinals/2020/06/21/ski-numerals.html Lower bounds of this function] (archived)
* [https://dallaylaen.github.io/ski-interpreter/ SKI interpreter]

[[Category:Functions]]

User:NathFR76

2026-10-30T13:14:04Z

NathFR76: i changed few spacing text

Hi! My name is Nathan.

I created **Thutus**, a diagonalization of the SKI calculus, and its associated function \(T(n)\).

This page describes the system, its rewrite rules, and the lower bounds currently known for \(T(n)\).

THUTUS — Function T(n)

Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

1. Alphabet

For each integer n ≥ 1, the available alphabet is:
L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols.
Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule:
L₁x → x.

The arguments x, y, z, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution.

For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses.

Arguments may be reused, rearranged, nested, or deleted.

Examples:
L₄xy → x(y(xx))
L₄xyz → z(xy)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus.

An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) is the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems.

The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

And actually few value for T(n):

T(0) = 0

T(1) = 1

T(2) = 1

T(3) = 4

T(4) ≥ 522

T(5) ≥ 1814

T(6) or higher can encode BCKW system so:

T(6) ≥ 2^256*6-1

T(7) ≥ 2^^^17

T(8) ≥ 2^^^2^^^17

T(9) ≥ 2^^^^^2^^^^2^^^17

T(10) ≥ f_ω+1(2^^6/2-1)

T(15) ≥ f_ω^(2^^18-1)(2)

And for T(1) to T(5) result:

T(1) = 1

A

T(2) = 1

AB

B

T(3) = 4

Initial: (L2 (L3 L3))

Rules:
L1 (1 args) -> x1
L2 (1 args) -> (x1 x1)
L3 (2 args) -> (x1 (x1 x2))
L3 (L3 (L3 L3))

T(4) ≥ 522

Initial: (L3 (L3 (L4 L4)))

Rules:
L1 (1 args) -> x1
L2 (1 args) -> (x1 x1)
L3 (1 args) -> ((x1 x1) x1)
L4 (3 args) -> ((x1 x2) (x2 x3))
Normal form: ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))))))) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4)))))))) ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))))) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4)))))) ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4)))))) ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L ... [truncated]

T(5) ≥ 1814

Initial: (L3 ((L3 L4) (L4 L5)))

Rules:
L1 (1 args) -> x1
L2 (1 args) -> x1
L3 (1 args) -> (x1 (x1 x1))
L4 (2 args) -> (x1 (x2 (x1 x2)))
L5 (4 args) -> x4
Normal form: (((L5 ((L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))) ((L5 (L4 (L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))))) ((L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))) (L5 (L4 (L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))))))))) (L4 (L5 ((L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))) ((L5 (L4 (L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))))) ((L5 (L5 (((L5 (L4 (L4 L5))) ... [truncated]

This bound for T(4) and T(5) is from a python program but T(4) and T(5) is probably higher than this bound and this bound is verified by SKI Interpreter (https://dallaylaen.github.io/ski-interpreter/)

User:NathFR76

2026-10-30T13:12:50Z

NathFR76: Created page with "Hi! My name is Nathan. I created **Thutus**, a diagonalization of the SKI calculus, and its associated function \(T(n)\). This page describes the system, its rewrite rules, and the lower bounds currently known for \(T(n)\). THUTUS — Function T(n) Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus. 1. Alphabet For each integer n ≥ 1, the available alphabet is: L₁, L₂, ..., Lₙ. 2. Initial expression..."

Hi! My name is Nathan.

I created **Thutus**, a diagonalization of the SKI calculus, and its associated function \(T(n)\).

This page describes the system, its rewrite rules, and the lower bounds currently known for \(T(n)\).

THUTUS — Function T(n)

Thutus is a combinatorial rewriting system whose syntax and expression application follow the SKI calculus.

1. Alphabet

For each integer n ≥ 1, the available alphabet is:
L₁, L₂, ..., Lₙ.

2. Initial expression

The initial expression contains exactly n occurrences of symbols.
Parentheses do not count toward the size.

3. Arity

Each symbol Lₖ has between 1 and k−1 arguments, with the exception of L₁, which always follows the rule:
L₁x → x.

The arguments x, y, z, etc., may be arbitrarily complex expressions.

4. Rewriting rules

The rules for each symbol are chosen prior to execution and remain fixed throughout the execution.

For each symbol Lₖ, the right-hand side of its rule contains between 1 and k occurrences of arguments, excluding parentheses.

Arguments may be reused, rearranged, nested, or deleted.

Examples:
L₄xy → x(y(xx))
L₄xyz → z(xy)

5. Reduction and termination

At each step, a rule may be applied to any reducible occurrence, as in the SKI calculus.

An expression terminates when it reaches a normal form—that is, when no further rules can be applied. Expressions that diverge do not contribute to the maximum.

6. Definition of T(n)

T(n) is the maximum number of symbols in the final normal form, taken over all initial expressions of size exactly n and all admissible Thutus rule systems.

The available alphabet is L₁, ..., Lₙ. The rules are chosen at the outset, must satisfy the aforementioned constraints, and remain fixed throughout the execution.

And actually few value for T(n):

T(0) = 0

T(1) = 1

T(2) = 1

T(3) = 4

T(4) ≥ 522

T(5) ≥ 1814

T(6) or higher can encode BCKW system so:

T(6) ≥ 2^256*6-1

T(7) ≥ 2^^^17

T(8) ≥ 2^^^2^^^17

T(9) ≥ 2^^^^^2^^^^2^^^17

T(10) ≥ f_ω+1(2^^6/2-1)

T(15) ≥ f_ω^(2^^18-1)(2)

And for T(1) to T(5) result:
T(1) = 1

A

T(2) = 1

AB
B

T(3) = 4

Initial: (L2 (L3 L3))
Rules:
L1 (1 args) -> x1
L2 (1 args) -> (x1 x1)
L3 (2 args) -> (x1 (x1 x2))
L3 (L3 (L3 L3))

T(4) ≥ 522

Initial: (L3 (L3 (L4 L4)))
Rules:
L1 (1 args) -> x1
L2 (1 args) -> (x1 x1)
L3 (1 args) -> ((x1 x1) x1)
L4 (3 args) -> ((x1 x2) (x2 x3))
Normal form: ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))))))) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4)))))))) ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))))) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4)))))) ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4)))))) ((L4 ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L4 L4))))) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) (L4 L4)))) ((L4 ((L4 L4) (L4 L4))) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) ((L4 (L4 L4)) ((L4 L4) (L ... [truncated]

T(5) ≥ 1814

Initial: (L3 ((L3 L4) (L4 L5)))
Rules:
L1 (1 args) -> x1
L2 (1 args) -> x1
L3 (1 args) -> (x1 (x1 x1))
L4 (2 args) -> (x1 (x2 (x1 x2)))
L5 (4 args) -> x4
Normal form: (((L5 ((L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))) ((L5 (L4 (L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))))) ((L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))) (L5 (L4 (L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))))))))) (L4 (L5 ((L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))) ((L5 (L4 (L5 (L5 (((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))) (L5 ((L5 (L4 (L4 L5))) (L5 ((L5 (L4 (L4 L5))) (L5 (L5 (L4 (L4 L5))))))))))))) ((L5 (L5 (((L5 (L4 (L4 L5))) ... [truncated]

This bound for T(4) and T(5) is from a python program but T(4) and T(5) is probably higher than this bound and this bound is verified by SKI Interpreter (https://dallaylaen.github.io/ski-interpreter/)