6 problems

Let $S(n)$ denote the maximum number of steps executed by any halting $n$-state Turing machine started on a blank tape. The Marxen–Buntrock machine is a 5-state machine achieving…

Fifth busy beaver number conjecture. Although there is no general algorithm to compute $\operatorname{BB}(n)$ in general, researchers have long conjectured that

Let $\operatorname{BB}(n)$ denote the maximum number of steps made by any halting deterministic Turing machine with $n$ states and two symbols, starting on a blank tape. A machine…

A one-dimensional reversible Turing machine is a reversible Turing machine whose tape is one-dimensional. Reversible physical universality means physical universality in the specif…

Attainment conjecture. The supremum in this expression is actually reached. Consequently, the numbers that arise as entropies of Turing machines are exactly the numbers that arise…

Let $S(n,m)$ denote the maximum number of steps before halting, and let $\mathnormal{\Sigma}(n,m)$ denote the maximum number of symbols written, among halting $n$-state, $m$-symbol…