User:NathFR76

Hi! My name is Nathan.

Thutus calculus

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₁ 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

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

[

CET(n)=\max{\text{number of steps before collision}}

]

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)

	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	≥ $2\times 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) ≥ 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) ≥ $2\times 10^{23}$ (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

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