Halting of transfinite Turing Machine question Consider a transfinite Turing Machine model, allowing ordinal-length tape and time, and a number of states of arbitrary cardinality.
Is there an algorithm P with at most $\aleph_{0}$ states, such that P halt after $\omega_{1}$ steps on the empty input?
 A: The answer is no, there is no such program.
Let me say, first, that allowing countably infinitely many states into the program is basically equivalent to having a finite program with a real
parameter, since one can have a master control program that consults the real parameter to see what it should do next; this would align things a little closer with how the theory is usually undertaken. But it is of no consequence, and I can go along with your infinite program. 
Suppose that $p$ is one of your programs, and we run it on an ordinal-length empty
tape, and suppose that it halts at time $\omega_1$. Consider the
relativized constructible universe $L[p]$, and observe that the
operation of the program $p$ is absolute to this universe $L[p]$.
Indeed, if $\theta>\omega_1$, then the operation of the machine is
absolute to $L_\theta[p]$, which will therefore observe that the
program halts at stage $\omega_1$. By the Löwenheim-Skolem
theorem and condensation, there is a countable ordinal $\gamma$
with an elementary embedding $L_\gamma[p]\precsim L_\theta[p]$. It follows that $L_\gamma[p]$
also observes that $p$ halts at the ordinal
$\omega_1^{L_\gamma[p]}$, which is a countable ordinal less than
$\gamma$. But the operation of the machine at stages below $\gamma$
is absolute to $L_\gamma[p]$, and so the program must really halt
at that countable stage, contradicting out assumption. 
The argument shows that every such program, even allowing countably infinitely many states, must halt at a countable stage, if it halts at all.
Another way to see this is to point out that the halting nature of a program is a $\Sigma_1$ expressible fact about the program, and so if this $\Sigma_1$ statement about $p$ is true, then it will become true by the first $\Sigma_1(p)$ stable ordinal, which is countable. 
Meanwhile, the very first theorem of my paper 


*

*Hamkins, Joel David; Lewis, Andy, Infinite time Turing machines, J. Symb. Log. 65, No.2, 567-604 (2000). DOI:10.2307/2586556, ZBL0963.03064, arxiv:9808093, blog entry.


shows that in the case of infinite time Turing machines, which allow a tape of length $\omega$ rather than Ord as in your question, every halting computation must halt at a countable stage. Indeed, every computation either halts or strongly repeats at a countable stage. 
