BusyBeaverWiki - User contributions [en]

Busy beaver lack of hope recurrence

2024-09-27T10:18:10Z

Bt2901:

People working on BB(n-1) believed BB(n) was impossible:

== BB(3) ==
'''1.5th-hand report:''' "Suppose that, just to gain experience, we simplify the situation by merely asking whether a given 3-card machine will ever stop if started (with its card 1) on an all-zero tape. This particular question has been studied extensively by the authors in connection with the subject of sequential circuits. Many computer programs were written to answer this question; these programs grew larger and larger as more and more criteria for stoppers were covered. These programs were the results of co-operative efforts of experienced mathematicians and skilled programmers, and were run on some of the finest existing computers. Yet this extremely primitive-looking problem was still unsolved when this paper was presented, and '''probably most of the participants in the studies felt that perhaps it would always remain so'''. But since then, this problem has been solved by T. Rado and one of his graduate students, S. Lin."

Source: R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

== BB(3) to BB(4) ==
'''Second-hand report:''' "In any case, even though skilled mathematicians and experienced programmers attempted to evaluate S(3) and Σ(3), there is no evidence that any known approach will yield the answer, even if we avail ourselves of high-speed computers and elaborate programs. As regards Σ(4), S(4), the situation seems to be entirely hopeless at present."—Tibor Rado, 1963.

Source: Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.

== BB(4) to BB(5) ==
'''Second-hand report:''' "Brady predicted that there will never be a proof of the values of Sigma(5) and S(5). We are just slightly more optimistic, and are lead to recast a parable due to Erdos (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless."

Source: From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html

'''Original source:''' 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), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024

[[File:BradyBB(5)isHopeless.png|alt=Allen H. Brady (who proved BB(4) = 107) is saying that ever proving BB(5) is unlikely|thumb|Original source where Allen H. Brady says that solving BB(5) rigorously is unlikely to happen.]]

== BB(5) ==
=== Brady on level of intelligence required ===
Even though it might appear now that the five-state problem is within grasp, there is a distinct possibility that the limit of practical solvability has in fact been reached. While we can follow Uhing's current champion machines [resp. σ = 1,915, s = 2,133,492, and σ = 1,471, s = 2,358,064] until they halt, it is not clear at all how the machines work. Any cleverness in their construction is not the result of human creation, so there is a conspicuous absence of documentation! In light of Green's results it was easy to accept that the turning point for the Busy Beaver Game might occur at k = 6, but such magnitudes as have now been produced for k = 5 had never been anticipated. Any hope for solving the problem at this level will require computer programs endowed with a level of intelligence that we have not seen in anything done previously by a machine. Can it be decided by a computer program or will it be necessary to assign one mathematician per unresolved five-state Turing Machine?

Source: Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life"

=== Brady's Prediction 5 ===
''Prediction 5.'' It will never be proved that S(5) = 1,915 and Σ(5) = 2,358,064. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.)

Reason: Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the ''Goldbach Conjecture''. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.

Source: Allen Brady, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252

== BB(6) ==
=== Brady's Prediction 6 ===

''Prediction 6.'' From known results for k = 5 a six-state machine will be constructed for which it can be "proved" that its shift number (and thus a lower bound for S(6)) is an incomprehensibly large value which is in itself difficult to describe.

Reason: It is now clear that determining Σ(6) and S(6) is intractable. At this level one can speculate with impunity, and we shall.

Some students of the author were readily convinced after extensive examination and computer testing that Uhing's champion machine for S(5) would never halt. Seeking assurance one student ran her simulator to a point just short of two million moves! From an amusing experience such as this, one is led to consider the possibility that someday a machine of six states (or a just a few more) will be presented by a group of mathematicians along with a "proof" that it will never halt. Suppose then an efficient simulator for the machine were built on the leading but slightly jagged edge of technology and run for an extensive period of time. And then suppose it were to halt! The mathematicians, with solid reasoning to back them up, could make a valid claim that the machine malfunctioned.

But now suppose that instead of building a machine, another group of equivalently qualified thinkers, supported by a great body of mathematical knowledge, countered with a different "proof" that after some unimaginable number of moves the proposed machine would in fact halt. Their number would be so large that building a simulator to check the result would be inconceivable. What then? (It is only speculation, of course!)

For k = 6 the problem transcends mechanism. One reaches a point where it becomes impossible to distinguish between the finite and the infinite. Is there a point at which it will transcend logic? Rado's question remains open.

== BB(1963) ==

Should one attempt to apply the method described above to the problem BB-1963, for example, then difficulties of prohibitive character are bound to arise. In the first place, the number of cases becomes astronomical, and the storage and execution for the computer programs involved will defeat any efforts to use existing computers. Even if we assume that somehow we managed to squeeze through the computer the portion of our approach involving partial recurrence patterns, the number of "holdouts" may be expected to be enormous. Over and beyond such "physical" difficulties, there is the basic fact of the non-computability of Σ(n), which implies that no single finite computer program exists that will furnish the value of Σ(n) for every n. Accordingly, there seems to be at present no justification for the assumption that Σ(n) is effectively calculable for each individual n. Evidently, these comments suggests a number of questions relating to the BB-n problem which seem to be beyond the reach of presently known methods, Thus it appears that clarification of the idea of a "given" non-negative integer may be a fruitful and certainly difficult enterprise.

Lin, 1963, "Computer Studies of Turing Machine Problems" (a PhD dissertation)

Busy beaver lack of hope recurrence

2024-09-27T10:10:09Z

Bt2901:

People working on BB(n-1) believed BB(n) was impossible:

== BB(3) ==
'''1.5th-hand report:''' "Suppose that, just to gain experience, we simplify the situation by merely asking whether a given 3-card machine will ever stop if started (with its card 1) on an all-zero tape. This particular question has been studied extensively by the authors in connection with the subject of sequential circuits. Many computer programs were written to answer this question; these programs grew larger and larger as more and more criteria for stoppers were covered. These programs were the results of co-operative efforts of experienced mathematicians and skilled programmers, and were run on some of the finest existing computers. Yet this extremely primitive-looking problem was still unsolved when this paper was presented, and '''probably most of the participants in the studies felt that perhaps it would always remain so'''. But since then, this problem has been solved by T. Rado and one of his graduate students, S. Lin."

Source: R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

== BB(3) to BB(4) ==
'''Second-hand report:''' "In any case, even though skilled mathematicians and experienced programmers attempted to evaluate S(3) and Σ(3), there is no evidence that any known approach will yield the answer, even if we avail ourselves of high-speed computers and elaborate programs. As regards Σ(4), S(4), the situation seems to be entirely hopeless at present."—Tibor Rado, 1963.

