Do there exist Infinite Time Turing Machines that satisfy a particular set of properties?

74 Views Asked by At

Let $x$ denote a real that encodes (in any fixed way that can be interpreted by an Infinite Time Turing Machine) a well-order of arbitrary order-type $\alpha$.

Does there exist an Infinite Time Turing Machine $M$ which, given a pair $(i,x)$ as input, satisfies the two following properties?

  1. If an $i$-th Infinite Time Turing Machine $m_i$ halts at stage $\beta \leq \alpha$, then $M$ outputs a non-zero bit followed by the final content of the output tape of $m_i$.
  2. If an $i$-th Infinite Time Turing Machine $m_i$ does not halt at stage $\beta \leq \alpha$, then $M$ outputs a zero bit followed by the content of the output tape of $m_i$ at stage $\alpha$.

If such $M$ exists, I am interested to know the details of how it operates.

1

There are 1 best solutions below

0
On BEST ANSWER

Some detail regarding what was written in comments. First one goes through the well-order relation (to confirm that it indeed is one). Let's suppose the corresponding order-type is $\alpha$. Now we want to simulate the running of machine $M_n$ with index $n$ till the minimum of (i) $\alpha$ (ii) its halting time.

Denote the order-preserving bijection function from $\alpha$ to $\mathbb{N}$ [under the well-ordering relation] as $address:\alpha \rightarrow \mathbb{N}$. Now what we want to do is to allocate some separate cells (permanently) which we denote as $a_0,a_1,a_2,a_3,...$ and $b_0,b_1,b_2,b_3,...$. In the cells of form $b_i$ we just store the contents of tape of our machine (when it has been simulated till time $t$). Initially these cells just contain what our machine $M_n$ contains in its cells.

The cells of form $a_i$ are all initially marked as $0$. Our simulation proceeds via step-by-step parsing of the well-order. These cells gradually begin changing to $1$ These cells $a_i$ don't oscillate and once turned to $1$ never turn back to $0$. At some ordinal-step $t$ a cell $a_i$ is $1$ iff $i=address(x)$ (for some ordinal $x<t$). Now every time one of the cells from $a_i$ is changed from to $0$ to $1$, the cells $b_i$ are updated accordingly (by simulating a step for the machine $M_n$). Also, note that its reasonable never to re-allocate or "shift" the space given to the cells $a_i$ and $b_i$ and instead just keep it fixed (because this makes the limit behaviour as easy to verify as correct).

If all cells $a_i$ are turned to $1$ without machine $M_n$ reaching halt-state then it means that the machine $M_n$ has reached the time $\alpha$ without halting. The contents of its tape are contained in the cells $b_i$. With some further details (and few differences), similar idea applies to simulation of OTMs/ORMs till time $\alpha$.