BusyBeaverWiki - User contributions [en]

User:ISquillante

2026-02-10T11:23:51Z

ISquillante: Blanked the page

Rate of tape growth

2025-06-06T23:43:54Z

ISquillante:

The '''rate of tape growth''' of a given [[Turing machine]] (also called the '''order''' of the Turing machine), written <math>G_T</math>, is a function which inputs a positive integer <math>n</math> and outputs the number of cells which have been read by the head at least once up to the first <math>n</math> transitions.

Rates of tape growths are usually denoted using [//en.wikipedia.org/wiki/Big_O_notation| big O notation], as finding closed form generating functions for <math>G_T(n)</math> can be difficult and is not always of interest.

The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.

Another tape growth function, the '''rate of strict tape growth''' <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bounded from above by <math>G_T(n)</math>.

User:ISquillante

2025-06-06T22:45:38Z

ISquillante: /* Formal definition */

'''Isis Squillante'''

Discord: @isisoftheeast

E-Mail: isissquillante@gmail.com

Drafts below.

=Quasicycler=
A '''quasicycler''' is a Turing machine which is neither a [[cycler]] nor a [[translated cycler]] but cycles through states periodically.

==Formal definition==
A ''quasicycler'' or ''quasicyclic Turing machine'' <math>\tau</math> is a Turing machine which has the following two properties:
# There exists some natural number <math>p\ge1</math> such that for all sufficiently large <math>N</math>, the current state of <math>\tau</math> after <math>N</math> transitions is identical to the current state of <math>\tau</math> after <math>N+p</math> transitions. <math>p</math> is called the ''period length'' of <math>\tau</math>.
# There is no natural number <math>x\ge1</math> such that for all sufficiently large <math>N</math>, the <math>N</math>-th transition is identical to the <math>N+px</math>-th transition.
This second property is what distinguishes quasicyclers from translated cyclers; translated cyclers are defined by the negation of the second property of quasicyclers.

==Properties==
For any quasicyclic Turing machine with preperiod of length <math>r</math> and period of length <math>p</math>, its [[Rate of tape growth|rate of strict tape growth]] <math>\gamma(x)</math> is bounded above by <math>\frac p2\sqrt{x}+\frac r3</math>.

User:ISquillante

2025-06-06T22:39:38Z

ISquillante:

'''Isis Squillante'''

Discord: @isisoftheeast

E-Mail: isissquillante@gmail.com

Drafts below.

=Quasicycler=
A '''quasicycler''' is a Turing machine which is neither a [[cycler]] nor a [[translated cycler]] but cycles through states periodically.

==Formal definition==
A ''quasicycler'' or ''quasicyclic Turing machine'' <math>\tau</math> is a Turing machine which has the following two properties:
# There exists some natural number <math>p\ge1</math> such that for all sufficiently large <math>N</math>, the current state of <math>\tau</math> after <math>N</math> transitions is identical to the current state of <math>\tau</math> after <math>N+p</math> transitions. <math>p</math> is called the ''period length'' of <math>\tau</math>.
# There is no natural number <math>x\ge1</math> such that for all sufficiently large <math>N</math>, the <math>N</math>-th transition is identical to the <math>N+px</math>-th transition.
==Properties==
For any quasicyclic Turing machine with preperiod of length <math>r</math> and period of length <math>p</math>, its [[Rate of tape growth|rate of strict tape growth]] <math>\gamma(x)</math> is bounded above by <math>\frac p2\sqrt{x}+\frac r3</math>.

Rate of tape growth

2025-06-06T22:16:48Z

ISquillante:

Rate of tape growth

2025-06-06T21:29:21Z

ISquillante: Add and fix whatever information you can. If someone knows citations, please add one for the O(n/log n) conj., thank you.

The '''rate of tape growth''' of a given [[Turing machine]] (also called the '''order''' of the Turing machine), written <math>G_T</math>, is a function which inputs a positive integer <math>n</math> and outputs the number of cells which have been read by the head at least once up to the first <math>n</math> transitions.

Rates of tape growths are usually denoted using [//en.wikipedia.org/wiki/Big_O_notation| big O notation], as finding closed form generating functions for <math>G_T(n)</math> can be difficult and is not always of interest.

The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.

Another tape growth function, <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bound from above by <math>G_T(n)</math>.

2025-05-29T19:00:31Z

ISquillante: /* Definitions */

A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}
c(2k) & = & k \\
c(2k+1) & = & 3k+2 \\
\end{array}</math>

A '''Collatz-like problem''' is a question about the behavior of iterating a Collatz-like function. Collatz-like problems are famously difficult.

Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.

== Definitions ==
An <math>n</math>-ary '''Collatz-like function''' is a partial function <math>f:\mathbb{Z}^n\hookrightarrow\mathbb{Z}^n</math> of the form

<math display="block">
f(t_1,t_2,\dots,t_n)=
\begin{cases}
(P_1(t_1),P_2(t_2),\dots,P_n(t_n)) & t_1\equiv 0\mod z\\
(P_{n+1}(t_1),P_{n+2}(t_2),\dots,P_{2n}(t_n)) & t_1\equiv 1\mod z\\
\quad\quad\quad\quad\quad\quad\quad\quad\vdots & \quad\quad\quad\vdots\\
(P_{nz-n+1}(t_1),\dots,P_{nz}(t_n)) & t_1\equiv -1\mod z,
\end{cases} </math>
where <math>z</math> is a positive integer and <math>P_1,P_2,\dots,P_{nz}</math> are (not necessarily distinct) polynomials with rational coefficients. This definition is often restricted to those polynomials of degree one.

For any given <math>n</math>-ary Collatz-like function <math>g</math> and some two indexed series of subsets <math>\{S_1,S_2,\dots,S_n\},\{T_1,T_2,\dots,T_n\}</math> of the integers, we can write a well-formed formula which states

<math display="block">
\forall \sigma \in \prod_{i=1}^n S_i\exists\tau\in\prod_{i=1}^nT_i\exists x.g^{\circ x}(\sigma)=\tau
</math>

where <math>g^{\circ x}(\sigma)</math> is the <math>x</math>-th iterate of <math>g</math> on <math>\sigma</math>. Proving or disproving a formula of the above form is a '''Collatz-like problem.'''

Many [[cryptids]] exhibit '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function. For example, [[Antihydra]]'s halting status is directly related to the truth value of <math>\exists x\in\mathbb{N}\times\mathbb{Z}^-\exists n.A^{\circ n}(8,0)=x</math> where

<math display="block">
A(x,y)=
\begin{cases}
(\frac{3}{2}x,y+2) & x\equiv 0\mod 2\\
(\frac{3}{2}x-\frac{1}{2},y-1) & x\equiv 1\mod 2.
\end{cases}</math>

== Examples ==

=== BB(5,2) Champion ===
Consider the [[5-state busy beaver winner|BB(5,2) Champion]] and the generalized configuration:

<math display="block">M(n) = 0^\infty \; \textrm{<A} \; 1^n \; 0^\infty</math>Pascal Michel showed that:

<math display="block">\begin{array}{lcl}
0^\infty \; \textrm{<A} \; 0^\infty & = & M(0) \\
M(3k) & \xrightarrow{5 k^2 + 19 k + 15} & M(5k+6) \\
M(3k+1) & \xrightarrow{5 k^2 + 25 k + 27} & M(5k+9) \\
M(3k+2) & \xrightarrow{6k +12} & 0^\infty \;\; 1 \;\; \textrm{H>} \;\; 01 \;\; {(001)}^{k+1} \;\; 1 \;\; 0^\infty \\
\end{array}</math>

Starting on a blank tape <math>M(0)</math>, these rules iterate 15 times before reaching the halt config.<ref>[https://bbchallenge.org/~pascal.michel/beh#tm52a Pascal Michel's Analysis of the BB(5, 2) Champion]</ref>

=== Hydra ===
Consider [[Hydra]] (a [[Cryptids|Cryptid]]) and the generalized configuration:

<math display="block">C(a, b) = 0^\infty \; \textrm{ <B } \; 0^{3(a-2)} \; 3^b \; 2 \; 0^\infty</math>
Daniel Yuan showed that:<math display="block">\begin{array}{l}
\\
0^\infty \; \textrm{A>} \; 0^\infty & & \xrightarrow{19} & C(3, 0) \\
C(2n, & 0) & \to & \text{Halt}(9n-6) \\
C(2n, & b+1) & \to & C(3n, & b) \\
C(2n+1, & b) & \to & C(3n+1, & b+2) \\
\end{array}</math>

Where <math>\textrm{Halt}(n)</math> is a halting configuration with <math>n</math> non-zero symbols on the tape.

Starting from config <math>C(3, 0)</math> this simulates a pseudo-random walk along the <math>b</math> parameter, increasing it by 2 every time <math>a</math> is odd, decreasing by 1 every time it's even. Deciding whether or not Hydra halts requires being able to prove a detailed question about the trajectory of the Collatz-like function<math display="block">\begin{array}{l}
h(2n) & = & 3n \\
h(2n+1) & = & 3n+1 \\
\end{array}</math>starting from 3:

<math display="block">\begin{array}{l}
\\
3 \xrightarrow{O} 4 \xrightarrow{E} 6\xrightarrow{E} 9 \xrightarrow{O} 13 \xrightarrow{O} 19 \xrightarrow{O} 28 \xrightarrow{E} 42 \xrightarrow{E} 63 \cdots \\
\end{array}
</math>

Specifically, will it ever reach a point where the cumulative number of <code>E</code> (even transitions) applied is greater than twice the number of <code>O</code> (odd transitions) applied?<ref>Shawn Ligocki. [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)]. 10 May 2024.</ref>

=== Tetration Machine ===
Consider the current [[1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|BB(6,2) Champion]] (discovered by Pavel Kropitz in May 2022) and consider the general configuration:<math display="block">K(n) = 0^\infty \; 1 \; 0^n \; 11 \; 0^5 \; \textrm{C>} \; 0^\infty</math>Shawn Ligocki showed that:
<math display="block">\begin{array}{l}
\\
0^\infty \; \textrm{A>} \; 0^\infty & \xrightarrow{45} & K(5) \\
K(4k) & \to & \text{Halt}(\frac{3^{k+3} - 11}{2}) \\
K(4k+1) & \to & K(\frac{3^{k+3} - 11}{2}) \\
K(4k+2) & \to & K(\frac{3^{k+3} - 11}{2}) \\
K(4k+3) & \to & K(\frac{3^{k+3} + 1}{2}) \\
\end{array}</math>

Starting from config <math>K(5)</math>, these rules iterate 15 times before reaching the halt config leaving over <math>10 \uparrow\uparrow 15</math> non-zero symbols on the tape.<ref>Shawn Ligocki. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15]. 21 Jun 2022.</ref>

