Forced Extensioned Busy Beaver: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
HelpMe (talk | contribs)
HelpMe moved page Forced Extensioned Busy Beaver to Greedy Busy Beaver: incorrect definition
Tag: New redirect
 
m FEBB(6) is solved now
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
#REDIRECT [[Greedy Busy Beaver]]
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>
|-
|6
|11,016,763
|<code>[1LE]0LB_1LA[1RF]_1RB[1RA]_1RA[1RD]_1RD[1LA]_0RC[1RZ]</code>
|}
 
[[Category:Functions]]

Latest revision as of 06:02, 18 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:

  1. 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.
  2. 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]
6 11,016,763 [1LE]0LB_1LA[1RF]_1RB[1RA]_1RA[1RD]_1RD[1LA]_0RC[1RZ]