BusyBeaverWiki - User contributions [en]

Champions

2024-08-17T19:16:20Z

Mei: fix typo in reference name

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Tree Normal Form

2024-07-13T15:42:02Z

Mei: /* TNF-1RB */ Expand on the equivalence between 1RB and 0RB machines

'''Tree Normal Form (TNF)''' is the unique standard [[Turing machine]] transition table representation for a class of functionally equivalent TMs (for the purposes of the Busy Beaver problem). TNF is also often used to to describe the process first described by Allen Brady which enumerates all TMs in TNF.

== Background ==
Radó's original definition of a Busy Beaver TM allows any choice of (write symbol, move direction, next state) for every (current state, read symbol) combination. For n-states, m-symbols that leads to <math>N(n,m) = (2m(n+1))^{mn}</math> distinct TMs (Note: there are <math>n+1</math> next states for the n run states and 1 halt state). But for the purposes of searching for Busy Beavers, these contain a lot of redundant TMs. Some notable redundancies are:

# Permutations: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.
# Unused transitions: If the TM (when started on a blank tape) does not actually use all transitions, then the behavior of this TM is identical for all choices of those transitions.
# Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of <math>2(m-1)</math> lead to same sigma score).
# Number of halting transitions: Any TM without any halting transitions can (obviously) never halt, so they can be ignored for the purposes of solving the Busy Beaver problem.

In order to (significantly) reduce the search space, TNF requires that the TM satisfy the following:

# Canonical permutation: All states (and symbols) are used in order when run on a blank tape. The first move direction is Right.
# Undefined transitions: All unused transitions are marked as blank/undefined <code>---</code>.
# Unique halting transition: All halting transitions are of the form <code>1RZ</code>.
# Require halting transition: TMs must have at least one undefined (<code>---</code>) or halting (<code>1RZ</code>) transition.

== TNF Enumeration ==
TNF enumeration is a process for enumerating all TMs in TNF by recursively expanding a "family tree" of machines:

* Start with a completely undefined TM of the desired size, this is the root node. Ex <code>------_------</code> for BB(2).
* For each unexplored node, run that TM on a blank tape until it reaches an undefined transition (or you give up searching).
* If you reach an undefined transition, then create children nodes from this node for all choices of transitions.
** One option for transition is always the single halting transition <code>1RZ</code>.
** If there is at least one more undefined transition (besides this one being filled in now) then we also allow all combinations of transitions with the following restrictions:
*** The next state may be any previously visited state or the next unvisited one,
*** The write symbol may be any previously used symbol or the next unused one.
*** If we are expanding the first transition of the machine, the direction must be Right.
*Repeat this on every leaf node (which contains at least one undefined transition).
This enumeration is complete if every leaf node is either a halting TM or an infinite TM that never reaches its undefined transitions. Unfortunately, there is no programmatic way to ensure you are done because that would involve solving the halting problem. Instead it is often helpful to think of TNF enumeration as an iterated process in which the tree is expanded as much as possible early on, but then iteratively refined over time as new leafs are proven to reach undefined transitions.

== TNF-1RB ==
One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, the TM that starts in state B instead will have the same exact sigma score and run for exactly one step less. By iterating this process at most <math>n - 1</math> times, any <math>n</math>-state <code>A0→0RB</code> machine can be transformed into an equivalent <code>A0→1RB</code> machine.

Many early enumerations chose to use the <code>A0→1RB</code> restriction because they were specifically searching for Σ. It can also be used when searching for the step champion, but requires some post-processing to check the near-champions for any state permutations that might lead to a few more steps.

== Number of TNF TMs ==
{| class="wikitable" style="text-align: right;"
|+
!
!Total TMs
!TNF TMs
!TNF-1RB TMs
|-
|[[BB(2)]]
|20,736
|
|41
|-
|[[BB(3)]]
|16,777,216
|
|4,057
|-
|[[BB(4)]]
|25,600,000,000
|
|620,261
|-
|[[BB(5)]]
|63,403,380,965,376
|
|126,891,605
|-
|[[BB(6)]]
|232,218,265,089,212,416
|
|~33,436,000,000
|}

Tree Normal Form

2024-07-13T15:36:58Z

Mei: /* TNF Enumeration */ Clarify what is meant by "first direction".