Source: Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.

== BB(4) to BB(5) ==
'''Second-hand report:''' "Brady predicted that there will never be a proof of the values of Sigma(5) and S(5). We are just slightly more optimistic, and are lead to recast a parable due to Erdos (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless."

Source: From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html

'''Original source:''' 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), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024

[[File:BradyBB(5)isHopeless.png|alt=Allen H. Brady (who proved BB(4) = 107) is saying that ever proving BB(5) is unlikely|thumb|Original source where Allen H. Brady says that solving BB(5) rigorously is unlikely to happen.]]

== BB(5) ==
=== Brady on level of intelligence required ===
Even though it might appear now that the five-state problem is within grasp, there is a distinct possibility that the limit of practical solvability has in fact been reached. While we can follow Uhing's current champion machines [resp. σ = 1,915, s = 2,133,492, and σ = 1,471, s = 2,358,064] until they halt, it is not clear at all how the machines work. Any cleverness in their construction is not the result of human creation, so there is a conspicuous absence of documentation! In light of Green's results it was easy to accept that the turning point for the Busy Beaver Game might occur at k = 6, but such magnitudes as have now been produced for k = 5 had never been anticipated. Any hope for solving the problem at this level will require computer programs endowed with a level of intelligence that we have not seen in anything done previously by a machine. Can it be decided by a computer program or will it be necessary to assign one mathematician per unresolved five-state Turing Machine?

Source: Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life"

=== Brady's Prediction 5 ===
''Prediction 5.'' It will never be proved that S(5) = 1,915 and Σ(5) = 2,358,064. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.)

''Reason:'' Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.

Source: Allen Brady, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252

== BB(6) ==
=== Brady's Prediction 6 ===

''Prediction 6.'' From known results for k = 5 a six-state machine will be constructed for which it can be "proved" that its shift number (and thus a lower bound for S(6)) is an incomprehensibly large value which is in itself difficult to describe.

''Reason:'' It is now clear that determining Σ(6) and S(6) is intractable. At this level one can speculate with impunity, and we shall.

Some students of the author were readily convinced after extensive examination and computer testing that Uhing's champion machine for S(5) would never halt. Seeking assurance one student ran her simulator to a point just short of two million moves! From an amusing experience such as this, one is led to consider the possibility that someday a machine of six states (or a just a few more) will be presented by a group of mathematicians along with a "proof" that it will never halt. Suppose then an efficient simulator for the machine were built on the leading but slightly jagged edge of technology and run for an extensive period of time. And then suppose it were to halt! The mathematicians, with solid reasoning to back them up, could make a valid claim that the machine malfunctioned.

But now suppose that instead of building a machine, another group of equivalently qualified thinkers, supported by a great body of mathematical knowledge, countered with a different "proof" that after some unimaginable number of moves the proposed machine would in fact halt. Their number would be so large that building a simulator to check the result would be inconceivable. What then? (It is only speculation, of course!)

For k = 6 the problem transcends mechanism. One reaches a point where it becomes impossible to distinguish between the finite and the infinite. Is there a point at which it will transcend logic? Rado's question remains open.

Busy beaver lack of hope recurrence

2024-09-26T22:22:04Z

Bt2901: /* BB(3) to BB(4) */

People working on BB(n-1) believed BB(n) was impossible:

== BB(2) to BB(3) ==
'''Second-hand report:''' "Suppose that, just to gain experience, we simplify the situation by merely asking whether a given 3-card machine will ever stop if started (with its card 1) on an all-zero tape. This particular question has been studied extensively by the authors in connection with the subject of sequential circuits. Many computer programs were written to answer this question; these programs grew larger and larger as more and more criteria for stoppers were covered. These programs were the results of co-operative efforts of experienced mathematicians and skilled programmers, and were run on some of the finest existing computers. Yet this extremely primitive-looking problem was still unsolved when this paper was presented, and '''probably most of the participants in the studies felt that perhaps it would always remain so'''. But since then, this problem has been solved by T. Rado and one of his graduate students, S. Lin."

Source: R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

== BB(3) to BB(4) ==
'''Second-hand report:''' "In any case, even though skilled mathematicians and experienced programmers attempted to evaluate S(3) and Σ(3), there is no evidence that any known approach will yield the answer, even if we avail ourselves of high-speed computers and elaborate programs. As regards Σ(4), S(4), the situation seems to be entirely hopeless at present."—Tibor Rado, 1963.

Source: Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.

== BB(4) to BB(5) ==
'''Second-hand report:''' "Brady predicted that there will never be a proof of the values of Sigma(5) and S(5). We are just slightly more optimistic, and are lead to recast a parable due to Erdos (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless."

Source: From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html

'''Original source:''' 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), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024

[[File:BradyBB(5)isHopeless.png|alt=Allen H. Brady (who proved BB(4) = 107) is saying that ever proving BB(5) is unlikely|thumb|Original source where Allen H. Brady says that solving BB(5) rigorously is unlikely to happen.]]

Busy beaver lack of hope recurrence

2024-09-26T22:18:05Z

Bt2901:

People working on BB(n-1) believed BB(n) was impossible:

== BB(2) to BB(3) ==
'''Second-hand report:''' "Suppose that, just to gain experience, we simplify the situation by merely asking whether a given 3-card machine will ever stop if started (with its card 1) on an all-zero tape. This particular question has been studied extensively by the authors in connection with the subject of sequential circuits. Many computer programs were written to answer this question; these programs grew larger and larger as more and more criteria for stoppers were covered. These programs were the results of co-operative efforts of experienced mathematicians and skilled programmers, and were run on some of the finest existing computers. Yet this extremely primitive-looking problem was still unsolved when this paper was presented, and '''probably most of the participants in the studies felt that perhaps it would always remain so'''. But since then, this problem has been solved by T. Rado and one of his graduate students, S. Lin."

Source: R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

== BB(3) to BB(4) ==
'''Second-hand report:''' "In any case, even though skilled mathematicians and experienced programmers attempted to evaluate 2(3) and 5(3), there is no evidence that any known approach will yield the answer, even if we avail ourselves of high-speed computers and elaborate programs. As regards \Sigma(4), S(4), the situation seems to be entirely hopeless at present."—Tibor Rado, 1963.

Source: Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.

== BB(4) to BB(5) ==
'''Second-hand report:''' "Brady predicted that there will never be a proof of the values of Sigma(5) and S(5). We are just slightly more optimistic, and are lead to recast a parable due to Erdos (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless."

