# set theory – How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $$M_i(x)$$ denote a computation of an $$i$$-th ITTM, assuming that the input $$x$$ is a real (an infinite binary sequence).

Then the function $$f(i)$$ (input: natural number, output: countable ordinal) is defined as follows:

1. if $$M_i(x)$$ does not halt for any real $$x$$, then $$f(i) = 0$$;
2. if there exists the largest countable ordinal $$alpha$$ such that there exists a real $$x$$ such that $$M_i(x)$$ halts at time $$alpha$$ (and there does not exist a real $$y neq x$$ such that $$M_i(y)$$ halts at time $$beta > alpha$$), then $$f(i) = alpha$$;
3. if both (1) and (2) are false (that is, if for any countable ordinal $$alpha$$ there exists a real $$x$$ such that $$M_i(x)$$ halts at time $$beta > alpha$$), then $$f(i) = 0$$.

The ordinal $$tau$$ is defined as the supremum of the infinite set $${f(0), f(1), f(2), ldots }$$. Question: how large is $$tau$$? In particular, what is $$tau$$ in comparison with the least $$Sigma_1$$-stable ordinal (mentioned in the Definition 3.1 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”)?

Posted on Categories Articles