== References ==
<references />
[[Category:Zoology]]

Collatz-like

2025-05-29T18:58:51Z

ISquillante: Added precise definition of a Collatz-like function.

A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}
c(2k) & = & k \\
c(2k+1) & = & 3k+2 \\
\end{array}</math>

A '''Collatz-like problem''' is a question about the behavior of iterating a Collatz-like function. Collatz-like problems are famously difficult.

Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.

== Definitions ==
An <math>n</math>-ary '''Collatz-like function''' is a partial function <math>f:\mathbb{Z}^n\hookrightarrow\mathbb{Z}^n</math> of the form

<math display="block">
f(t_1,t_2,\dots,t_n)=
\begin{cases}
(P_1(t_1),P_2(t_2),\dots,P_n(t_n)) & t_1\equiv 0\mod z\\
(P_{n+1}(t_1),P_{n+2}(t_2),\dots,P_{2n}(t_n)) & t_1\equiv 1\mod z\\
\quad\quad\quad\quad\quad\quad\quad\quad\vdots & \quad\quad\quad\vdots\\
(P_{nz-n+1}(t_1),\dots,P_{nz}(t_n)) & t_1\equiv -1\mod z,
\end{cases} </math>
where <math>z</math> is a positive integer and <math>P_1,P_2,\dots,P_{nz}</math> are (not necessarily distinct) polynomials with rational coefficients. This definition is often restricted to those polynomials of degree one.