Source: From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html

'''Original source:''' 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), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024

[[File:BradyBB(5)isHopeless.png|alt=Allen H. Brady (who proved BB(4) = 107) is saying that ever proving BB(5) is unlikely|thumb|Original source where Allen H. Brady says that solving BB(5) rigorously is unlikely to happen.]]

Fast-Growing Hierarchy Growth Bound Theorem

2024-09-14T22:11:56Z

Bt2901: Created page with "The ''Fast-Growing Hierarchy Growth Bound Theorem'' is an important result in mathematical logic that has significant implications for unprovability results. The theorem highlights a relationship between computable functions that are provably total in first-order Peano Arithmetic (PA) and the fast-growing functions in the Wainer hierarchy. The theorem is based on work by several mathematicians. Georg Kreisel laid the groundwork in 1952 by inve..."

The ''Fast-Growing Hierarchy Growth Bound Theorem'' is an important result in mathematical logic that has significant implications for unprovability results. The theorem highlights a relationship between computable functions that are provably total in first-order Peano Arithmetic (PA) and the fast-growing functions in the [[Fast-Growing Hierarchy|Wainer hierarchy]].

The theorem is based on work by several mathematicians. Georg Kreisel laid the groundwork in 1952 by investigating connections between recursions over well ordered sets and proofs in PA. These results were subsequently extended by many others; the following form is based on the presentation by Buchholz and Wainer.

== Statement ==

Let <math>T</math> be a Turing machine that computes a function <math>g:\N\to\N</math>, terminating on every input. Suppose that PA can prove the statement «<math>T</math> terminates on every input.» Then <math>g</math> cannot grow too fast: There exist <math>\alpha < \varepsilon_0</math> and <math>n_0\in\N</math> such that <math>g(n) < F_\alpha(n)</math> for every <math>n\ge n_0</math>.

