Is every pair of writable reals one-tape-ITTM-computable?

Question

I've been reading this paper, in which authors prove that not all ITTM-computable functions $\Bbb R\rightarrow\Bbb R$ are 1-tape-computable, but if we put some restriction on the output of the function (e.g. restrict it to be $\Bbb N$), then they all are. I asked myself, "how about restricting the input of the function?".

My first question was, is every ITTM-computable function $\Bbb N\rightarrow\Bbb R$ 1-tape-computable? After a minute, I have realized I don't know the answer to a simpler question: Is every function ITTM-computable function $\{0\}\rightarrow\Bbb R$ 1-tape-computable? Or, to put another way, is every writable real 1-tape-writable?

I believe I've shown the answer to the last question is "yes", and the idea is to use the theorem 1.5 from the paper linked: given a writable real $r$, a real $r'$ which we get by deleting the first bit of $r$ is writable as well. Then the function $0\mapsto r'$ is computable, hence the functions $1r'$ and $0r'$ are 1-tape-computable (first by theorem 1.5, second by making the machine change $1$ to $0$ upon halting), and one of these is $r$.

Later I have found that proof of theorem 2.1 actually provides a function $\Bbb N\rightarrow\Bbb R$ which is not 1-tape-computable but is ITTM-computable. This however still leaves open the intermediate case, and this is where I ask my question:

Is there an ITTM-computable function $f:\{0,1\}\rightarrow\mathbb R$ which is not 1-tape-computable?

I will quickly mention that my argument for writable reals doesn't prove this negative, since that method only allows us to change the first bit to something fixed, so if first bits of $f(0),f(1)$ are distinct, we are in dead end.

I suspect the answer to this question is yes. The reason is the following: function defined in theorem 2.1, witnessing that ITTM-computable functions need not be 1-tape-computable, has as $f(n),n>0$ finite strings [EDIT: reading more carefully, I have realized this might not be true, so the argument below isn't correct], so we could concatenate these (and put markers inbetween) to get a real $r$. Then if function $0\mapsto f(0),1\mapsto r$ were 1-tape-computable, we maybe could reconstruct $f(n)$ given $r$ and $n$ with just one tape, making $f$ 1-tape-computable. However, I didn't manage to fill in all the details, and I'm not sure if all these steps are executable on a 1-tape machine. Another detail would be removing the remainder of $r$ from the tape, but I think leaving it will keep the function non-1-tape-computable by precisely the same argument.

Thanks in advance for any help.

Answer 1

How nice to hear that you are reading that paper. The paper appeared as:

• J. D. Hamkins and D. E. Seabold, Infinite Time Turing Machines With Only One Tape, Mathematical Logic Quarterly, vol. 47, iss. 2, pp. 271-287, 2001.

It seems to me that your question is answered negatively by theorem 1.6 of the paper, which says that if the range of a partial function $f:\mathbb{R}\to\mathbb{R}$ is not dense, then it is infinite time computable if and only if it is one-tape computable. Since no function on a finite domain has dense range, it follows that every ITTM computable function $f:\{0,1\}\to\mathbb{R}$ is also computable by a one-tape ITTM. Right?

The idea of the proof is that if there is some finite string of bits that never arise as an initial segment of an output string, then we can put that finite string on the start of the one tape, using it as a marker that we are not yet done with the computation simulation, and so at a limit stage we can recognize that it is still there, so we will thereby know that we are still in the simulating part of the computation. But at the very end, when we collapse the output, then the actual output will not agree with that finite string, and so we will recognize after the following limit stage that we have just finished collapsing the output and we can therefore halt with confidence.