'''Tree Normal Form (TNF)''' is the unique standard [[Turing machine]] transition table representation for a class of functionally equivalent TMs (for the purposes of the Busy Beaver problem). TNF is also often used to to describe the process first described by Allen Brady which enumerates all TMs in TNF.

== Background ==
Radó's original definition of a Busy Beaver TM allows any choice of (write symbol, move direction, next state) for every (current state, read symbol) combination. For n-states, m-symbols that leads to <math>N(n,m) = (2m(n+1))^{mn}</math> distinct TMs (Note: there are <math>n+1</math> next states for the n run states and 1 halt state). But for the purposes of searching for Busy Beavers, these contain a lot of redundant TMs. Some notable redundancies are:

# Permutations: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.
# Unused transitions: If the TM (when started on a blank tape) does not actually use all transitions, then the behavior of this TM is identical for all choices of those transitions.
# Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of <math>2(m-1)</math> lead to same sigma score).
# Number of halting transitions: Any TM without any halting transitions can (obviously) never halt, so they can be ignored for the purposes of solving the Busy Beaver problem.

In order to (significantly) reduce the search space, TNF requires that the TM satisfy the following:

# Canonical permutation: All states (and symbols) are used in order when run on a blank tape. The first move direction is Right.
# Undefined transitions: All unused transitions are marked as blank/undefined <code>---</code>.
# Unique halting transition: All halting transitions are of the form <code>1RZ</code>.
# Require halting transition: TMs must have at least one undefined (<code>---</code>) or halting (<code>1RZ</code>) transition.

== TNF Enumeration ==
TNF enumeration is a process for enumerating all TMs in TNF by recursively expanding a "family tree" of machines:

* Start with a completely undefined TM of the desired size, this is the root node. Ex <code>------_------</code> for BB(2).
* For each unexplored node, run that TM on a blank tape until it reaches an undefined transition (or you give up searching).
* If you reach an undefined transition, then create children nodes from this node for all choices of transitions.
** One option for transition is always the single halting transition <code>1RZ</code>.
** If there is at least one more undefined transition (besides this one being filled in now) then we also allow all combinations of transitions with the following restrictions:
*** The next state may be any previously visited state or the next unvisited one,
*** The write symbol may be any previously used symbol or the next unused one.
*** If we are expanding the first transition of the machine, the direction must be Right.
*Repeat this on every leaf node (which contains at least one undefined transition).
This enumeration is complete if every leaf node is either a halting TM or an infinite TM that never reaches its undefined transitions. Unfortunately, there is no programmatic way to ensure you are done because that would involve solving the halting problem. Instead it is often helpful to think of TNF enumeration as an iterated process in which the tree is expanded as much as possible early on, but then iteratively refined over time as new leafs are proven to reach undefined transitions.

== TNF-1RB ==
One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, the TM starts in state B will have the same exact sigma score and run for exactly one step longer. Many early enumerations used this restriction because they were specifically searching for Σ. It can also be used when searching for the step champion, but requires some post-processing to check for any state permutations that might lead to a few more steps.

== Number of TNF TMs ==
{| class="wikitable" style="text-align: right;"
|+
!
!Total TMs
!TNF TMs
!TNF-1RB TMs
|-
|[[BB(2)]]
|20,736
|
|41
|-
|[[BB(3)]]
|16,777,216
|
|4,057
|-
|[[BB(4)]]
|25,600,000,000
|
|620,261
|-
|[[BB(5)]]
|63,403,380,965,376
|
|126,891,605
|-
|[[BB(6)]]
|232,218,265,089,212,416
|
|~33,436,000,000
|}

Closed Set

2024-06-21T13:45:30Z

Mei: reword the introductory sentence

A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Tape Language]], [[Closed Position Set]] and [[Finite Automata Reduction]].

== General Definition ==
Given a specific Turing machine ''M'', a set ''C'' of configurations is a '''closed set''' for ''M'' if:
# ''M'' enters ''C'': <math>\exists c \in C: O \to^* c</math> (where <math>O</math> is the initial config).
# ''C'' is closed: <math>\forall c \in C: \exists d \in C: c \to^+ d</math>. Every configuration in ''C'' returns to a new config in ''C'' after some '''positive''' number of steps.
# ''C'' is non-halting: <math>\forall c \in C:</math> ''c'' is not a halting config.