== References ==
Wilfried Buchholz and Stan S. Wainer. Provably computable functions and the fast growing hierarchy. In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 179–198. AMS, 1987. [https://epub.ub.uni-muenchen.de/3843/1/3843.pdf]

[[Category:Stub]]
[[Category:Computability theory]]

Dekaheptoid

2024-09-07T22:37:01Z

Bt2901:

'''Dekaheptoid''' (from Ancient Greek word meaning "seventeen") is an informal class of Turing machines that are, in some sense, similar to [[Skelet 17]]. A typical Turing machine in this class has the following behavior:

* it works with the sequence of numbers encoded as <math>10^{k}</math> (here referred to as ''digits'').
* it spends most of its time performing an operation that could be described as incrementing/decrementing the Gray Code of the sequence
* it has a roughly cubic growth rate

The specifics can differ, but some of common tape transformations and conditions are:

* ''Increment'': the value at the last index is decremented and some other value is incremented. Typically this does not expand the tape.
* ''Halve'': the last digit (typically having a value 1 or less) is deleted.
* ''Zero'': expand the tape to the left by adding some number of leading zeros. The leftmost digit could be incremented by some small value. Typically this occurs when all digits (possibly, except for the least significant one) are even.
* ''Overflow'': incrementing the leftmost digit creates new leading zeros.
* ''Smudge'': if an "internal" (i.e. neither the first nor the last) digit is zero, increment it and decrement some digit next to it. In some cases, this leads to halting.

== State variables ==

It is useful to consider the following ''state variables'':

* Rightmost digit (denoted by <code>last</code>). The parity of <code>last</code> can be relevant, and is either 0 or 1, as calculated by <code>last % 2</code>. Possible values of <code>last</code> are all natural numbers <math>\mathbb{N} = {0,1,2,3, ...}</math> (note, however, that only <code>0</code> and <code>1</code> values affect the behaviour; everything else could be merged into a single class named <code>2+</code>)
* Gray code value (denoted by <code>grayval</code>): the integer corresponding to the Gray code bitstring obtained by calculating the parity of each number (except the last) in the list. For a list of length <math>L</math>, possible Grey code values are <math>[0, 1, 2, ..., 2^L - 1]</math>. If <code>grayval == 0</code>, all entries in the list are even, except perhaps the last one. If <code>grayval == 2^L - 1</code>, all entries in the list are odd, except perhaps the last one.
* Number of internal zeros (denoted by <code>num_internal_zero</code>).
* Number of leading zeros (denoted by <code>num_leading_zeros</code>).
* Rightmost odd index, including the last digit (denoted by <code>rightmost_odd_idx</code>). If all entries are even, it is defined as <math>-1</math> by convention.
* Rightmost odd index not counting the last digit (denoted by <code>rightmost_odd_idx_alt</code>). If all pertinent entries are even, it is defined as <math>-1</math> by convention.

Note that if <code>grayval == 0</code>, then <code>rightmost_odd_idx_alt == -1</code>, and <code>rightmost_odd_idx</code> is either 0 or L.
== 5-state dekaheptoids ==

Two notable machines are [[Skelet 17]] and {{TM|1RB1LC_1RC---_0LD1RE_0LA1LD_0RC0RB|halting}} which is equivalent to Skelet 17 starting from the state D and halts after 533 steps (29 rule applications).

== 6-state dekaheptoids ==

Known dekaheptoids fall into one of 12 equivalence classes (based on checking configurations after each rule application; two TMs are considered equivalent if their high-level configs are always equivalent during 15k+ high-level steps).

=== equivalent to skelet 17 ===
<pre>
1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0LF_0RA1RF
1RB1RF_0LC1RE_0LD1LC_1RA1LB_0RB1LA_---0RA
1RB1RF_0LC1RE_0LD1LC_1RA1LB_1LA0RA_---0RB
1RB0RA_0LC1RE_0LD1LC_1RA1LB_0RB1RF_0LA---
1RB---_0LC1RF_0LD1LC_1LE1LB_0RE1RA_0RB0RA
1RB---_0LC1RE_0LD1LC_1RA1LB_0LF0RA_0RB1RF
1RB---_0LC1RF_0LE1LD_0RD1LC_1RA1LB_0RB0RA
1RB---_0LC1RE_0LD1LC_1RA1LB_0RB1RF_0LF0RA
1RB---_0LC1RF_0LD1LC_1RE1LB_0LE1RA_0RB0RA
1RB---_0LC1RE_0LD1LC_1RA1RF_0RB0RA_0LF1LB
</pre>

The notable machine is {{TM|1RB---_0LC1RF_0LE1LD_0RD1LC_1RA1LB_0RB0RA|undecided}} that employs a different mechanism for keeping track of parity.

=== "Old Relif Orbora" family ===
<pre>
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0RB_0RB0RA
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0LB_0RB0RA
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0LD_0RB0RA
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0LF_0RB0RA
</pre>

''Rules'' (based on <code>1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0RB_0RB0RA</code>)

<pre>
last != 0 and rightmost_odd_idx > 0:
apply_increment -- the usual Gray Code increment operation.

last == 0 and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0:
apply_halve o apply_increment -- first, run an Increment operation, decreasing the last digit to fictitious value "-1"; then, delete the last digit.

last == 0 and (rightmost_odd_idx <= 0) and grayval != "2^L - 1" and num_leading_zeros != 2:
apply_halve o apply_weird_double_zero -- first, add two leading zeros, then increment the last leading zero, then delete the last digit
For example: [2, 6, 12, 24, 48, 0] -> [0, 1, 2, 6, 12, 24, 48]

grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "0" :
apply_halve o apply_zero_D -- an overflow variant (see below)

grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
apply_zero_D -- an overflow variant (see below)

grayval == '2^L - 1' and L == 1:
apply_leading_zero_increment o apply_add_one_zero o apply_overflow -- increment the leading digit, add leading zero, then add one leading zero, then increase the first non-zero digit and decrease the last digit.

grayval == "0" and ((internal_zeros_len > 0) or (num_ending_zeros > 2) or (num_leading_zeros > 0)) :
apply_halt

if the halting condition isn't met, then the either of these ones happen:
grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
apply_leading_zero_increment o apply_add_double_zero -- add two leading zeros, then increase the first non-zero digit and decrease the last digit.

grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros > 0 :
apply_halve o apply_leading_zero_increment o apply_add_double_zero -- the same as above but delete the last digit afterward

</pre>
The <code>apply_zero_D</code> operation could be written as <code>apply_increment_1N o apply_overflow</code>: increment the leading digit, add leading zero, then increase the first digit (newly added zero) and decrease the last digit.

=== "Iralic Orcora" family ===
<pre>
1RB---_0LC1RD_0LE1RD_0RC0RA_0LF1LE_1RA1LC
1RB---_0RC1RF_0LD1RF_0LE1LD_1RA1LC_0RC0RA
1RB---_0LB1RC_0RD0RA_0LE1RC_0LF1LE_1RA1LD
</pre>
''Rules'' (based on <code>1RB---_0RC1RF_0LD1RF_0LE1LD_1RA1LC_0RC0RA</code>)

<pre>
grayval == '2^L - 1' and L == 1:
apply_init -- increment the only digit and add leading zero
`gray-adic` == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
apply_zero_increment -- increase the first digit by 2 (instead of more customary 1), add leading zero, decrement the last digit
last == "2+" and rightmost_odd_idx > 0 :
apply_increment
last == '1' and grayval != '2^L - 1' and grayval != '0' :
apply_halve_and_increment o apply_increment -- apply the usual Gray Code increment, then delete the last digit and increment the new last digit by 1.
grayval == "0" and last %2 == 0 and ((internal_zeros_len == 0 and num_leading_zeros > 1) or internal_zeros_len > 0 or num_ending_zeros >= 3) :
apply_halt

if the halting condition isn't met, then the either of these ones happen:

grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
apply_zero -- increment the first digit, decrement the last digit, add two leading zeros
grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 1 :
apply_halve o apply_zero -- increment the first digit, decrement the last digit, add two leading zeros, erase the last digit (that is less than zero now)
grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 2 :
apply_weird_halve_zero_variant -- erase two last digits (that are zero), increment the first digit and the new last digit, add two leading zeros

</pre>
=== "Olaile Orcorb" family ===
<pre>
1RB1LC_1RC---_0LD1RF_0LE1RD_0LA1LE_0RC0RB
1RB1LC_1RC---_0LD1RF_0LE1LE_0LA1LE_0RC0RB
</pre>

Instead of a single Gray Code Increment, these TMs have two different increment rules: Excluding Increment and Shallow Increment. One can also analyze them as a traditional Gray Code Increment except with the parity of last digit switched.
''Rules'' (based on <code>1RB1LC_1RC---_0LD1RF_0LE1LE_0LA1LE_0RC0RB</code>)
<pre>
last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
apply_halve o apply_increment
last != "0" and rightmost_odd_idx_alt > 0 and last %2 == 1 :
apply_excluding_increment
last == "2+" and last %2 == 0 :
apply_shallow_increment

grayval == "0" and all_even == 0 :
apply_zero
grayval == '2^L - 1' and L > 1 :
apply_overflow o apply_zero_increment
rightmost_odd_idx_alt == 0 and last == '1' :
apply_overflow o apply_zero_increment

grayval == "0" and last == "0" and ((`L %2` == 0 and num_ending_zeros == L) or (internal_zeros_len > 0) or (internal_zeros_len == 0 and num_leading_zeros != -1 and (num_leading_zeros >= 3 or num_ending_zeros >= 3))) :
apply_halt

if the halting condition isn't met, then this rule applies:

L > 1 and grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros > 0 :
apply_halve o apply_zero
</pre>

=== 1RB1LC_1RC---_0LD1RE_0LA1LD_0RC1RF_0LF0RB ===
The rules aren't complete.
<pre>
last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
apply_halve o apply_increment
last != "0" and rightmost_odd_idx > 0 :
apply_increment
num_leading_zeros == 2 and last == "0" and all_even == 1 :
apply_halve o apply_weird_double_zero -- first, add two leading zeros, then increment the last leading zero, then delete the last digit

The conditions for these operations aren't described yet:
apply_zero
apply_halve o apply_zero
apply_zero_variant o apply_smudge_internal_zeros
apply_weird_double_zero o apply_halve_and_increment (a rare operation)
apply_weird_double_zero
apply_halt
</pre>
=== 1RB---_0LC1LB_1RE1LD_0LB1RF_1RD1RA_0RD0RE ===

This machine is obtained by adding a new state F to the halting config of Skelet 17. The F state mangles the left end of the tape and introduces a lot of chaos into tape evolution.

=== 1RB---_0LC1RF_0LD1LC_1RE1LB_0RE1LA_0RB0RA ===

<pre>
last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
apply_halve o apply_increment
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "0" :
apply_halve o apply_zero_D
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
apply_zero_D
last != "0" and rightmost_odd_idx > 0 :
apply_increment
grayval == "0" and last %2 == 0 and ((internal_zeros_len == 0 and num_leading_zeros > 1) or internal_zeros_len > 0 or num_ending_zeros >= 3) :
apply_halt

if the halting condition isn't met, then this rule applies:

grayval == "0" and L > 1 and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
apply_zero

The condition for this operation isn't described yet:
apply_halve o apply_zero
</pre>
=== 1RB---_0LC1RF_1RA1LD_0LE1RF_0LC1LE_0RD0RA ===

<pre>

1RB---_0LC1RF_1RA1LD_0LE1RF_0LC1LE_0RD0RA 9
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
apply_zero_D -- see above for description
last == "2+" and rightmost_odd_idx > 0 :
apply_increment
last == '1' and grayval != '2^L - 1' and grayval != '0' :
apply_halve_and_increment o apply_excluding_increment
gray == "0" and `last %2` == 0 and ((internal_zeros_len == 0 and num_leading_zeros > 1) or internal_zeros_len > 0 or num_ending_zeros >= 3) :
apply_halt

If the halting condition isn't met:
L > 1 and gray == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
apply_zero
L > 1 and gray == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 1 :
apply_halve o apply_zero
L > 1 and gray == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 2 :
apply_weird_halve_zero

The conditions for these two very rare operations aren't described yet:
apply_weird_incrementing_halve
apply_halve_and_increment o apply_zero_D
</pre>
=== 1RB---_0RC1RB_1LD1RE_1LE---_0RB1LF_0LE0LD ===

=== 1RB1LC_1RC---_0LD1RE_0LA1LD_0RF0RB_0LC1RE ===
This TM is notable, as I was unable to found any config where it would halt.

<pre>
last == "0" and (rightmost_odd_idx <= 0) and grayval != "2^L - 1" and num_leading_zeros != 2 :
apply_halve_and_increment
last == "2+" and last %2 == 0 :
apply_shallow_increment
last == "2+" and last %2 == 1 and gray != "0" :
apply_excluding_increment
last == "2+" and last %2 == 1 and gray == "0" :
apply_zero
grayval == '2^L - 1' and L > 1 :
apply_halve o apply_weird_one_zero o apply_increment_D_even o apply_weird_double_zero
last == '1' and grayval == '0' :
apply_smudge_internal_zeros o apply_zero
rightmost_odd_idx_alt == 0 and last == '1' :
apply_halve o apply_weird_one_zero o apply_increment_D_even o apply_weird_double_zero

The conditions for these operations aren't described yet:
apply_weird_incrementing_halve o apply_halve
apply_smudge_internal_zeros o apply_unsafe_increment_1N
apply_halve o apply_increment o apply_excluding_increment

</pre>
=== 1RB1LC_1RC0RF_0LD1RE_0LA1LD_0RC0RB_0RE--- ===
The rules aren't complete.
<pre>
last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
apply_halve o apply_increment
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "0" :
apply_halve o apply_zero o apply_overflow
last != "0" and rightmost_odd_idx > 0 :
apply_increment
grayval == '2^L - 1' and L > 1 :
apply_halve o apply_zero o apply_overflow

The conditions for these operations aren't described yet:
apply_zero
apply_zero_variant o apply_reverse_smudge_internal_zeros
apply_halve o apply_zero
apply_halt
</pre>

== 2-state, 5-symbol dekaheptoids ==

The {{TM|1RB3RB1LB---2RB_2LA1RA4LB2LA2RA|Undecided}} machine encodes digits as <math>4^k</math> separated by <math>12</math>. For example, {{mono|[x,y,z]}} is represented as <math>1 . Note this machine is mirrored (z is the most significant digit while x is the least significant).

The analysis by {{mono|@dyuan01}} is available [[:File:BB_2x5_Dekaheptoid_Non_Halt_Proof_Version_2_.pdf|here]].

[[Category:Stub]]
[[Category:Zoology]]

Dekaheptoid

2024-09-01T12:07:55Z

Bt2901:

Collatz-like

2024-08-25T20:49:42Z

Bt2901:

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.

== 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>C(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{ 
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]]

Translated cycler

2024-08-25T20:48:29Z

Bt2901:

[[File:Translated_cycler_44394115_annotated.svg|right|thumb|Example "Translated cycler": 45-step space-time diagram of bbchallenge's machine {{TM|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC}}. The same bounded pattern is being translated to the right forever. The text annotations illustrate the main idea for recognising "Translated Cyclers": find two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state (here state D) such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.]]

A '''translated cycler''' (also known as a '''partial recurrent''' or '''Lin recurrent''' TM) is a non-halting [[Turing machine]] which eventually exhibits a traveling cyclic behavior. Specifically, a TM has ented a translated cycle once it begins repeating a fixed sequence of transition rules in such a way that it will continue repeating them forever. It is, by far, the most common type of non-halting behavior. For example, 95% of all infinite [[BB(6)]] TMs are translated cyclers (which have cycled at least once within the first 1000 steps) and this number is relatively consistent across other BB "domains" (Say BB(5), BB(3,3), etc.).

== History ==
Translated cycling behavior was first described by Shen Lin in his proof of [[BB(3)]] where he called it "partial recurrence".<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. <nowiki>https://doi.org/10.1145/321264.321270</nowiki></ref> He describes an algorithm for detecting it which appears to be the first documented example of a [[decider]]. This behavior has been given many names over the years. For example, Nick Drozd calls this Lin recurrence in honor of Shen Lin.<ref>Nick Drozd. 2021. [https://nickdrozd.github.io/2021/02/24/lin-recurrence-and-lins-algorithm.html Lin Recurrence and Lin's Algorithm]</ref>

== Record breaking ==
One way to detect translated cycling is by analyzing [[record breaking]] configurations. This is the algorithm used by [[bbchallenge]]. A Turing machine is a translated cycler if it has two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.

Here are the properties of the translated cycler shown in the figure:

* L = 2. After the translated cycler reaches record 1, the translated cycler moves at most L = 2 symbols to the left.
* The '''cycle period''' is 10 steps. This is the number of steps from record 1 to record 2.
* The '''cycle offset''' is 2 symbols to the right. In other words, after each cycle, the TM moves 2 places to the right.
* The '''cycle start time''' is 6 steps. This is the position of record 1.

Translated cyclers are close to [[Cycler|Cyclers]] in the sense that they are only repeating a pattern but there is added complexity as they are able to translate the pattern in space at the same time, hence the decider for Cyclers cannot directly apply here.

== Infinite shift rule ==
A translated cycle can be seen as an infinite [[shift rule]]. For example, consider the TM {{TM|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC|non-halt}} in the image at the right. It performs the following [[transition rule]]:<math display="block">\begin{array}{l}
\\
10 \; \textrm{D>} \; 00 \xrightarrow{10} 00 \; 10 \; \textrm{D>} \\
\end{array}</math>

which can be repeated to form the shift rule:<math display="block">\begin{array}{l}
\\
10 \; \textrm{D>} \; {00}^n \xrightarrow{10n} {00}^n \; 10 \; \textrm{D>} \\
\end{array}</math>

Furthermore, on step 6, this TM is in config

<math display="block">0^\infty \; 1 \; 10 \; \textrm{D>} \; 0^\infty</math>

Therefore, we can see that for all <math>n \ge 0</math> we can apply the shift rule and so this TM can never halt.

== Notable translated cyclers ==

[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of at least <math>10^{24}</math>.

== Sources ==
<references />

[[Category:Zoology]]

Shift overflow counter

2024-08-25T10:47:12Z

Bt2901: Created page with "'''Shift overflow counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior: * it represents digits as short fixed-length blocks of symbols * it spends most of it's time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits * after “Counter Phase” there is a “Reset Phase” where the conte..."

'''Shift overflow counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:

* it represents digits as short fixed-length blocks of symbols
* it spends most of it's time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits
* after “Counter Phase” there is a “Reset Phase” where the contents are “reparsed”, creating a new double counter configuration. The new configuration could lead to halting.

== Examples ==
* Skelet holdouts: [[Skelet 34]], [[Skelet 33]], [[Skelet 35]], [[Skelet 15]], [[Skelet 26]]
* [https://bbchallenge.org/1RB1LD_1RC0RB_1LA0LE_1LC0LA_1RZ1RB]
* [https://bbchallenge.org/1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE 1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE]
* [https://bbchallenge.org/1RB1LD_1RC0RB_1LA1LE_1LC0LA_1RZ0RD]

== Related links ==
[https://www.sligocki.com/2023/02/02/skelet-34.html]
[https://www.sligocki.com/2023/02/05/shift-overflow.html]
[https://discuss.bbchallenge.org/t/skelet-26-and-15-do-not-halt-coq-proof/183]
[https://discuss.bbchallenge.org/t/skelet-34-and-35-coq-proof/165]
[https://discuss.bbchallenge.org/t/skelet-33-doesnt-halt-coq-proof/180]

[[Category:Stub]]
[[Category:Zoology]]

Category:Zoology

2024-08-25T10:33:57Z

Bt2901: Created blank page

Dekaheptoid

2024-08-25T10:32:22Z

Bt2901:

Sync bi-counter

2024-08-25T10:32:03Z

Bt2901:

'''Sync bi-counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:

* It has two counters on the tape, and the lowest digit of both counters are adjacent.
* In each round, both of the two counters are increased by one, and they count in the same base. Both counters count to the same number after each round (i.e. they are synchronized).

== Examples ==

* [https://bbchallenge.org/1RB0RA_0LC1RA_1RE1LD_1LC0LD_---0RB Skelet #10] ([https://www.sligocki.com/2023/03/14/skelet-10.html Proof of non-halt])
* [https://bbchallenge.org/1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA 1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA]
* [https://bbchallenge.org/1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF 1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF]

== Decider ==
For typical cases, we can fold the tape so that two counters overlap as one counter, and then it's usually decidable by CTL.

Inductive decider can deal with some more complex situations.
[[Category:Stub]]
[[Category:Zoology]]

Sync bouncer counter

2024-08-25T10:31:47Z

Bt2901:

'''Sync bouncer counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:

* It has both a bouncer and a counter on the tape, and the lowest digit of the counter is adjacent to the bouncer.
* Increment: the counter is increased by one, and the bouncer finishes a period.
* Overflow: when the counter overflows, the bouncer changes its structure (and change back before next overflow).
[https://github.com/ccz181078/busycoq/blob/BB6/verify/SBCv1.v A Coq proof of a kind of typical behavior doesn't halt.]

== Examples ==
[https://bbchallenge.org/1RB0LF_0RC---_1RD1LE_0RE0LA_1LF0RF_0LC0LB 1RB0LF_0RC---_1RD1LE_0RE0LA_1LF0RF_0LC0LB] (most common)

[https://bbchallenge.org/1RB---_0LC1RF_1LE0RD_0RB1RC_1RD0LE_0RC1RA 1RB---_0LC1RF_1LE0RD_0RB1RC_1RD0LE_0RC1RA] (complex)

[[Category:Stub]]
[[Category:Zoology]]

Shift overflow bouncer counter

2024-08-25T10:31:36Z

Bt2901:

== Definition ==
Shift overflow bouncer counter is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:
* It has both a bouncer and a counter on the tape.
* Increment: when the bouncer finish a loop, the counter is increased by one.
* Overflow: when the counter overflows, the bouncer is reset to nearly empty, and the original location of the bouncer becomes part of the counter (this is imprecise and sometimes it has more complex behavior).

== Examples ==
* [https://bbchallenge.org/1RB0RE_1LC0RA_1LD0LB_1LA0LB_1RF1RA_---0RD&s=60000&ox=0.1 1RB0RE_1LC0RA_1LD0LB_1LA0LB_1RF1RA_---0RD]
* [https://bbchallenge.org/1RB1RE_1LC---_0LD0LC_1RD0RA_1RE0RF_0LA1LD 1RB1RE_1LC---_0LD0LC_1RD0RA_1RE0RF_0LA1LD]
* [https://bbchallenge.org/1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE 1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE]
* [https://bbchallenge.org/1RB3LA3LB1RA3RA_2LA2LB---4RA4LA 1RB3LA3LB1RA3RA_2LA2LB---4RA4LA]

[[Category:Stub]]
[[Category:Zoology]]

Bell eats counter

2024-08-25T10:30:54Z

Bt2901:

'''Bell eats counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:

* It has both a bell and a counter on the tape.
* Increment: when the bouncer in the bell finishes a period, the counter is increased by one.
* Overflow: when the bouncer in the bell overflows, the bell eats the lowest digit of the counter (the counter is halved), and the bouncer in the bell is reset.
[https://github.com/ccz181078/busycoq/blob/BB6/verify/BECv1.v A Coq proof of a kind of typical behavior doesn't halt.]

== Examples ==
[https://bbchallenge.org/1RB1RE_0RC1RD_1LA1RC_1LC---_1LF0RE_0LF0LA 1RB1RE_0RC1RD_1LA1RC_1LC---_1LF0RE_0LF0LA]

[https://bbchallenge.org/1RB---_1RC0RA_1LD1RA_1LE0LD_0RE1RF_0RB0LF 1RB---_1RC0RA_1LD1RA_1LE0LD_0RE1RF_0RB0LF]

[https://bbchallenge.org/1RB0LE_0RC---_1LC0RD_0RB1RA_1LF1LE_0LA1LF 1RB0LE_0RC---_1LC0RD_0RB1RA_1LF1LE_0LA1LF] (more complex than typical ones)

[https://bbchallenge.org/1RB3LB---3RA0LA_2LA3LB4RB1RB2RA 1RB3LB---3RA0LA_2LA3LB4RB1RB2RA]

[[Category:Stub]]
[[Category:Zoology]]

Dekaheptoid

2024-08-24T23:28:30Z

Bt2901: Created page with "'''Dekaheptoid''' (from Ancient Greek word meaning "seventeen") is an informal class of Turing machines that are, in some sense, similar to Skelet 17. A typical Turing machine in this class has the following behavior: * it works with the sequence of numbers encoded as <math>10^{k}</math> (here referred to as ''digits''). * it spends most of it's time performing an operation that could be described as incrementing/decrementing Gray Code of the sequence * it has a rou..."

Oriented state

2024-08-13T09:29:47Z

Bt2901: Redirected page to Directed head notation

#Redirect [[Directed head notation]]

Directed Head Notation

2024-08-13T09:29:18Z

Bt2901: Redirected page to Directed head notation

#Redirect [[Directed head notation]]

Skelet 1

2024-07-30T15:48:32Z

Bt2901: add fanart

{{machine|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC}}{{unsolved|What is the cycle start time of Skelet 1? The best known lower bound is <math>10^{24}</math>.}}{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}
[[File:Skeleton warrior.png|thumb|A skeleton warrior holding a sword. The runic inscription on its blade is a string that is particularly often encountered on a tape during Skelet 1 simulation.]]
One of the most challenging [[BB(5)]] Turing machines to prove non-halting. It was eventually proven to be a [[Translated Cycler]] with period 8,468,569,863 and start step over <math>10^{24}</math> (probably much larger!)<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#stats Skelet #1 is infinite] Statistics.</ref>

== References ==
<references />

== See Also ==
* https://www.sligocki.com/2023/02/25/skelet-1-wip.html
* https://www.sligocki.com/2023/02/27/skelet-1-halting-config.html
* https://www.sligocki.com/2023/03/13/skelet-1-infinite.html
[[Category:Stub]]

File:Skeleton warrior.png

2024-07-30T15:47:15Z

Bt2901:

A skeleton warrior holding a sword. The runic inscription on its blade is a string that is particularly often encountered on a tape during Skelet 1 simulation.

Skelet 17

2024-07-26T14:33:30Z

Bt2901: /* TM Behavior */

{{machine|1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA}}{{TM|1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA}}

Skelet #17 was one of [[Skelet's 43 holdouts]] and one of the last holdouts in BB(5).

The first step towards its resolution was made by savask, who showed the connection to [[wikipedia:Gray_code|Gray Code]]: https://docs.bbchallenge.org/other/skelet17_savasks_analysis.pdf

Building upon this work, Chris Xu produced a full proof of its nonhalting that can be found here: https://chrisxudoesmath.com/papers/skelet17.pdf

Adapting the above, a formal proof of its nonhalting by mxdys can be found here: https://github.com/ccz181078/Coq-BB5/blob/main/Skelet17.md

== TM Behavior ==

{| class="wikitable floatright" style="text-align:center;"
! rowspan="2"|
|-
! 5 !! 4 !! 3 !! 2 !! 1 !! 0 !! value !! length !! <math>\sigma</math>
|-
| 0 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || 0 || 3 || +1
|-
| 1 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|0}} || 1 || 3 || +1
|-
| 1* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#F22"|{{mono|-1}} || 2 || 3 || +1
|-
| 2 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || 1 || 2 || -1
|-
| 3 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 2 || -1
|-
| 3* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 2 || -1
|-
| 4 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|3}} || 0 || 3 || +1
|-
| 5 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || 1 || 3 || +1
|-
| 6 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || 2 || 3 || +1
|-
| 7 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 3 || 3 || +1
|-
| 7* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|-
| 7** || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#F22"|{{mono|-1}} || 7 || 6 || -1
|-
| 8 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || 3 || 5 || +1
|-
| 9 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || 4 || 5 || +1
|-
| 10 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|0}} || 5 || 5 || +1
|-
| 10* || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#F22"|{{mono|-1}} || 6 || 5 || +1
|-
| 11 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 3 || 4 || -1
|-
| 12 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 2 || 4 || -1
|-
| 13 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 1 || 4 || -1
|-
| 14 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|-
| 14* || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 7 || 5 || +1
|-
| 14** || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#F22"|{{mono|-1}} || 7 || 6 || -1
|-
| 15 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || 3 || 5 || +1
|-
| 16 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 4 || 5 || +1
|-
| 17 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 5 || 5 || +1
|-
| 18 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 6 || 5 || +1
|-
| 19 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 7 || 5 || +1
|-
| 19* || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#F22"|{{mono|-1}} || 8 || 5 || +1
|-
| 20 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || 4 || 4 || -1
|-
| 21 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 3 || 4 || -1
|-
| 22 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 2 || 4 || -1
|-
| 23 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 1 || 4 || -1
|-
| 24 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|}

It can be shown that when the machine head is at the right end of the tape, the complete tape configuration is of the following form (using [[Directed head notation]]):

<math>0^\infty \; 10^{n_1} \; 1 \; 10^{n_2} \; \dots 1 \; 10^{n_k} \textrm{ B> } \; 0^\infty</math>,

where <math>n_i</math> represents a non-negative integer. Essentially, Skelet 17 builds <math>k</math>-length lists of non-negative numbers delimited with individual cells imprinted with a 1.

The most common transformation (frequency tends to 1 as the number of steps increases) occuring between such configurations is described by Increment rule, similar to the Lucal form of Gray Code: the value at the last index is decremented and the value to the left of the rightmost index with odd value is incremented.

It is useful to consider the following ''state variables'':

* Gray Code value (denoted by <math>n</math>): the integer that is obtained by calculating the parity of each number (except the last) in the list, considering the result as a Gray Code bitstring corresponding to some integer and "recovering" this integer.
* Increment value (denoted by <math>\sigma</math>): the parity of the entire sequence, mapped to <math>\{-1, 1\}</math>. Dirung Increment steps, Skelet 17 counts forwards when <math>\sigma = +1</math> or backwards if <math>\sigma = -1</math>.
* Length of the sequence (including leading zeros).

When started on a blank tape, the machine visits configurations of the form <math>(0, 2, 4, ..., 2^{2k+2}, 0)</math> infinitely often (the step numbers where it occurs approximately equal power of 16: 14, 251, 4088, 65537, 1048646, 16777607, 268437188, etc).

=== Analysis by bisimulation ===

Chris Xu found it useful to divide some tape transformations into two phases, one of them is "virtual" or "invisible", as it does not actually occur on the tape. Indeed, the intermediate step involves negative numbers (the last number being decremented to -1 from 0), which is of course cannot correspond to the <math>10^{a_i}</math> written on the tape.

Such skipped intermediate steps are denoted by asterisk in the table to preserve the "real" step counts (e.g. steps 7* and 7**).

[[Category:Stub]]

Skelet 17

2024-07-24T18:35:16Z

Bt2901: add the table with state variables

{{machine|1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA}}{{TM|1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA}}

Skelet #17 was one of [[Skelet's 43 holdouts]] and one of the last holdouts in BB(5).

The first step towards its resolution was made by savask, who showed the connection to [[wikipedia:Gray_code|Gray Code]]: https://docs.bbchallenge.org/other/skelet17_savasks_analysis.pdf

Building upon this work, Chris Xu produced a full proof of its nonhalting that can be found here: https://chrisxudoesmath.com/papers/skelet17.pdf

Adapting the above, a formal proof of its nonhalting by mxdys can be found here: https://github.com/ccz181078/Coq-BB5/blob/main/Skelet17.md

== TM Behavior ==

{| class="wikitable floatright" style="text-align:center;"
! rowspan="2"|
|-
! 5 !! 4 !! 3 !! 2 !! 1 !! 0 !! value !! length !! <math>\sigma</math>
|-
| 0 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || 0 || 3 || +1
|-
| 1 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|0}} || 1 || 3 || +1
|-
| 1* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#F22"|{{mono|-1}} || 2 || 3 || +1
|-
| 2 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || 1 || 2 || -1
|-
| 3 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 2 || -1
|-
| 3* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 2 || -1
|-
| 4 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|3}} || 0 || 3 || +1
|-
| 5 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || 1 || 3 || +1
|-
| 6 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || 2 || 3 || +1
|-
| 7 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 3 || 3 || +1
|-
| 7* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|-
| 7** || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#F22"|{{mono|-1}} || 7 || 6 || -1
|-
| 8 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || 3 || 5 || +1
|-
| 9 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || 4 || 5 || +1
|-
| 10 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|0}} || 5 || 5 || +1
|-
| 10* || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#F22"|{{mono|-1}} || 6 || 5 || +1
|-
| 11 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 3 || 4 || -1
|-
| 12 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 2 || 4 || -1
|-
| 13 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 1 || 4 || -1
|-
| 14 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|-
| 14* || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 7 || 5 || +1
|-
| 14** || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#F22"|{{mono|-1}} || 7 || 6 || -1
|-
| 15 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || 3 || 5 || +1
|-
| 16 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 4 || 5 || +1
|-
| 17 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 5 || 5 || +1
|-
| 18 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 6 || 5 || +1
|-
| 19 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 7 || 5 || +1
|-
| 19* || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#F22"|{{mono|-1}} || 8 || 5 || +1
|-
| 20 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || 4 || 4 || -1
|-
| 21 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 3 || 4 || -1
|-
| 22 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 2 || 4 || -1
|-
| 23 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 1 || 4 || -1
|-
| 24 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|}

