A060843 -id:A060843 - cp's OEIS frontend

A362199 Decimal expansion of the sum of the reciprocals of the Busy Beaver numbers (A060843).

1, 2, 2, 3, 6, 3, 1, 5, 2, 9, 8, 7, 5, 0, 6, 5, 6, 7, 2, 0, 6, 7, 7, 6, 2, 6, 8, 3, 1, 7, 6, 3, 1, 2, 4, 6, 2, 1, 6, 2, 2, 6, 4, 6, 6, 0, 0, 2, 7, 1, 6, 1, 4, 9, 0, 9, 0, 6, 4, 6, 8, 9, 4, 4, 5, 6, 4, 1, 9, 6, 8, 8, 4, 9, 8, 7, 5, 6, 4, 5, 4, 9, 7, 2, 8, 9, 7, 1, 6, 2, 6, 1, 2, 7, 7, 9, 0, 1, 4, 6, 8, 5, 6, 4, 4

Offset: 1

Robert C. Lyons, Apr 10 2023

Equal to 1/BB(1) + 1/BB(2) + 1/BB(3) + ... = 1/A060843(1) + 1/A060843(2) + 1/A060843(3) + ...
A homework assignment in Scott Aaronson's "PHYS771 Lecture 3: Gödel, Turing, and Friends" (see links) asks if 1/BB(1) + 1/BB(2) + 1/BB(3) + ... is a computable real number. Scott Aaronson's "PHYS771 Lecture 4: Minds and Machines" (see links), which provides the answers to the homework assignment, proves that the number is not computable.
Because BB(5) was proved to be 47176870 (see here https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237) and BB(6) was proved to be greater than 10^^15 (see here https://www.sligocki.com/2022/06/21/bb-6-2-t15.html), over 10^14 terms are known. - Matthew Schulz, Dec 13 2024.

			1.22363152987506567206776268317631246216226466...

Matthew Schulz, Table of n, a(n) for n = 1..20000
Scott Aaronson, PHYS771 Lecture 3: Gödel, Turing, and Friends.
Scott Aaronson, PHYS771 Lecture 4: Minds and Machines.

Cf. A060843.

1/A060843(1) + 1/A060843(2) + 1/A060843(3) + ...

a(8) onwards from Matthew Schulz, Dec 13 2024

A028444 Busy Beaver sequence, or Rado's sigma function: maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting.

Original entry on oeis.org

0, 1, 4, 6, 13, 4098

Offset: 0

Scott Aaronson (sja8(AT)cornell.edu)

Expanded definition from Daniel Forgues: Busy Beaver sequence, or Rado's Sigma function: maximum number of 1s that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) halting Turing machine can print on an initially blank tape (all 0's) before halting.
States q and q+ in set Q_n of n distinct states (plus the Halt state), tape symbols s and s+ in set S = {0, 1}, shift direction d+ in {LEFT, RIGHT} (NONE is excluded here), + suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).
The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) which a halting Turing Machine H with n internal states, 2 symbols, and a two-way infinite tape can produce onto an initially blank tape (all 0's) and then halt. The function S(n) = S(n, 2) (A060843) denotes the maximal number of steps (thus shifts, since direction NONE is excluded) which a halting machine H can take (not necessarily the same Turing machine producing a maximum number of 1's and need not even produce many tape marks). For all n, S(n) >= Sigma(n).
Given that 5-state 2-symbol halting Turing machines can compute Collatz-like congruential functions (see references under A060843), it may be very hard to find the next term.
Rado's Sigma function grows faster than any computable function and is thus noncomputable.
From Daniel Forgues, Jun 05-06 2011: (Start)
H in H_(n, k) is a halting* Turing machine with n states and k symbols;
* (on a blank tape (all 0's) as input)
States q, q+ in set Q_n of n distinct states (plus the Halt state);
Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol);
Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here);
sigma(H) is the number of non-blank symbols left on the tape by H;
s(H) is the number of steps (or shifts in our case) taken by H;
Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
a(n) is Sigma(n) = Sigma(n, 2) since a 2-symbol BB-class Turing machine is assumed.
For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)
From Jianing Song, Nov 12 2023: (Start)
We have a(2*n) > H_n(3,3) = 3 "up-arrow"(n-2) 3, where H_n is the n-th hyperoperator, and "up-arrow" is Knuth up-arrow notation (see the Wikipedia link). This means that a(12) > 3^^^^3 = g(1), where g(1) is the starting value in the sequence that defines Graham's number = g(64).
Note that there is an (n_0)-state binary Turing machine (and hence an n-state one for every n >= n_0) which halts if and only if ZFC is inconsistent, so a(n_0) (and hence a(n) for every n >= n_0) is independent of ZFC, which means that a(n_0) evaluates differently in different models of ZFC; see the section "Non-computability" of the Wikipedia link and the Math Stack Exchange. The minimum such n_0 is not exceeding 745. (End)
a(6) >= 2^^(2^^(2^^10)). - Brian Galebach, Jul 10 2025