We can easily see that if all of these conditions hold, then ''M'' can never halt because it will enter set ''C'' and once it has entered, it will return infinitely often and these configurations will never be halt configs.

Note that ''C'' may contain configurations that ''M'' will never reach and in fact this is usually the case. In this way, closed set deciders generalize a behavior in order to simplify its proof of non-halting. A closed set proof does not tell you what the TM will do precisely, instead it tells you that (whatever it does) it will never escape some broad category.

== Stepwise Closed Set ==
It is often easier to prove that ''C'' is a closed set if it satisfies a stricter set of rules.

Given a specific Turing machine ''M'', a set ''S'' of configurations is a '''stepwise closed set''' for ''M'' if:
# ''M'' starts in ''S'': <math>O \in S</math> (where <math>O</math> is the initial config).
# ''S'' is closed under single step: <math>\forall c \in S: c \to^1 d \implies d \in S</math>. If you take one step from any configuration in ''S'', you remain in ''S''.
# ''S'' is non-halting: <math>\forall c \in S:</math> ''c'' is not a halting config.

Any stepwise closed set is general closed set.

== Deciders ==
We have described closed sets above as general mathematical sets. But in order for a decider to effectively use a closed set method it must define these sets precisely using some sort of "tape language". The exact choice of tape language is one of the primary distinctions between different closed set deciders.