It can be shown that when the machine head is at the right end of the tape, the complete tape configuration is of the following form (using [[Directed head notation]]):

<math>0^\infty \; 10^{n_1} \; 1 \; 10^{n_2} \; \dots 1 \; 10^{n_k} \textrm{ B> } \; 0^\infty</math>,

where <math>n_i</math> represents a non-negative integer. Essentially, Skelet 17 builds <math>k</math>-length lists of non-negative numbers with individual cells imprinted with a 1 acting as the delimiter.

[[Category:Stub]]

Template:Mono

2024-07-24T07:01:35Z

Bt2901: this fancy stuff doesn't work idk

{{{2|{{{1}}}}}}

Template:Mono

2024-07-24T07:00:32Z

Bt2901: stolen from english wikipedia

{{<includeonly>safesubst:</includeonly>ifsubst|1=|2=<templatestyles src="Mono/styles.css" />}}{{{2|{{{1}}}}}}

Skelet 17

2024-07-24T06:47:40Z

Bt2901: add details

Hydra

2024-07-23T07:49:45Z

Bt2901: Add etymology

{{machine|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}
Hydra is the 2-state 5-symbol machine {{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}.

It simulates the Collatz-like iteration

<math display="block">\begin{array}{l}
C(2a+1, & b) & \to & A(3a+1, & b+2) \\
C(2a, & b) & \to & A(3a, & b-1) & \text{if} & b>0 \\
C(2a, & 0) & \to & \text{HALT}
\end{array}</math>
 
starting from <math>C(3,0)</math>.<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2023). Accessed 22 July 2024.</ref>

It is closely related to the machine [[Antihydra]].<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]". Accessed 22 July 2024.</ref>

