A081419 Largest value held in any register at the end of a halting computation by an n-instruction register Minsky machine.

0, 1, 2, 3, 4, 6, 9, 34, 520

Offset

1,3

Comments

We start with initially empty registers and include exactly one Halt instruction. Analogous to the Busy Beaver function, Sigma, for Turing Machines.

n<=5 are proved. 5<n<=9 are good lower bounds.

References

Tibor Rado, On Noncomputable Functions, Bell System Technical Journal, vol. 41, # 3, 877-884, May 1963.

Links

Table of n, a(n) for n=1..9.

Formula

Noncomputable.

Example

A program for a(3)=2 is:
  1: A+ -> 2
  2: A+ -> 3
  3: HALT
which halts with A=2.
From Sean A. Irvine, Oct 28 2025: (Start)
A program for a(6)=6 is:
  1: A+ -> 2
  2: A+ -> 3
  3: A+ -> 4
  4: B- -> 6, 5 (jump to 5 is B=0, otherwise 6)
  5: B+ -> 1
  6: HALT
which halts with A=6.
A program for a(7)=9 is:
  1: B+ -> 2
  2: B+ -> 3
  3: A+ -> 4
  4: A+ -> 5
  5: A+ -> 6
  6: B- -> 3, 7
  7: HALT
which halts with A=9. (End)

Crossrefs

Cf. A028444.

Sequence in context: A375621 A275173 A295394 * A108858 A294688 A267102

Adjacent sequences: A081416 A081417 A081418 * A081420 A081421 A081422

Keyword

hard,nice,nonn,more

Author

Rick J. Griffiths (rjg42(AT)cam.ac.uk), Apr 20 2003

Status

approved