* [[Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.
* [[Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.
* [[Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.

For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.

== See also ==

* https://www.sligocki.com/2022/06/10/ctl.html

Holdouts lists

2024-06-14T14:16:30Z

Mei: typo

A holdout (or undecided machine) is a [[Turing machine]] for which it is not known whether the machine halts or not from all-0 input tape.

Holdout lists are often shared by contributors:

{| class="wikitable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13th 2024]
|@tjligocki, @Shawn Ligocki
| 12091
|[[:File:BB6 holdouts 12091.txt]]
|-
|BB(3,3)
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9th 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7th 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|-
|BB(2,5)
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22nd 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|}

Main Page

2024-06-14T14:13:55Z

Mei: don't show Category: as part of the link

The [[Busy Beaver function]] BB (called S originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 <ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref> for 2-symbol [[Turing machines]] and later generalised<ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref> to m-symbol Turing machines:

{| class="wikitable"
|-
| BB(n,m) = Maximum number of steps done by a halting m-symbol Turing machine with n states starting from all-0 memory tape
|}

The busy beaver function is not computable and, few of its values are known:

{| class="wikitable"
|+ Small busy beaver values <ref>https://bbchallenge.org/~pascal.michel/ha.html</ref> <ref name=":0">https://bbchallenge.org/</ref>
|-
| || 2-state || 3-state || 4-state || 5-state || 6-state
|-
| 2-symbol
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| [[BB(6)]] > <math>10 \uparrow \uparrow 15</math>
|-
| 3-symbol || [[BB(2,3)]] = 38
| style="background: orange;" | [[BB(3,3)]] > <math>10^{17}</math>
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>10^{14072}</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
| 4-symbol
| [[BB(2,4)]] = 3,932,964
| style="background: #ffe4b2;" | [[BB(3,4)]] > 2(^15)5 + 14
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
| 5-symbol
| style="background: orange;" | [[BB(2,5)]] > 6.5 × <math>10^{38033}</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |

|}

In the above table, cells are highlighted in orange when there are known [[Cryptids]] (mathematically-hard machines) in that class.

=== [[bbchallenge.org]] ===

[[bbchallenge.org]] <ref name=":0" /> is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:

* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])
* Maintaining [[Holdouts lists]] for small busy beaver values
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]
* Finding [[Cryptids]] (mathematically-hard machines)
* Building [[Accelerators]] to simulate halting machines faster

Notably, as part of [[bbchallenge.org]], in June 2024 the 5th busy beaver value [[BB(5)]] was proven in Coq to be equal to the lower bound found in 1989<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>: 47,176,870.

==Notes==
<references />

Directed head notation

2024-06-12T23:23:51Z

Mei: avoid pointless redirect in link

'''Directed head notation''' is a notation for specifying a [[Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{ 

or for a partial configuration <math display="block">101 \; \textrm{ A> } \; 1^n</math>

== Tape Compression ==
This notation supports run-length encoding for tape compression using "exponents". Given a "word" (sequence of tape symbols) <math>w</math> and a count <math>n</math>, <math>w^n</math> represents <math>n</math> repetitions of <math>w</math> concatenated. So for example, <math>2^4 = 2222</math> and <math>10^3 = 101010</math>.

It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions, generally it should be obvious from the context that this is a tape configuration and not a math expression.

Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation <math>0^\infty</math> is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:<math display="block">0^\infty \; 121212 = 0^\infty \; 12 \; 12 \; 12 = 0^\infty \; 12^3 = 0^\infty \; 01 \; 21^2 \; 2</math>

== Directed Head ==
Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configurations include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).

In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.

== Partial Configurations ==
A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes <math>0^\infty</math> at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration<math display="block">101 \; \textrm{ C> } \; 1^3</math>matches any of these complete configurations<math display="block">\begin{array}{rcl}
0^\infty \; 101 & \textrm{ C> } & 1^3 \; 0^\infty \\
0^\infty \; 11101 & \textrm{ C> } & 1^8 \; 0^\infty \\
0^\infty \; 01^3 & \textrm{ C> } & 11^2 \; 0^\infty \\
\end{array}</math>Partial configurations may have no segments specified even on the side the TM head is facing. For example<math display="block">\textrm{<C} \; 101</math>is a valid partial configuration. In these cases, we cannot tell what "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.

== Configuration Transitions ==
One of the most common use cases for directed head notation is for specifying configurations transition rules. For example, the rule<math display="block">\begin{array}{c}
\\
0^\infty \; 011 \; \textrm{<C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<C} \; 101 \; 0^\infty \\
\end{array}</math>indicates that if the TM starts in config <math> 0^\infty \; 011 \; \textrm{<C} \; 0^\infty</math>, 3 steps later it will be in configuration <math> 0^\infty \; \textrm{<C} \; 101 \; 0^\infty</math>. It is common to define these rules for partial configurations. For example,<math display="block">\begin{array}{c}
\\
011 \; \textrm{<C} \; \xrightarrow{3} \; \textrm{<C} \; 101 \\
\end{array}</math>which means that for any complete configuration <math> w \; 011 \; \textrm{<C} \; u</math> (where <math> w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math> w \; \textrm{<C} \; 101 \; u</math>.

Transition rules become especially useful once you use induction to prove them over an arbitrary repetition counts. For example [[Shift rule|shift rules]] like for all <math> n \ge 0</math>:<math display="block">\begin{array}{c}
\\
011^n \; \textrm{<C} \; \xrightarrow{3n} \; \textrm{<C} \; 101^n \\
\end{array}</math>

Turing machines

2024-06-12T23:22:27Z

Mei: Mei moved page Turing machines to Turing machine: The singular form should be preferred for a page title

#REDIRECT [[Turing machine]]

Turing machine

2024-06-12T23:22:27Z

Mei: Mei moved page Turing machines to Turing machine: The singular form should be preferred for a page title

'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref>
As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors.
In the Busy Beaver space, the following conventions has been adopted:
* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.
* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.
* The machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
** Replace the symbol it has read with a possibly different one;
** Move either left or right;
** Change the state the machine is in.
* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.
** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].

== Examples ==

The following machine is the longest-running 2-symbol 2-state Turing machine. It terminates after 6 steps.

{| class="wikitable"
|+ BB(2) champion
|-
| || '''0''' || '''1'''
|-
| '''A''' || 1RB || 1LB
|-
| '''B''' || 1LA || 1RZ
|}

The computation proceeds as follows:
<pre>
0. 000 A[0] 000
1. 0001 B[0] 00
2. 000 A[1] 100
3. 00 B[0] 1100
4. 0 A[0] 11100
5. 01 B[1] 1100
6. 011 Z[1] 100
</pre>

== Standard text format ==

To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>
The format supports Turing machines with up to 25 states and up to 10 symbols.
As an example, the BB(2) champion listed above would be specified as <code>1RB1LB_1LA1RZ</code>. A full specification of the format follows.

* Symbols are represented by digits, starting from <code>0</code>
* States are represented by letters, starting from <code>A</code>
* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
* Halting transitions can be represented by any listing as the next state any capital letter larger than the number of states, but use of <code>H</code> or <code>Z</code> is encouraged for readability.
* Undefined transitions are represented as <code>---</code>

== See also ==

* [[Directed head notation]]

== References ==
<references />

Turing machine

2024-06-12T22:14:59Z

Mei:

Turing machine

2024-06-12T15:10:05Z

Mei: /* Standard text format */

'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref>
As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors.
In the Busy Beaver space, the following conventions has been adopted:
* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.
* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.
* The machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
** Replace the symbol it has read with a possibly different one;
** Move either left or right;
** Change the state the machine is in.
* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.
** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].

== Examples ==

The following machine is the longest-running 2-symbol 2-state Turing machine. It terminates after 6 steps.

{| class="wikitable"
|+ BB(2) champion
|-
| || '''0''' || '''1'''
|-
| '''A''' || 1RB || 1LB
|-
| '''B''' || 1LA || 1RZ
|}

The computation proceeds as follows:
<pre>
0. 000 A[0] 000
1. 0001 B[0] 00
2. 000 A[1] 100
3. 00 B[0] 1100
4. 0 A[0] 11100
5. 01 B[1] 1100
6. 011 Z[1] 100
</pre>

== Standard text format ==

To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>
The format supports Turing machines with up to 25 states and up to 10 symbols.
As an example, the BB(2) champion listed above would be specified as <code>1RB1LB_1LA1RZ</code>. A full specification of the format follows.

* Symbols are represented by digits, starting from <code>0</code>
* States are represented by letters, starting from <code>A</code>
* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
* Halting transitions can be represented by any listing as the next state any capital letter larger than the number of states, but use of <code>H</code> or <code>Z</code> is encouraged for readability.
* Undefined transitions are represented as <code>---</code>

== Directed-head formulation ==

TODO

== References ==
<references />

Turing machine

2024-06-12T14:51:54Z

Mei: Add a simple example

Turing machine

2024-06-12T14:34:13Z

Mei: Create an initial draft for the Turing machine page

Cryptids

2024-06-12T12:53:24Z

Mei: Remove placeholder "Caption text"

'''Cryptids''' are Turing Machines whose behavior (when started on a blank tape) can be described completely by a relatively simple mathematical rule, but where that rule falls into a class of unsolved (and presumed hard) mathematical problems. This definition is somewhat subjective (What counts as a simple rule? What counts as a hard problem?). In practice, most currently known Cryptids have [[Collatz-like]] behavior. In other words, the halting problem from blank tape of cryptids is mathematically-hard.

If there exists a Cryptid with n states and m symbols, then BB(n, m) cannot be solved without solving this hard math problem.

The name Cryptid was proposed by Shawn Ligocki in an Oct 2023 [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html blog post] announcing the first discovered Cryptid, called Bigfoot.

== List of Cryptids ==

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
|RH
|BB(744)
|https://github.com/sorear/metamath-turing-machines/blob/master/riemann-matiyasevich-aaronson.nql
|
|2016
|Matiyasevich and O’Rear
|The machine halts if and only if [https://en.wikipedia.org/wiki/Riemann_hypothesis Riemann Hypothesis] is false.
|-
|Goldbach
|BB(27)
|https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6<nowiki/>(unverified)
|
|2016
|anonymous
|The machine halts if and only if [https://en.wikipedia.org/wiki/Goldbach%27s_conjecture Golbach's conjecture] is false. To the best of our knowledge this construction has not been independently verified.
|-
| Erdős || BB(5,4) and
BB(15)
|
https://docs.bbchallenge.org/other/powers_of_two_5_4.txt

https://docs.bbchallenge.org/other/powers_of_two_15_2.txt
|| [https://arxiv.org/abs/2107.12475 arxiv preprint] || Jul 2021 || Tristan Stérin (<code>@cosmo</code>) and Damien Woods || The machine halts if and only if the following conjecture by Erdős is false: "For all n > 8, there is at least one 2 in the base-3 representation of 2^n"
|-
|Weak Collatz
|BB(124) and BB(43,4)
|https://docs.bbchallenge.org/other/weak_Collatz_conjecture_124_2.txt (unverified)
https://docs.bbchallenge.org/other/weak_Collatz_conjecture_43_4.txt (unverified)
|
|Jul 2021
|Tristan Stérin
|The machine halts if and only if the "weak Collatz conjecture" is false. The weak Collatz conjecture states that the iterated Collatz map (3x+1) has only one cycle on the positive integers.
Not independently verified, and probably easy to further optimise.
|-
| Bigfoot || [[BB(3, 3)]]|| <code>1RB2RA1LC_2LC1RB2RB_---2LA1LA</code>|| [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is hard] || Nov 2023 || [[User:Sligocki|Shawn Ligocki]] ||
|-
| Hydra || [[BB(2, 5)]]|| <code>1RB3RB---3LA1RA_2LA3RA4LB0LB0LA</code>|| [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is hard] || May 2024 || Daniel Yuan ||
|-
| || BB(2, 5) || <code>1RB3RB---3LA1RA_2LA3RA4LB0LB1LB</code>||[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid A Bonus Cryptid] || May 2024 || Daniel Yuan ||
|-
| || [[BB(7, 2)]]|| <code>0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB</code>|| [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-2140887228 Bigfoot Comment] || June 2024 || <code>@Iijil1</code>|| Compilation of Bigfoot into 2 symbols, there was a previous compilation [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-1774200442 with 8 states]
|-
| || BB(10, 2) || <code>0RE1RG_1RH0LD_0LA0LF_0LB1LJ_1RB1RA_1RE1LC_0LF---_1LF0LI_0LD0LC_1RE0RH</code>|| [https://discord.com/channels/960643023006490684/1084047886494470185/1247560072427474955 Discord message] || June 2024 || Daniel Yuan || Compilation of Hydra into 2 symbols
|}

== Beeping Busy Beaver ==

Cryptids were actually noticed in the [[Beeping Busy Beaver]] problem before they were in the classic Busy Beaver. See [https://www.sligocki.com/2022/04/03/mother-of-giants.html Mother of Giants] describing a "family" of Turing machines which "probviously" quasihalt, but requires solving a Collatz-like problem in order to actually prove it. They are all TMs formed by filling in the missing transition in <code>1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA</code> with different values.

Main Page

2024-06-11T12:09:18Z

Mei: mark BB parameters that inherit cryptids with a light orange

The [[Busy Beaver function]] BB (called S originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 <ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref> for 2-symbol [[Turing machines]] and later generalised<ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref> to m-symbol Turing machines:

{| class="wikitable"
|-
| BB(n,m) = Maximum number of steps done by a halting m-symbol Turing machine with n states starting from all-0 memory tape
|}

The busy beaver function is not computable and, few of its values are known:

{| class="wikitable"
|+ Small busy beaver values <ref>https://bbchallenge.org/~pascal.michel/ha.html</ref> <ref name=":0">https://bbchallenge.org/</ref>
|-
| || 2-state || 3-state || 4-state || 5-state || 6-state
|-
| 2-symbol
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| [[BB(6)]] > <math>10 \uparrow \uparrow 15</math>
|-
| 3-symbol || [[BB(2,3)]] = 38
| style="background: orange;" | [[BB(3,3)]] > <math>10^{17}</math>
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>10^{14072}</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
| 4-symbol
| [[BB(2,4)]] = 3,932,964
| style="background: #ffe4b2;" | [[BB(3,4)]] > 2(^15)5 + 14
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
| 5-symbol
| style="background: orange;" | [[BB(2,5)]] > 6.5 × <math>10^{38033}</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |

|}

In the above table, cells are highlighted in orange when there are known [[Cryptids]] (mathematically-hard machines) in that class.

=== [[bbchallenge.org]] ===

[[bbchallenge.org]] <ref name=":0" /> is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:

* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])
* Maintaining lists of [[Holdouts]] for small busy beaver values
* Proving the behavior of [[Individual Machines]]
* Finding [[Cryptids]] (mathematically-hard machines)
* Building [[Accelerators]] to simulate halting machines faster

Notably, as part of [[bbchallenge.org]], in June 2024 the 5th busy beaver value [[BB(5)]] was proven in Coq to be equal to the lower bound found in 1989<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>: 47,176,870.

==Notes==
<references />