Forced Extensioned Busy Beaver: Difference between revisions
Jump to navigation
Jump to search
HelpMe moved page Forced Extensioned Busy Beaver to Greedy Busy Beaver: incorrect definition Tag: New redirect |
champions Tags: Removed redirect Visual edit |
||
| Line 1: | Line 1: | ||
# | The '''Forced Extensioned Busy Beaver''' function (FEBB(n)) is defined as the largest number of steps executed by any halting n-state machine obtained by extending one of the n-1-state champions. | ||
An n-state machine can be extended to an n+1-state machine according to the following rules: | |||
# Replace each of the machine's marked transitions (here, represented with square brackets) with any valid transition, other than the halting transition. These transitions are still marked. | |||
# Add another state to the machine, consisting of any two valid transitions; there must be exactly one halting transition, which is also marked. | |||
Additionally, we define <code>[1RZ]---</code> (with the A0 transition marked) as the 1-state champion. | |||
== Champions == | |||
{| class="wikitable" | |||
!n | |||
!FEBB(n) | |||
!Champions | |||
|- | |||
|1 | |||
|1 | |||
|<code>[1RZ]---</code> | |||
|- | |||
|2 | |||
|6 | |||
|<code>[1RB]0LB_1LA[1RZ]</code>, <code>[1RB]1LB_1LA[1RZ]</code> | |||
|- | |||
|3 | |||
|14 | |||
|<code>[1RC]0LB_1LA[0RC]_1RB[1RZ]</code> | |||
|- | |||
|4 | |||
|52 | |||
|<code>[0RC]0LB_1LA[1LC]_1RB[0LD]_1RA[1RZ]</code> | |||
|- | |||
|5 | |||
|≥ 792 | |||
|<code>[1RC]0LB_1LA[0LB]_1RB[0RE]_1RA[0RB]_1RD[1RZ]</code> | |||
|} | |||
Revision as of 13:07, 15 November 2026
The Forced Extensioned Busy Beaver function (FEBB(n)) is defined as the largest number of steps executed by any halting n-state machine obtained by extending one of the n-1-state champions.
An n-state machine can be extended to an n+1-state machine according to the following rules:
- Replace each of the machine's marked transitions (here, represented with square brackets) with any valid transition, other than the halting transition. These transitions are still marked.
- Add another state to the machine, consisting of any two valid transitions; there must be exactly one halting transition, which is also marked.
Additionally, we define [1RZ]--- (with the A0 transition marked) as the 1-state champion.
Champions
| n | FEBB(n) | Champions |
|---|---|---|
| 1 | 1 | [1RZ]---
|
| 2 | 6 | [1RB]0LB_1LA[1RZ], [1RB]1LB_1LA[1RZ]
|
| 3 | 14 | [1RC]0LB_1LA[0RC]_1RB[1RZ]
|
| 4 | 52 | [0RC]0LB_1LA[1LC]_1RB[0LD]_1RA[1RZ]
|
| 5 | ≥ 792 | [1RC]0LB_1LA[0LB]_1RB[0RE]_1RA[0RB]_1RD[1RZ]
|