Skip to main content
1 of 2
user avatar
user avatar

Jean-Camille Birget answered my question. These are called universally halting Turing machines. The oldest reference is:

Martin Davis (1956). A note on universal Turing machines. In Shannon, C. E., McCarthy, J., eds, Automata Studies, pp. 167-175. Princeton University Press.

Birget proved a complexity version of this: Every deterministic Turing machine with time complexity $T(n)$ is equivalent to a deterministic Turing machine which halts after $O(T(n))$ steps, no matter what configuration of size $n$ this machine starts in [J.C. Birget, Infinite String Rewrite Systems and Complexity, J. Symbolic Computation (1998) 25, 759-793.]

user6976