John Hopcroft, Turing Machines, Sci. Amer. vol. 250, #5, 86-98, May 1984, table on page 92 gives old lower bounds.
Jeffrey Shallit, A second course in formal languages and automata theory, Cambridge University Press, 2008. See Fig. 6.2, p. 185.

S. Aaronson, BusyBeaver(6) is really quite large, 28 June 2025.
Bob Boonstra, Busy Beavers, Programmer's Challenge, MacTech Journal, Volume 16 (2000), Issue 9 - reports that in December 1984 George Uhing found a 5-state machine that produced 1915 1's before halting.
Computerphile, Busy Beaver Turing Machines, YouTube video, 2014.
J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.
S. Ligocki, BB(6, 2) > 10↑↑15, 2022.
H. Marxen, Busy Beaver
H. Marxen and J. Buntrock, Attacking the Busy Beaver 5, Bulletin of the EATCS, 40, pages 247-251, 1990.
Math Stack Exchange, What does it mean to say BB(7918) is not computable from ZFC?
mxdys, Current BB(6) Champion Discovered by mxdys on 25 June 2025.
Pascal Michel, Historical survey of Busy Beavers, 2011.
Pascal Michel, Behavior of busy beavers, 2010.
Pascal Michel, The Busy Beaver Competitions, 2010.
Pascal Michel, The Busy Beaver Competition: a historical survey, arXiv:0906.3749 [math.LO], 2009-2017.
Tibor Rado, On Noncomputable Functions, Bell System Technical Journal, vol. 41, # 3, 877-884, May 1963.
Michael Somos, Busy Beaver Turing Machine.
Michael Somos, Busy Beaver.
Eric Weisstein's World of Mathematics, Busy Beaver
Wikipedia, Busy beaver
Index entries for sequences related to Busy Beaver problem

Cf. A004147, A052200, A060843.

Edited by Daniel Forgues, Mar 25 2010, Jun 05 2011
Edited by N. J. A. Sloane, Aug 30 2011
a(5) added by Brian Galebach, Jun 10 2025

A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

Original entry on oeis.org

1, 64, 20736, 16777216, 25600000000, 63403380965376, 232218265089212416, 1180591620717411303424, 7958661109946400884391936, 68719476736000000000000000000, 739696442014594807059393047166976, 9711967541295580042210555933809967104, 152784834199652075368661148843397208866816

Offset: 0

Michael Somos, Jan 28 2000