For any given <math>n</math>-ary Collatz-like function <math>g</math> and some two indexed series of subsets <math>\{S_1,S_2,\dots,S_n\},\{T_1,T_2,\dots,T_n\}</math> of the integers, we can write a well-formed formula which states

<math display="block">
\forall \sigma \in \prod_{i=1}^n S_i\exists\tau\in\prod_{i=1}^nT_i\exists x.g^{\circ x}(\sigma)=\tau
</math>

where <math>g^{\circ x}(\sigma)</math> is the <math>x</math>-th iterate of <math>g</math> on <math>\sigma</math>. Proving or disproving a formula of the above form is a '''Collatz-like problem.'''

Many [[cryptids]] exhibit '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function. For example, [[Antihydra]]'s halting status is directly related to the truth value of <math>\exists x\in\mathbb{N}\times\mathbb{Z}^-\exists n.A(8,0)=x</math> where

<math display="block">
A(x,y)=
\begin{cases}
(\frac{3}{2}x,y+2) & x\equiv 0\mod 2\\
(\frac{3}{2}x-\frac{1}{2},y-1) & x\equiv 1\mod 2.
\end{cases}</math>

== Examples ==

=== BB(5,2) Champion ===
Consider the [[5-state busy beaver winner|BB(5,2) Champion]] and the generalized configuration:

