Technical limitations of Turing machines due to the input and output encoding of values

Question

Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine with $m$ states for some $m\geq 1$, its program is a function $\delta \colon Q \times \Sigma \to (Q\cup \{0\}) \times \Sigma \times \{ \mathtt{L}, \mathtt{R} \}$ where $Q = \{1,\ldots,m\}$ is the set of states, $\Sigma = \{0,1\}$ is the set of tape symbols and $\mathtt{L}, \mathtt{R}$ stand for the directions left and right in which the head may move. The tape will always be filled with $0$'s except for finitely many $1$'s. The machine always starts execution in state $1$ and stops when it reaches the state $0$.

We know Turing machines can compute any computable function, in the sense that there is a proper encoding of input and output values such that any computable function can be computed by some program. Very specifically, for each $f \colon \mathbb{N} \dashrightarrow \mathbb{N}$ partial computable, there is a Turing machine $M_f$ such that if $M_f$ is run from a tape containing the number $x$ written in unary immediately after the starting head position (i.e., the tape starts as $1^x$ with the head at the leftmost $1$, and the rest is filled with $0$'s), the machine terminates in finite time iff $f(x) =: y$ is defined, and, if so, returns a tape in the form $1^y$ with the head at the same position as initially.

When studying computability, the details of the encoding aren't very interesting, but the point is some encoding is necessary and it can't be arbitrary:

Definition: Let us say that two computable injections $\gamma_{\mathrm{i}}$ and $\gamma_{\mathrm{o}}$ (the “input encoding” and “output encoding” respectively) of $\mathbb{N}$ in the set of all possible tapes with only finitely many $1$'s on them (together with a marked head position) are a (computably) proper encoding [my terminology] when, for any $f \colon \mathbb{N} \dashrightarrow \mathbb{N}$ partial computable, there is a Turing machine $M_f$ such that $M_f$ terminates on $\gamma_{\mathrm{i}}(x)$ iff $f(x) =: y$ is defined and in this case leaves the tape as $\gamma_{\mathrm{o}}(y)$. [See remarks at end for the definition of what it means for $\gamma_{\mathrm{i}}$ and $\gamma_{\mathrm{o}}$ to be “computable”.]

So the unary encoding ($x \mapsto 1^x$) for input and output is proper. But it is emphatically not true that for any computable injections $\gamma_{\mathrm{i}}$ and $\gamma_{\mathrm{o}}$ define a proper encoding. For example, here's something you can't do with a Turing machine because the input encoding is wrong: if the integer $n \geq 1$ is encoded as a single $1$ at $n$ positions to the right of the starting head position whereas the number $0$ is encoded as a completely blank tape (i.e., $\gamma_{\mathrm{i}}(n) = 0^n 1$ for $n\geq 1$ and $\gamma_{\mathrm{i}}(0) = 0$), then the function $\mathbf{1}_{\{0\}} \colon \mathbb{N} \to \mathbb{N}$ (with value $1$ at $0$ and $0$ elsewhere) cannot be computed by a Turing machine with this (silly) encoding because the machine can never be sure if there is a $1$ somewhere on the tape: so distinguishing a nonzero value becomes semi-computable and no longer computable for (input) encoding reasons.

I suspect there are also limitations due to the output encoding. Specifically, I suspect that if $\gamma_{\mathrm{o}}$ is surjective (any tape configuration is attained). it can never be part of a proper encoding. (The reason for my belief is that the Turing machine needs to use its tape as memory even as part of the writing process, so if you ask it to be able to write any tape, something will conflict with the use as memory. But I have not been able to make this argument precise.)

Anyway, my QUESTIONS are:

• Is there a standard term for what I call “computably proper” encodings above? Has the notion been studied in any detail?

• Is it correct that there are limitations due to the output encoding and not just the input one? Namely, that not every $\gamma_{\mathrm{o}}$ can be part of a proper encoding? Specifically, is it correct that a surjective $\gamma_{\mathrm{o}}$ is never proper (or at least isn't when $\gamma_{\mathrm{i}}$ is the unary encoding)?

• Even the following point escapes me: is the condition “$(\gamma_{\mathrm{i}}, \gamma_{\mathrm{o}})$ is proper” the conjunction of a property on $\gamma_{\mathrm{i}}$ and one on $\gamma_{\mathrm{o}}$?

---

Remarks (2023-11-19): The question has now been satisfactorily answered, but let me clarify a few points that have been raised in the comments.

✱ “What does it mean for $\gamma_{\mathrm{i}}$ and $\gamma_{\mathrm{o}}$ to be computable?”

I didn't want to lengthen the question by defining a notion that I think is standard, but since the context led to a lot of misunderstanding, here it is:

A map $\gamma$ from $\mathbb{N}$ to the set $\mathrm{Tape}$ of all possible tapes with only finitely many $1$'s on them (together with a marked head position) is computable when $\gamma = \gamma_{\mathrm{std}} \circ g$ where $g \colon \mathbb{N} \to \mathbb{N}^2$ is a computable function (in the standard sense, e.g., Herbrand-Gödel-Kleene general recursive) and $\gamma_{\mathrm{std}} \colon \mathbb{N}^2 \to \mathrm{Tape}$ takes a pair of natural numbers $n_0,n_1$ and returns the tape where $n_0$ is written in binary, left-to-right with the least significant bit first, starting from the head position, and $n_1$ is written in binary, right-to-left with the least significant bit first, starting just left of the head position (so for example $\gamma_{\mathrm{std}}(26,14)$ produces the tape $1110\underline{0}1011$ with the head at the underlined $0$, since $26$ is $11010$ in binary and $14$ is $1110$ in binary, all other symbols being, of course, $0$).

Sorry for the excruciating details here, which of course aren't important (this is what anyone would call a “computable” function from $\mathbb{N}$ to $\mathrm{Tape}$), but the context of the question seems to have caused confusion. The important thing is that from $n$ we can compute any reasonable complete description of $\gamma(n)$ and $\gamma_{\mathrm{std}}$ is just there to formalize what I mean by a “reasonable complete description” without waving my hands: we need to be able to compute the list of all $1$'s on the tape (relative to the head position).

Note that $\gamma_{\mathrm{std}}$ is not proper as an input encoding (this is probably what caused much of the confusion): indeed, I need it to be surjective to define all other computable encodings, and if $\gamma_{\mathrm{std}}$ were proper then any encoding would be proper, which is ont the case as I point out.

✱ “What is the point of this question?”

Of course this doesn't tell us anything new about computable functions but it tells us something about what Turing Machines can do. Turing machines can compute exactly computable functions when (and only when) we use a proper encoding, but if we're interested in Turing Machines per se (and not just as an instrument to define computable functions) and what they can do, then I think it's at least worth taking the time to ask what it means for an encoding to be “proper” rather than imposing it once and for all (as in the unary encoding).

Given the historical importance of Turing Machines, I think it's worth trying to understand a bit more precisely how input and output encodings affect what they can do.

Specifically, this question occurred in my teaching in at least two contexts:

• Clearing up confusion on the students' part regarding the issue “how come a Turing machine can't detect whether there's the tape is entirely blank whereas any singleton is decidable?” — I think this is a very valid issue to be raised (at least when teaching) and this concerns the input encoding.

• Trying to write an exercise of the form “show that there is a Turing machine which writes its own program on the tape, then stops”, where I wanted the output format to be something a little more transparent than a number in unary that encodes the program in a complicated way (which pedagogically seems very much like cheating): but for the exercise to work we need to chose an output encoding that is proper (and thanks to Joel David Hamkins's answer, we know that any one will do).

Answer 1

I claim that surjective output encodings $\gamma_{\mathrm{o}}$ are possible, and indeed, every output encoding $\gamma_o$ is allowed as part of a proper encoding.

First, I claim that we we can arrange that a Turing machine computation is tidy, in that the output tape is exactly $1^y$ for output $y$, with all $0$s after this. One simply arranges that the machine keeps track of how much space it is using, with suitable markers, and it undertakes a clean-up session after the main computation is complete, to erase everything after the main output.

Next, there is a surjective primitive recursive function mapping $\mathbb{N}$ to all finitely supported strings, and we can undertake a supplementary computation to transform $1^y$ to any desired finite string. We simply reserve $1^y$ in a space with suitable markers. We produce a stretched copy of the corresponding desired output string (stretched, meaning that we use every other cell, in order to allow markers in the other cells). Ultimately, we will create a stretched copy of the desired output string. Now, finally, we perform a copying collapse process that copies the stretched cell to the desired place unstretched (with markers to indicate the progress). In the end, we leave the desired finite string encoding $y$ on the tape.

The argument works with any $\gamma_{\mathrm{o}}$. Basically, first compute $f(x)=y$ with your favorite encoding. Then tidy up. Then compute $\gamma_{\mathrm{o}}(y)$, but stretched. Then tidy up. Then collapse the stretched version to be unstretched.

It follows that the question whether $(\gamma_{\mathrm{i}},\gamma_{\mathrm{o}})$ is a proper encoding reduces to a question about $\gamma_{\mathrm{i}}$ alone.

Answer 2

For convenience, I will change the problem conventions slightly: instead of viewing encodings like $\gamma_i$ and $\gamma_o$ as functions from $\mathbb{N}$ to infinite binary strings with finitely many 1s, I view them as functions from $\mathbb{N}$ to $\mathbb{N}$, where the "original" encoding output strings are the binary representations of the encoding output naturals. (Thus, a pair $(\gamma_i, \gamma_o)$ is proper iff for all partial computable function $f$, there exists a Turing machine that, given $\gamma_i(x)$ in binary on its input tape, outputs $\gamma_o(x)$ in binary)

Let $U$ be the standard unary encoding. (Thus, for example, “$(\gamma_i, U)$ is proper” translates to “for all $f$ partial computable, there exists a TM that outputs $f(x)$ in unary given $\gamma_i(x)$ in binary”, since $U(f(x))$ in binary is $f(x)$ in unary.)

Claim 1: For all $γ_i, γ_o$, if $(γ_i, U)$ is proper, then $(γ_i, γ_o)$ is proper.

Proof: Assume $(γ_i, U)$ is proper. Let $f: ℕ ⇢ ℕ$ be a partial computable function. By assumption, there exists a Turing machine that outputs $f(x)$ in unary given $γ_i(x)$ in binary (for all $x$ such that $f(x)$ is defined). You can compose this TM with a TM computing $γ_o$ (i.e., computing $γ_o(x)$ in unary given $x$ in unary), obtaining a TM that outputs $γ_o(x)$ in unary given $γ_i(x)$ in binary. It only remains to compose this TM with a TM that converts unary to binary. It's not too hard, though tedious, to show that such a TM exists. One strategy is to expand the unary representation to use every other cell only, then iteratively divide this unary representation by 2, writing the remainder on the virtual tape that is liberated by the expansion on every other cell, and finally compress the result.

Claim 2: For all $γ_i, γ_o$, if $(γ_i, γ_o)$ is proper, then $(γ_i, U)$ is proper.

Proof: Assume $(γ_i, γ_o)$ is proper and let $f: ℕ ⇢ ℕ$ be a partial computable function. There exists a Turing machine $M$ that outputs $γ_o(f(x))$ in binary given $γ_i(x)$ in binary. Let $T$ be a Turing machine that does the following. Given $γ_i(x)$ in binary, $T$ first simulates $M$ on $γ_i(x)$. Thus, $T$ gets $γ_o(f(x))$, in unary.

(Depending on your formalization of computability, you might complain here, saying that a universal Turing machine should take a Turing machine that outputs in unary format and simulate it. But you could apply the same type of construction to build a universal Turing machine that takes in unary a pair of a Turing machine $A$ and an input $x$, and returns in unary the output of $A$ when applied to $x$ in binary, with the output of $A$ interpreted as binary and converted to unary by the Turing machine. This is all just tedious but trivial encoding details.)

Now that $T$ has $γ_o(f(x))$ in unary, it can compute $f(x)$ in unary. Let $G$ be a Turing machine that computes $γ_o$. It suffices for $T$ to launch parallel computations of $G$ on all integers, using a standard technique like: run one step of $G$ on the integer 1, then one step on 1 and one step on 2, then one step on 1, one step on 2 and one step on 3, and so on. Since we know that $γ_o(f(x))$ has a preimage by $γ_o$, this will at some point terminate and find the said preimage, $f(x)$.

Combining these claims, we get that whether $(γ_i, γ_o)$ is proper only depends on $γ_i$. (Thus, let me write “$γ_i$ is proper” instead of “$(γ_i, U)$ is proper”.)

Assume $γ_i$ is proper. By applying the definition of “proper” to the identity function (which is computable), we obtain that there exists a Turing machine that, given $γ_i(x)$ in binary, outputs $x$ in unary.

Conversely, suppose that $γ_i$ is such that there is a Turing machine computing $x$ in unary from $γ_i(x)$ in binary. Let $f: ℕ ⇢ ℕ$ partial computable. We can build a Turing machine that outputs $f(x)$ in unary given $γ_i(x)$ in binary. Indeed, it suffices to compose the Turing machine that builds $x$ in unary from $γ_i(x)$ in binary, with a standard Turing machine computing $f(x)$ in unary from $x$ in unary.

This gives us a reasonably simple criterion: $γ_i$ is proper iff there exists a Turing machine that, given the tape $γ_i(x)$, can reconstruct $x$ (in unary).

As a small further simplification: $γ_i$ is proper iff there exists a Turing machine $X$ that, when run on the tape $γ_i(x)$, can compute a bound on the length of the tape $γ_i(x)$ (i.e., an integer $n$ such that all values on the tape are 0 after index $n$).

Indeed, if $X$ exists, then we can build a TM that reconstructs $x$ (in unary) from $γ_i(x)$ (in binary), by first applying $X$ to get an upper bound on the length of the tape, which gives it access to $γ_i(x)$ in unary (now that it knows where it stops), and then trying integers in parallel to find the preimage of $γ_i(x)$ by $γ_i$. Conversely, if $x$ (in unary) can be computably reconstructed from $γ_i(x)$ (in binary), using a certain Turing machine $M$, then we can construct a Turing machine that uses $M$ to find $x$ in unary from $γ_i(x)$ in binary, then computes $γ_i(x)$ in unary, and outputs the log in base 2 of the length of $γ_i(x)$ in unary.

Bottom line: $(γ_i, γ_o)$ is proper iff there exists a Turing machine that computes a bound on the length of the tape $γ_i(x)$ when run on it. I don't believe this can be further simplified much. Essentially, your counterexample with $0^n 1$ is the “only type” of counterexample in a certain sense: if the encoding doesn't work, it must be because we cannot know where the input ends.

You didn't ask it, but I find this to be an interesting question: what happens if we don't require $γ_i$ and $γ_o$ to be computable anymore?

It's not too hard to see that whether $(γ_i, γ_o)$ is proper now depends on $γ_o$. For example, let $(u_n)$ be an uncomputable infinite sequence of bits (e.g., $u_n = 1$ iff the $n$-th Turing machine terminates on the empty input, for some standard encoding of Turing machines). Define the encoding $E$ like this: to compute $E(n)$, write $n$ in unary on every other bit, and fill up every other bit until the end of the unary word with a prefix of the sequence $(u_n)$. Now, $(U, U)$ is proper (obviously) but $(U, E)$ is not proper, because if it were proper, by applying the definition of “proper” to the identity function, you could build a Turing machine computing as many bits of $(u_n)$ as its input requests.

I found it harder, though, to prove that in this new setting, “$(γ_i, γ_o)$ is proper” is no longer even a conjunction of a property (say $A$) of $γ_i$ and a property (say $B$) of $γ_o$. To show this, it suffices to exhibit an encoding $F$ such that $(F, E)$ is proper. Indeed, if $(F, E)$ is proper, then $B(E)$ is true; since $(U, U)$ is proper, $A(U)$ is true, and since $(U, E)$ is not proper, $B(E)$ must be false, contradiction.

To build such an $F$, a possibility is the following. Divide the input tape in two interwoven tapes. Then $F(x)$ is constructed like this: on the first tape, $x$ in unary; on the second tape, a unary representation of the binary number formed by $BB(x)$ initial bits of $(u_n)$. Here, $(u_n)$ is the same sequence than the one used to defined $E$, and $BB(x)$ is the busy beaver function applied to $x$ (i.e., the length of $x$ in unary).

I claim that $(F, E)$ is proper. To see this, let $f: ℕ ⇢ ℕ$ partial computable. We build a Turing machine $T$ that computes $E(f(x))$ in binary from $F(x)$ in binary (for all $x$ such that $f(x)$ is defined). The machine we are building receives $F(x)$, which gives it access to both $x$ and $BB(x)$ bits of $(u_n)$. Recall that the desired output has two interleaved tapes, containing $f(x)$ in unary, and a prefix of $(u_n)$ in binary, of length $f(x)$. Now, $x$ is part of the output is already contained in the input, so we can just compute $f(x)$ (since $f$ is partial computable) and write that to one of our interleaved output tapes. Furthermore, we have access to $BB(x)$ bits of $(u_n)$. Recall that the busy beaver function grows asymptotically faster than any computable function, in particular, than $f$. Thus our Turing machine $T$ can do the following: if $BB(x) ≥ f(x)$, then copy the required $f(x)$ bits of $(u_n)$ from the input; the other case happens for finitely many values of $x$, so the Turing machine can just use a precomputed table of some fixed finite prefix of $(u_n)$, encoded in its transition table.