A fast simulator for the odd/even sequence used by Hydra is available [http://nethack4.org/esolangs/fasthydra.zip here].

== Name ==

The name ''Hydra'' references the Ancient Greek legend: just as the legendary creature was growing 2 heads after losing 1 head, the $b$ counter that is kept on the right side of the tape is either decremented by or 1 incremented by 2 (approximately with equal frequency if modelled as a random process; in reality it depends on the parity of $a$). The Hydra dies (halts) when the last head is cut.

==Sources==
<references/>

[[Category:Stub]]

Beaver Math Olympiad

2024-07-23T07:36:06Z

Bt2901: Created page with "''Beaver Mathematical Olympiad'' is an attempt to re-formulate the halting problem for some particular TMs as mathematical problem in a style suitable for a hypothetical math olympiad. The purpose of BMO is twofold. First, statements where every non-essential details (e.g. related to tape encoding, number of steps, etc) is discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard ques..."

''Beaver Mathematical Olympiad'' is an attempt to re-formulate the halting problem for some particular TMs as mathematical problem in a style suitable for a hypothetical math olympiad.

The purpose of BMO is twofold. First, statements where every non-essential details (e.g. related to tape encoding, number of steps, etc) is discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard question could appear deceptively simple.

[[Category:Stub]]