<math display="block">M(n) = 0^\infty \; \textrm{<A} \; 1^n \; 0^\infty</math>Pascal Michel showed that:

<math display="block">\begin{array}{lcl}
0^\infty \; \textrm{<A} \; 0^\infty & = & M(0) \\
M(3k) & \xrightarrow{5 k^2 + 19 k + 15} & M(5k+6) \\
M(3k+1) & \xrightarrow{5 k^2 + 25 k + 27} & M(5k+9) \\
M(3k+2) & \xrightarrow{6k +12} & 0^\infty \;\; 1 \;\; \textrm{H>} \;\; 01 \;\; {(001)}^{k+1} \;\; 1 \;\; 0^\infty \\
\end{array}</math>

Starting on a blank tape <math>M(0)</math>, these rules iterate 15 times before reaching the halt config.<ref>[https://bbchallenge.org/~pascal.michel/beh#tm52a Pascal Michel's Analysis of the BB(5, 2) Champion]</ref>

=== Hydra ===
Consider [[Hydra]] (a [[Cryptids|Cryptid]]) and the generalized configuration:

<math display="block">C(a, b) = 0^\infty \; \textrm{ <B } \; 0^{3(a-2)} \; 3^b \; 2 \; 0^\infty</math>
Daniel Yuan showed that:<math display="block">\begin{array}{l}
\\
0^\infty \; \textrm{A>} \; 0^\infty & & \xrightarrow{19} & C(3, 0) \\
C(2n, & 0) & \to & \text{Halt}(9n-6) \\
C(2n, & b+1) & \to & C(3n, & b) \\
C(2n+1, & b) & \to & C(3n+1, & b+2) \\
\end{array}</math>

Where <math>\textrm{Halt}(n)</math> is a halting configuration with <math>n</math> non-zero symbols on the tape.

Starting from config <math>C(3, 0)</math> this simulates a pseudo-random walk along the <math>b</math> parameter, increasing it by 2 every time <math>a</math> is odd, decreasing by 1 every time it's even. Deciding whether or not Hydra halts requires being able to prove a detailed question about the trajectory of the Collatz-like function<math display="block">\begin{array}{l}
h(2n) & = & 3n \\
h(2n+1) & = & 3n+1 \\
\end{array}</math>starting from 3:

<math display="block">\begin{array}{l}
\\
3 \xrightarrow{O} 4 \xrightarrow{E} 6\xrightarrow{E} 9 \xrightarrow{O} 13 \xrightarrow{O} 19 \xrightarrow{O} 28 \xrightarrow{E} 42 \xrightarrow{E} 63 \cdots \\
\end{array}
</math>

Specifically, will it ever reach a point where the cumulative number of <code>E</code> (even transitions) applied is greater than twice the number of <code>O</code> (odd transitions) applied?<ref>Shawn Ligocki. [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)]. 10 May 2024.</ref>

=== Tetration Machine ===
Consider the current [[1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|BB(6,2) Champion]] (discovered by Pavel Kropitz in May 2022) and consider the general configuration:<math display="block">K(n) = 0^\infty \; 1 \; 0^n \; 11 \; 0^5 \; \textrm{C>} \; 0^\infty</math>Shawn Ligocki showed that:
<math display="block">\begin{array}{l}
\\
0^\infty \; \textrm{A>} \; 0^\infty & \xrightarrow{45} & K(5) \\
K(4k) & \to & \text{Halt}(\frac{3^{k+3} - 11}{2}) \\
K(4k+1) & \to & K(\frac{3^{k+3} - 11}{2}) \\
K(4k+2) & \to & K(\frac{3^{k+3} - 11}{2}) \\
K(4k+3) & \to & K(\frac{3^{k+3} + 1}{2}) \\
\end{array}</math>

Starting from config <math>K(5)</math>, these rules iterate 15 times before reaching the halt config leaving over <math>10 \uparrow\uparrow 15</math> non-zero symbols on the tape.<ref>Shawn Ligocki. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15]. 21 Jun 2022.</ref>

== References ==
<references />
[[Category:Zoology]]