A337025 Number of n-state 2-symbol halt-free Turing machines.

1, 16, 4096, 2985984, 4294967296, 10240000000000, 36520347436056576, 182059119829942534144, 1208925819614629174706176, 10314424798490535546171949056, 109951162777600000000000000000000, 1432052311740255546466984939315265536

Offset: 0

Author

Nicholas Drozd, Aug 11 2020

Keywords

• nonn
• easy

Comments

A Turing machine is halt-free if none of its instructions lead to the halt state.

This sequence is strictly less than A052200(n) for all n > 0, since halt-free n-state machines are a strict subset of all n-state machines.

Solutions to the so-called "Beeping Busy Beaver" problem will almost certainly be halt-free programs.

For n > 1, a(n) is the absolute value of the determinant of a Hadamard matrix of size 4(n-1). This is apparent from the fact that HH^T = nI_n implies det(H)^2 = det(nI_n) = n^n, so det(H) = +- n^(n/2) and plugging in 4n yields a(n). - Nour Abouyoussef, Jun 25 2025

Links

• Scott Aaronson, The Busy Beaver Frontier.
• Nick Drozd, Beeping Busy Beavers.

Crossrefs

Cf. A052200.

Programs

Python

[((4 * n) ** 2) ** n for n in range(12)]

Formula

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