T in T_(n, k) is a Turing machine with n states and k symbols;
States q, q+ in set Q_n of n distinct states (plus the Halt state;)
Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol;)
Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here;)
+ suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).
This sequence is computable. On the other hand, the busy beaver numbers are noncomputable, found only by examining each of the many n-state Turing machine programs' halting. - Michael Joseph Halm, Apr 29 2003
From Daniel Forgues, Jun 06 2011: (Start)
RE: Busy beaver halting Turing machines:
H in H_(n, k) is a halting* Turing machine with n states and k symbols;
* (on a blank tape, all 0's, as input)
sigma(H) is the number of non-blank symbols left on the tape by H;
s(H) is the number of steps (or shifts in our case) taken by H;
Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
Cf. A028444 for Sigma(n, 2), A060843 for S(n, 2). (End)
This sequence also counts machines with unreachable states, and all (up to (n-1)!) permutations of non-start states, which don't affect behavior. In contrast, A107668 only counts state graphs reaching all n states in canonical order. - John Tromp, Oct 17 2024

			a(1) = 64 = (4*1+4)^(2*1) = 8^2.

J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.
Michael Somos, The Busy Beaver Problem
OEIS Wiki, Busy Beaver numbers
Index entries for sequences related to Busy Beaver problem

Cf. A028444, A004147, A060843, A107668.

A052200[n_]:=(4(n+1))^(2n); Array[A052200,20,0] (* Paolo Xausa, May 21 2023 *)

a(n) = (4*(n+1))^(2*n).

Entry revised by N. J. A. Sloane, Feb 08 2007

Edited by Daniel Forgues, Mar 25 2010

A385902 Antihydra, a BB(6) Turing machine (values of b).

Original entry on oeis.org

0, 2, 4, 6, 5, 7, 9, 11, 10, 12, 11, 13, 12, 11, 10, 12, 14, 16, 15, 14, 16, 15, 17, 16, 18, 17, 19, 21, 20, 19, 21, 20, 19, 21, 23, 25, 24, 23, 22, 21, 20, 22, 21, 20, 19, 18, 17, 19, 21, 23, 25, 27, 29, 31, 30, 29, 31, 30, 32, 31, 33, 32, 31, 33, 35, 37, 36

Offset: 0

Peter Luschny, Aug 02 2025

nonn

Let f(a, b) = (3*a / 2, b + 2) if a is even, otherwise ((3*a - 1)/2, b - 1). The Busy Beaver challenge is to find natural numbers n and v, such that after n iterations, starting with f(8, 0), the result is (v, -1). The sequence lists the values of b in the iteration, the values of a are in A386792.

It is strongly suspected that the iteration does not halt according to the random-walk heuristic. Since Antihydra is derived from the transition rules of a 6-state, 2-symbol Turing machine, proving its divergence is equivalent to proving that this machine does not halt. Demonstrating the divergence of Antihydra is likely a necessary step in establishing a lower bound for BB(6), as this Turing machine appears to outrun all known halting 6-state machines.

Paolo Xausa, Table of n, a(n) for n = 0..10000
The Busy Beaver Challenge, Antihydra.
The Busy Beaver Wiki, Antihydra.
Shawn Ligocki, BB(6) is Hard (Antihydra), Jul 6, 2024.
Index entries for sequences related to Busy Beaver problem.

Cf. A386792 (values of a), A028444, A060843.

Module[{a = 8, b = 0}, NestWhileList[(If[OddQ[a], b--, b += 2]; a += Quotient[a, 2]; b) &, b, b != -1 &, 1, 100]] (* Paolo Xausa, Aug 04 2025 *)

def antihydra(start: int = 8, halt: int = 66) -> list[int]:
    seq = []
    a = start
    b = 0
    n = 0
    while b != -1:
        if n > halt: break
        seq.append(b) # print(f"[{n}] -> ({a}, {b})")
        if a % 2 == 0:
            b += 2
        else:
            b -= 1
        a += a // 2
        n += 1
    return seq
print(antihydra())

A386792 Antihydra, a BB(6) Turing machine (values of a).

Original entry on oeis.org

8, 12, 18, 27, 40, 60, 90, 135, 202, 303, 454, 681, 1021, 1531, 2296, 3444, 5166, 7749, 11623, 17434, 26151, 39226, 58839, 88258, 132387, 198580, 297870, 446805, 670207, 1005310, 1507965, 2261947, 3392920, 5089380, 7634070, 11451105, 17176657, 25764985, 38647477

Offset: 0

Peter Luschny, Aug 02 2025

nonn

Let f(a, b) = (3*a / 2, b + 2) if a is even, otherwise ((3*a - 1)/2, b - 1). The Busy Beaver challenge is to find natural numbers n and v, such that after n iterations, starting with f(8, 0), the result is (v, -1).

We consider the sequence to be defined for all values of n, regardless of whether 'b' ever takes the value -1 or not. The sequence records the values of 'a' in this iteration. See A385902 for the values of 'b'.

Paolo Xausa, Table of n, a(n) for n = 0..5000
The Busy Beaver Challenge, Antihydra.
The Busy Beaver Wiki, Antihydra.
Shawn Ligocki, BB(6) is Hard (Antihydra), July 2024.

Cf. A385902 (values of b), A028444, A060843.

aList := proc(halt) a := 8; u := 0; H := 8;
from 0 to halt do
    q, r := iquo(a, 2), irem(a, 2):
    a, u := a + q, u + r: H := H,a
od: H end: aList(37);

A386792List[n_] := Module[{next},
    next[{a_, u_}] := {a, u} + QuotientRemainder[a, 2];
    NestList[next, {8, 0}, n][[All, 1]]];
A386792List[38] (* Peter Luschny, Aug 05 2025 *)

def A386792List(n) -> list[int]:
    (a, b), H = (8, 0), [8]
    for _ in range(n):
        a, b = map(sum, zip((a, b), divmod(a, 2)))
        H.append(a)
    return H

A125269 Minimal number of states required for a 2-symbol, 5-tuple Turing machine that takes n steps on an initially blank tape before halting.

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 4, 4, 5, 5, 4, 5, 5, 5, 5, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5

Offset: 1

Dustin Wehr (robert.wehr(AT)mail.mcgill.ca), Jan 16 2007, Jan 28 2007

If BB(n) = A060843(n), then a(BB(n)) = n and that is the last occurrence of n in this sequence. a(n) will not become monotonic; if it did, we could compute BB(n), since a(n) is computable. a(n) diverges properly, but does so very slowly. The terms with values 1,2,3 were computed by exhaustive search. The terms with value 4 were inferred from knowing that they are greater than 3 and from the observation that for all n, a(n+1) <= a(n) + 1 (an easy construction). Using exhaustive search, may be able to extend the sequence to (most of) the terms up to and a bit beyond a(107) = 4, but going much further would likely require a more sophisticated method (see A052200).

If BB(n) = A060843(n), then a(BB(n)) = n and that is the last occurrence of n in this sequence. a(n) will not become monotonic; if it did, we could compute BB(n), since a(n) is computable. a(n) diverges properly, but does so very slowly. a(n+1) <= a(n) + 1 (an easy construction). - Martin Fuller, Feb 14 2007

Martin Fuller, Table of n, a(n) for n = 1..626
Martin Fuller, Illustration file listing a Turing machine for each n
H. Marxen, Info on the Busy Beaver problem

Cf. A060843, A052200.

More terms from Martin Fuller, Feb 14 2007

A131956 Busy Beaver variation: maximum number of steps for a 2-state, 2-symbol Turing machine running on a tape which is initialized with the number n in binary and 0's everywhere else. The machine is started at the rightmost bit in the number n.

Original entry on oeis.org

6, 7, 9, 9, 9, 14, 9, 13, 13, 11, 13, 14, 9, 14, 11, 17, 15, 18, 9, 11, 11, 22, 24, 23, 13, 11, 13, 15, 10, 14, 14, 21, 18, 15, 17, 14, 10, 14, 9, 13, 21, 18, 20, 20, 22, 37, 39, 38, 15, 18, 10, 11, 14, 22, 24, 23, 13, 11, 13, 16, 13, 16, 17, 25, 21, 22, 15, 16, 13, 26, 28, 25, 15

Offset: 0

Bryan Jacobs (bryanjj(AT)gmail.com), Aug 01 2007

nonn

			a(5) is the maximum number of steps running on a tape which is initialized as:
..000001010000.... with the machine starting at the rightmost 1.
a(5) = 14, with the machine:
A0-> 0*L
A1-> 0BR
B0-> 1BL
B1-> 1AR

Eric Weisstein's World of Mathematics, Busy Beaver.

Cf. A060843.

A384629 Instruction-Limited Busy Beaver Sequence BBi(n): Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before eventually halting.

Original entry on oeis.org

0, 1, 3, 5, 16, 37, 123, 3932963

Offset: 0

Brian Galebach, Jun 05 2025

This sequence is uncomputable.
No halting instruction is required, as a Turing machine halts whenever the current state/tape symbol combination does not have a corresponding instruction. However, a halting instruction can be implemented by transitioning to a state which has no instructions. For example, the 2-state 2-symbol busy beaver can be given as A0:1RB, A1:1LB, B0:1LA, B1:1RC, where "C" effectively substitutes for "H".
This sequence effectively combines the various Busy Beaver step functions BB(states,symbols) into a single sequence defined only by number of allowable instructions BBi(inst). It is very interesting to observe the number of states and symbols associated with the champion machine for each number of instructions.
a(6)=123 confirmed by Shawn Ligocki on bbchallenge discord on Jul 12 2025.
a(7)=3932963 confirmed and announced on discord on Jul 23 2025. Two different Turing machines - one a 2-state, 4-symbol machine, and the other a 3-state, 3-symbol machine - each take 3932963 steps, writing 2050 non-blank symbols to tape.
A new champion machine for a(8) was discovered by Nick Drozd and confirmed by Shawn Ligocki on Jul 26 2025. This machine takes around 6.889 x 10^1565 steps before halting.

			a(0)=0.  No instructions means machine instantly halts. (Philosophical question: Can something that was never moving actually "halt"?)
a(1)=1.   A0:0RB - One of two 1-instruction machines taking 1 step.
a(2)=3.   A0:0RB, B0:1LA
a(3)=5.   A0:0RB, B0:1LA, B1:1RB - One of 14 3-instruction machines taking 5 steps.
a(4)=16.  A0:1RB, B0:0RC, C0:1LC, C1:0LA
a(5)=37.  A0:1RB, A1:2LB, B0:2LA, B1:2RB, B2:1LB - BB(2,3) minus the halt instruction for A2.
a(6)=123. A0:1RB, A1:3LA, A2:1RA, A3:0LA, B0:2LA, B3:3RA
a(7)=3932963. A0:1RB, A1:2LA, A2:1RA, A3:1RA, B0:1LB, B1:1LA, B2:3RB - BB(2,4) minus the halt instruction for B3, and A0:1RB, A1:2LA, A2:1RA, B0:1LC, B1:1LA, B2:2RB, C1:1LA - A 3-state, 3-symbol Turing machine with two empty instructions.
a(8)>=6.889 x 10^1565. Must be at least the number of steps taken by the following 3-state, 4-symbol machine discovered by Nick Drozd: A0:1RB, A1:1LA, B0:1RC, B1:3LB, B2:1RB, C0:2LA, C1:2LC, C3:0LC. a(8) will not easily be proven because a 3-state, 3-symbol machine "Bigfoot", having 8 non-halting instructions, must first be proven never to halt, requiring solving a Collatz-like problem.

bbchalenge Wiki, Instruction-Limited Busy Beaver.
discord, Announcement of BBi(7)..
N. Drozd, New BBi(8) champion machine found.
S. Ligocki, BBi(8) steps value confirmed.
S. Ligocki, BB(3,3) is Hard (Bigfoot).
Pascal Michel, The Busy Beaver Competitions.

Cf. A060843, A384766.

a(6) added by Brian Galebach, Jul 15 2025

a(7) added by Brian Galebach, Aug 05 2025

A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.

Original entry on oeis.org

1, 3, 1, 4, 2, 1, 1, 0, 1, 12, 2, 1, 1, 1, 1, 16, 0, 19, 1, 21, 3, 2, 2, 0, 1, 1, 1, 1, 1, 1, 1, 32, 1, 0, 0, 36, 2, 1, 1, 0, 2, 45, 3, 2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 64, 1, 67, 1, 0, 0, 0, 0, 0, 1, 76, 2, 1, 1, 1, 1, 81, 0, 84, 2, 86, 4, 3, 3, 0, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0

Offset: 0

Sam Alexander, May 24 2006

nonn

The prototypical example of a noncomputable sequence.

			Using Cutland's Godel numbering, 80 corresponds to the URM program "Z(1) J(1,1,1) S(1)", which clearly loops forever on any input, so a(80)=0. On the other hand, 17 corresponds to the URM program "S(1) T(1,1)", which, on input 17, produces 18. So a(17)=18+1=19.

Nigel Cutland, "Computability: An introduction to recursive function theory". Cambridge University Press, 1980. p. 78.

Ramin Naimi, URM Simulator

Cf. A004147, A028444, A052200, A060843, A081419.

A119683 Maximal number of steps that an n-state Turing machine can make which was started on an initially blank tape before halting on the blank tape again.

Original entry on oeis.org

1, 4, 12, 34

Offset: 1

Christian Hercher (ch(AT)wurzel.org), Jun 08 2006

Cf. A060843, A028444.

cp's OEIS Frontend

A362199 Decimal expansion of the sum of the reciprocals of the Busy Beaver numbers (A060843).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A028444 Busy Beaver sequence, or Rado's sigma function: maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A385902 Antihydra, a BB(6) Turing machine (values of b).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A386792 Antihydra, a BB(6) Turing machine (values of a).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

A125269 Minimal number of states required for a 2-symbol, 5-tuple Turing machine that takes n steps on an initially blank tape before halting.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A131956 Busy Beaver variation: maximum number of steps for a 2-state, 2-symbol Turing machine running on a tape which is initialized with the number n in binary and 0's everywhere else. The machine is started at the rightmost bit in the number n.

Views

Author

Keywords

Examples

Links

Crossrefs

A384629 Instruction-Limited Busy Beaver Sequence BBi(n): Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before eventually halting.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.

Views

Author