<p>I claim that surjective output encodings <span class="math-container">$\gamma_{\mathrm{o}}$</span> are possible, and indeed, every output encoding <span class="math-container">$\gamma_o$</span> is allowed as part of a proper encoding.</p>
<p>First, I claim that we we can arrange that a Turing machine computation is tidy, in that the output tape is exactly <span class="math-container">$1^y$</span> for output <span class="math-container">$y$</span>, with all <span class="math-container">$0$</span>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.</p>
<p>Next, there is a surjective primitive recursive function mapping <span class="math-container">$\mathbb{N}$</span> to all finitely supported strings, and we can undertake a supplementary computation to transform <span class="math-container">$1^y$</span> to any desired finite string. We simply reserve <span class="math-container">$1^y$</span> 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 <span class="math-container">$y$</span> on the tape.</p>
<p>The argument works with any <span class="math-container">$\gamma_{\mathrm{o}}$</span>. Basically, first compute <span class="math-container">$f(x)=y$</span> with your favorite encoding. Then tidy up. Then compute <span class="math-container">$\gamma_{\mathrm{o}}(y)$</span>, but stretched. Then tidy up. Then collapse the stretched version to be unstretched.</p>
<p>It follows that the question whether <span class="math-container">$(\gamma_{\mathrm{i}},\gamma_{\mathrm{o}})$</span> is a proper encoding reduces to a question about <span class="math-container">$\gamma_{\mathrm{i}}$</span> alone.</p>

CC BY-SA 4.0
2023-11-18T13:18:31.947Z
2023-11-18T16:21:21.653Z
2023-11-18T16:21:21.653Z
JDH
<p>For convenience, I will change the problem conventions slightly: instead of viewing encodings like <span class="math-container">$\gamma_i$</span> and <span class="math-container">$\gamma_o$</span> as functions from <span class="math-container">$\mathbb{N}$</span> to infinite binary strings with finitely many 1s, I view them as functions from <span class="math-container">$\mathbb{N}$</span> to <span class="math-container">$\mathbb{N}$</span>, where the &quot;original&quot; encoding output strings are the binary representations of the encoding output naturals. (Thus, a pair <span class="math-container">$(\gamma_i, \gamma_o)$</span> is proper iff for all partial computable function <span class="math-container">$f$</span>, there exists a Turing machine that, given <span class="math-container">$\gamma_i(x)$</span> in binary on its input tape, outputs <span class="math-container">$\gamma_o(x)$</span> in binary)</p>
<p>Let <span class="math-container">$U$</span> be the standard unary encoding. (Thus, for example, “<span class="math-container">$(\gamma_i, U)$</span> is proper” translates to “for all <span class="math-container">$f$</span> partial computable, there exists a TM that outputs <span class="math-container">$f(x)$</span> in unary given <span class="math-container">$\gamma_i(x)$</span> in binary”, since <span class="math-container">$U(f(x))$</span> in binary is <span class="math-container">$f(x)$</span> in unary.)</p>
<p>Claim 1: For all <span class="math-container">$γ_i, γ_o$</span>, if <span class="math-container">$(γ_i, U)$</span> is proper, then <span class="math-container">$(γ_i, γ_o)$</span> is proper.</p>
<p>Proof: Assume <span class="math-container">$(γ_i, U)$</span> is proper. Let <span class="math-container">$f: ℕ ⇢ ℕ$</span> be a partial computable function. By assumption, there exists a Turing machine that outputs <span class="math-container">$f(x)$</span> in unary given <span class="math-container">$γ_i(x)$</span> in binary (for all <span class="math-container">$x$</span> such that <span class="math-container">$f(x)$</span> is defined). You can compose this TM with a TM computing <span class="math-container">$γ_o$</span> (i.e., computing <span class="math-container">$γ_o(x)$</span> in unary given <span class="math-container">$x$</span> in unary), obtaining a TM that outputs <span class="math-container">$γ_o(x)$</span> in unary given <span class="math-container">$γ_i(x)$</span> 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.</p>
<p>Claim 2: For all <span class="math-container">$γ_i, γ_o$</span>, if <span class="math-container">$(γ_i, γ_o)$</span> is proper, then <span class="math-container">$(γ_i, U)$</span> is proper.</p>
<p>Proof: Assume <span class="math-container">$(γ_i, γ_o)$</span> is proper and let <span class="math-container">$f: ℕ ⇢ ℕ$</span> be a partial computable function. There exists a Turing machine <span class="math-container">$M$</span> that outputs <span class="math-container">$γ_o(f(x))$</span> in binary given <span class="math-container">$γ_i(x)$</span> in binary. Let <span class="math-container">$T$</span> be a Turing machine that does the following. Given <span class="math-container">$γ_i(x)$</span> in binary, <span class="math-container">$T$</span> first simulates <span class="math-container">$M$</span> on <span class="math-container">$γ_i(x)$</span>. Thus, <span class="math-container">$T$</span> gets <span class="math-container">$γ_o(f(x))$</span>, in unary.</p>
<p>(Depending on your formalization of computability, you might complain here, saying that a universal Turing machine should take a Turing machine <em>that outputs in unary format</em> and simulate it. But you could apply the same type of construction to build a universal Turing machine that takes <em>in unary</em> a pair of a Turing machine <span class="math-container">$A$</span> and an input <span class="math-container">$x$</span>, and returns <em>in unary</em> the output of <span class="math-container">$A$</span> when applied to <span class="math-container">$x$</span> <em>in binary</em>, with the output of <span class="math-container">$A$</span> interpreted as binary and converted to unary by the Turing machine. This is all just tedious but trivial encoding details.)</p>
<p>Now that <span class="math-container">$T$</span> has <span class="math-container">$γ_o(f(x))$</span> in unary, it can compute <span class="math-container">$f(x)$</span> in unary. Let <span class="math-container">$G$</span> be a Turing machine that computes <span class="math-container">$γ_o$</span>. It suffices for <span class="math-container">$T$</span> to launch parallel computations of <span class="math-container">$G$</span> on all integers, using a standard technique like: run one step of <span class="math-container">$G$</span> 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 <span class="math-container">$γ_o(f(x))$</span> has a preimage by <span class="math-container">$γ_o$</span>, this will at some point terminate and find the said preimage, <span class="math-container">$f(x)$</span>.</p>
<p>Combining these claims, we get that whether <span class="math-container">$(γ_i, γ_o)$</span> is proper only depends on <span class="math-container">$γ_i$</span>. (Thus, let me write “<span class="math-container">$γ_i$</span> is proper” instead of “<span class="math-container">$(γ_i, U)$</span> is proper”.)</p>
<p>Assume <span class="math-container">$γ_i$</span> 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 <span class="math-container">$γ_i(x)$</span> in binary, outputs <span class="math-container">$x$</span> in unary.</p>
<p>Conversely, suppose that <span class="math-container">$γ_i$</span> is such that there is a Turing machine computing <span class="math-container">$x$</span> in unary from <span class="math-container">$γ_i(x)$</span> in binary. Let <span class="math-container">$f: ℕ ⇢ ℕ$</span> partial computable. We can build a Turing machine that outputs <span class="math-container">$f(x)$</span> in unary given <span class="math-container">$γ_i(x)$</span> in binary. Indeed, it suffices to compose the Turing machine that builds <span class="math-container">$x$</span> in unary from <span class="math-container">$γ_i(x)$</span> in binary, with a standard Turing machine computing <span class="math-container">$f(x)$</span> in unary from <span class="math-container">$x$</span> in unary.</p>
<p>This gives us a reasonably simple criterion: <span class="math-container">$γ_i$</span> is proper iff there exists a Turing machine that, given the tape <span class="math-container">$γ_i(x)$</span>, can reconstruct <span class="math-container">$x$</span> (in unary).</p>
<p>As a small further simplification: <span class="math-container">$γ_i$</span> is proper iff there exists a Turing machine <span class="math-container">$X$</span> that, when run on the tape <span class="math-container">$γ_i(x)$</span>, can compute a bound on the length of the tape <span class="math-container">$γ_i(x)$</span> (i.e., an integer <span class="math-container">$n$</span> such that all values on the tape are 0 after index <span class="math-container">$n$</span>).</p>
<p>Indeed, if <span class="math-container">$X$</span> exists, then we can build a TM that reconstructs <span class="math-container">$x$</span> (in unary) from <span class="math-container">$γ_i(x)$</span> (in binary), by first applying <span class="math-container">$X$</span> to get an upper bound on the length of the tape, which gives it access to <span class="math-container">$γ_i(x)$</span> in unary (now that it knows where it stops), and then trying integers in parallel to find the preimage of <span class="math-container">$γ_i(x)$</span> by <span class="math-container">$γ_i$</span>. Conversely, if <span class="math-container">$x$</span> (in unary) can be computably reconstructed from <span class="math-container">$γ_i(x)$</span> (in binary), using a certain Turing machine <span class="math-container">$M$</span>, then we can construct a Turing machine that uses <span class="math-container">$M$</span> to find <span class="math-container">$x$</span> in unary from <span class="math-container">$γ_i(x)$</span> in binary, then computes <span class="math-container">$γ_i(x)$</span> in unary, and outputs the log in base 2 of the length of <span class="math-container">$γ_i(x)$</span> in unary.</p>
<p>Bottom line: <span class="math-container">$(γ_i, γ_o)$</span> is proper iff there exists a Turing machine that computes a bound on the length of the tape <span class="math-container">$γ_i(x)$</span> when run on it. I don't believe this can be further simplified much. Essentially, your counterexample with <span class="math-container">$0^n 1$</span> 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.</p>
<p>You didn't ask it, but I find this to be an interesting question: what happens if we don't require <span class="math-container">$γ_i$</span> and <span class="math-container">$γ_o$</span> to be computable anymore?</p>
<p>It's not too hard to see that whether <span class="math-container">$(γ_i, γ_o)$</span> is proper now depends on <span class="math-container">$γ_o$</span>. For example, let <span class="math-container">$(u_n)$</span> be an uncomputable infinite sequence of bits (e.g., <span class="math-container">$u_n = 1$</span> iff the <span class="math-container">$n$</span>-th Turing machine terminates on the empty input, for some standard encoding of Turing machines). Define the encoding <span class="math-container">$E$</span> like this: to compute <span class="math-container">$E(n)$</span>, write <span class="math-container">$n$</span> 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 <span class="math-container">$(u_n)$</span>. Now, <span class="math-container">$(U, U)$</span> is proper (obviously) but <span class="math-container">$(U, E)$</span> 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 <span class="math-container">$(u_n)$</span> as its input requests.</p>
<p>I found it harder, though, to prove that in this new setting, “<span class="math-container">$(γ_i, γ_o)$</span> is proper” is no longer even a conjunction of a property (say <span class="math-container">$A$</span>) of <span class="math-container">$γ_i$</span> and a property (say <span class="math-container">$B$</span>) of <span class="math-container">$γ_o$</span>. To show this, it suffices to exhibit an encoding <span class="math-container">$F$</span> such that <span class="math-container">$(F, E)$</span> is proper. Indeed, if <span class="math-container">$(F, E)$</span> is proper, then <span class="math-container">$B(E)$</span> is true; since <span class="math-container">$(U, U)$</span> is proper, <span class="math-container">$A(U)$</span> is true, and since <span class="math-container">$(U, E)$</span> is not proper, <span class="math-container">$B(E)$</span> must be false, contradiction.</p>
<p>To build such an <span class="math-container">$F$</span>, a possibility is the following. Divide the input tape in two interwoven tapes. Then <span class="math-container">$F(x)$</span> is constructed like this: on the first tape, <span class="math-container">$x$</span> in unary; on the second tape, a unary representation of the binary number formed by <span class="math-container">$BB(x)$</span> initial bits of <span class="math-container">$(u_n)$</span>. Here, <span class="math-container">$(u_n)$</span> is the same sequence than the one used to defined <span class="math-container">$E$</span>, and <span class="math-container">$BB(x)$</span> is the busy beaver function applied to <span class="math-container">$x$</span> (i.e., the length of <span class="math-container">$x$</span> in unary).</p>
<p>I claim that <span class="math-container">$(F, E)$</span> is proper. To see this, let <span class="math-container">$f: ℕ ⇢ ℕ$</span> partial computable. We build a Turing machine <span class="math-container">$T$</span> that computes <span class="math-container">$E(f(x))$</span> in binary from <span class="math-container">$F(x)$</span> in binary (for all <span class="math-container">$x$</span> such that <span class="math-container">$f(x)$</span> is defined). The machine we are building receives <span class="math-container">$F(x)$</span>, which gives it access to both <span class="math-container">$x$</span> and <span class="math-container">$BB(x)$</span> bits of <span class="math-container">$(u_n)$</span>. Recall that the desired output has two interleaved tapes, containing <span class="math-container">$f(x)$</span> in unary, and a prefix of <span class="math-container">$(u_n)$</span> in binary, of length <span class="math-container">$f(x)$</span>. Now, <span class="math-container">$x$</span> is part of the output is already contained in the input, so we can just compute <span class="math-container">$f(x)$</span> (since <span class="math-container">$f$</span> is partial computable) and write that to one of our interleaved output tapes. Furthermore, we have access to <span class="math-container">$BB(x)$</span> bits of <span class="math-container">$(u_n)$</span>. Recall that the busy beaver function grows asymptotically faster than any computable function, in particular, than <span class="math-container">$f$</span>. Thus our Turing machine <span class="math-container">$T$</span> can do the following: if <span class="math-container">$BB(x) ≥ f(x)$</span>, then copy the required <span class="math-container">$f(x)$</span> bits of <span class="math-container">$(u_n)$</span> from the input; the other case happens for finitely many values of <span class="math-container">$x$</span>, so the Turing machine can just use a precomputed table of some fixed finite prefix of <span class="math-container">$(u_n)$</span>, encoded in its transition table.</p>

CC BY-SA 4.0
2023-11-18T22:18:56.057Z
I agree with your main conclusions—indeed, the main part of your post is essentially the same as my answer—nevertheless I find parts of your post puzzling or nonsensical. For example, you refer to using input in binary, but of course this is not generally possible in the 2-symbol alphabet, for reasons explained in the OP. Also, what do you mean by "given $\gamma_{\mathrm{i}}(x)$ in binary" and "output $\gamma_{\textrm{o}}(x)$ in unary", given that the former are infinite binary strings? Is this somehow part of the "identification" of integers with finitely-supported infinite binary strings?
JDH
CC BY-SA 4.0
2023-11-18T23:05:43.547Z
By "given $γ_i(x)$ in binary" I mean "when the input tape is initialized with the binary representation of $γ_i(x)$ (padded with infinitely many zeros)". This was basically a way to avoid sprinkling the whole answer with phrases like "the interpretation of the input tape [that has finitely many 1s] as a number in binary", "the encoding of the input tape into a word in unary" (by converting to an integer through binary representation then encoding that integer in unary), etc. "Input" is meant as "initial state", not necessarily something you can delimit upfront (since that's the whole question)
user70521
CC BY-SA 4.0
2023-11-19T00:28:59.357Z
"binary representation of $\gamma_{\mathrm{i}}(x)$" makes no sense, since $\gamma_{\mathrm{i}}(x)$ is already an infinite binary string (and there is no need for padding, since it is already infinite). Unless I have misunderstood, I think you have a different understanding of the notation here than the OP.
JDH
CC BY-SA 4.0
2023-11-19T00:54:16.547Z
Since I am identifying binary strings with natural numbers I am also viewing $\gamma_i$ as a map $\mathbb{N} \to \mathbb{N}$. Then the binary representation of $\gamma_i(x)$ is the "original" $\gamma_i(x)$ and its unary representation is a way to encode the original for inputting it to a TM that uses the unary input convention. You might find this a stretch, but after all, the canonical definition of a computable function applies to functions $\mathbb{N} \to \mathbb{N}$ (e.g., recursive functions), so the assumption that $\gamma_i$ is computable already makes this type of identification.
Jean Abou Samra
CC BY-SA 4.0
2023-11-19T01:20:15.810Z
Said differently, it's just that instead of speaking of an infinite, finitely supported binary string (X), its representation as a natural through binary encoding (Y) and the conversion of that back into an infinite finitely supported binary string using unary decoding (Z), I find it simpler and more concrete to speak about a natural (Y), its binary representation (X) and its unary representation (Z).
Jean Abou Samra
CC BY-SA 4.0
2023-11-19T01:43:39.627Z
@JDH I have attempted to clarify this in the answer.
user70521
CC BY-SA 4.0
2023-11-18T19:18:57.943Z
2023-11-19T01:43:09.913Z
2023-11-19T01:43:09.913Z
user70521
<p><strong>Convention:</strong> 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 <span class="math-container">$2$</span>-symbol <span class="math-container">$1$</span>-tape machine with <span class="math-container">$m$</span> states for some <span class="math-container">$m\geq 1$</span>, its program is a function <span class="math-container">$\delta \colon Q \times \Sigma \to (Q\cup \{0\}) \times \Sigma \times \{ \mathtt{L}, \mathtt{R} \}$</span> where <span class="math-container">$Q = \{1,\ldots,m\}$</span> is the set of states, <span class="math-container">$\Sigma = \{0,1\}$</span> is the set of tape symbols and <span class="math-container">$\mathtt{L}, \mathtt{R}$</span> stand for the directions left and right in which the head may move.  The tape will always be filled with <span class="math-container">$0$</span>'s except for finitely many <span class="math-container">$1$</span>'s.  The machine always starts execution in state <span class="math-container">$1$</span> and stops when it reaches the state <span class="math-container">$0$</span>.</p>
<p>We know Turing machines can compute any computable function, in the sense that there is a <em>proper encoding</em> of input and output values such that any computable function can be computed by some program.  Very specifically, for each <span class="math-container">$f \colon \mathbb{N} \dashrightarrow \mathbb{N}$</span> partial computable, there is a Turing machine <span class="math-container">$M_f$</span> such that if <span class="math-container">$M_f$</span> is run from a tape containing the number <span class="math-container">$x$</span> written in unary immediately after the starting head position (i.e., the tape starts as <span class="math-container">$1^x$</span> with the head at the leftmost <span class="math-container">$1$</span>, and the rest is filled with <span class="math-container">$0$</span>'s), the machine terminates in finite time iff <span class="math-container">$f(x) =: y$</span> is defined, and, if so, returns a tape in the form <span class="math-container">$1^y$</span> with the head at the same position as initially.</p>
<p>When studying computability, the details of the encoding aren't very interesting, but the point is <em>some encoding is necessary</em> and <em>it can't be arbitrary</em>:</p>
<p><strong>Definition:</strong> Let us say that two computable injections <span class="math-container">$\gamma_{\mathrm{i}}$</span> and <span class="math-container">$\gamma_{\mathrm{o}}$</span> (the “input encoding” and “output encoding” respectively) of <span class="math-container">$\mathbb{N}$</span> in the set of all possible tapes with only finitely many <span class="math-container">$1$</span>'s on them (together with a marked head position) are a <strong>(computably) proper</strong> encoding [my terminology] when, for any <span class="math-container">$f \colon \mathbb{N} \dashrightarrow \mathbb{N}$</span> partial computable, there is a Turing machine <span class="math-container">$M_f$</span> such that <span class="math-container">$M_f$</span> terminates on <span class="math-container">$\gamma_{\mathrm{i}}(x)$</span> iff <span class="math-container">$f(x) =: y$</span> is defined and in this case leaves the tape as <span class="math-container">$\gamma_{\mathrm{o}}(y)$</span>.  [See remarks at end for the definition of what it means for <span class="math-container">$\gamma_{\mathrm{i}}$</span> and <span class="math-container">$\gamma_{\mathrm{o}}$</span> to be “computable”.]</p>
<p>So the unary encoding (<span class="math-container">$x \mapsto 1^x$</span>) for input and output is proper.  But it is <strong>emphatically not</strong> true that for any computable injections <span class="math-container">$\gamma_{\mathrm{i}}$</span> and <span class="math-container">$\gamma_{\mathrm{o}}$</span> define a proper encoding.  For example, here's something you <em>can't</em> do with a Turing machine because the input encoding is wrong: if the integer <span class="math-container">$n \geq 1$</span> is encoded as a single <span class="math-container">$1$</span> at <span class="math-container">$n$</span> positions to the right of the starting head position whereas the number <span class="math-container">$0$</span> is encoded as a completely blank tape (i.e., <span class="math-container">$\gamma_{\mathrm{i}}(n) = 0^n 1$</span> for <span class="math-container">$n\geq 1$</span> and <span class="math-container">$\gamma_{\mathrm{i}}(0) = 0$</span>), then the function <span class="math-container">$\mathbf{1}_{\{0\}} \colon \mathbb{N} \to \mathbb{N}$</span> (with value <span class="math-container">$1$</span> at <span class="math-container">$0$</span> and <span class="math-container">$0$</span> elsewhere) cannot be computed by a Turing machine with this (silly) encoding because the machine can never be sure if there is a <span class="math-container">$1$</span> somewhere on the tape: so distinguishing a nonzero value becomes semi-computable and no longer computable for (input) encoding reasons.</p>
<p>I suspect there are also limitations due to the <em>output</em> encoding.  Specifically, I suspect that if <span class="math-container">$\gamma_{\mathrm{o}}$</span> 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 <em>any</em> tape, something will conflict with the use as memory.  But I have not been able to make this argument precise.)</p>
<p>Anyway, my <strong>QUESTIONS</strong> are:</p>
<ul>
<li><p>Is there a standard term for what I call “computably proper” encodings above?  Has the notion been studied in any detail?</p>
</li>
<li><p>Is it correct that there are limitations due to the output encoding and not just the input one?  Namely, that not every <span class="math-container">$\gamma_{\mathrm{o}}$</span> can be part of a proper encoding?  Specifically, is it correct that a surjective <span class="math-container">$\gamma_{\mathrm{o}}$</span> is <em>never</em> proper (or at least isn't when <span class="math-container">$\gamma_{\mathrm{i}}$</span> is the unary encoding)?</p>
</li>
<li><p>Even the following point escapes me: is the condition “<span class="math-container">$(\gamma_{\mathrm{i}}, \gamma_{\mathrm{o}})$</span> is proper” the conjunction of a property on <span class="math-container">$\gamma_{\mathrm{i}}$</span> and one on <span class="math-container">$\gamma_{\mathrm{o}}$</span>?</p>
</li>
</ul>
<hr />
<p><strong>Remarks</strong> (2023-11-19): The question has now been satisfactorily answered, but let me clarify a few points that have been raised in the comments.</p>
<p>✱ “What does it mean for <span class="math-container">$\gamma_{\mathrm{i}}$</span> and <span class="math-container">$\gamma_{\mathrm{o}}$</span> to be computable?”</p>
<p>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:</p>
<p>A map <span class="math-container">$\gamma$</span> from <span class="math-container">$\mathbb{N}$</span> to the set <span class="math-container">$\mathrm{Tape}$</span> of all possible tapes with only finitely many <span class="math-container">$1$</span>'s on them (together with a marked head position) is <strong>computable</strong> when <span class="math-container">$\gamma = \gamma_{\mathrm{std}} \circ g$</span> where <span class="math-container">$g \colon \mathbb{N} \to \mathbb{N}^2$</span> is a computable function (in the standard sense, e.g., Herbrand-Gödel-Kleene general recursive) and <span class="math-container">$\gamma_{\mathrm{std}} \colon \mathbb{N}^2 \to \mathrm{Tape}$</span> takes a pair of natural numbers <span class="math-container">$n_0,n_1$</span> and returns the tape where <span class="math-container">$n_0$</span> is written in binary, left-to-right with the least significant bit first, starting from the head position, and <span class="math-container">$n_1$</span> is written in binary, right-to-left with the least significant bit first, starting just left of the head position (so for example <span class="math-container">$\gamma_{\mathrm{std}}(26,14)$</span> produces the tape <span class="math-container">$1110\underline{0}1011$</span> with the head at the underlined <span class="math-container">$0$</span>, since <span class="math-container">$26$</span> is <span class="math-container">$11010$</span> in binary and <span class="math-container">$14$</span> is <span class="math-container">$1110$</span> in binary, all other symbols being, of course, <span class="math-container">$0$</span>).</p>
<p>Sorry for the excruciating details here, which of course aren't important (this is what anyone would call a “computable” function from <span class="math-container">$\mathbb{N}$</span> to <span class="math-container">$\mathrm{Tape}$</span>), but the context of the question seems to have caused confusion.  The important thing is that from <span class="math-container">$n$</span> we can compute any reasonable complete description of <span class="math-container">$\gamma(n)$</span> and <span class="math-container">$\gamma_{\mathrm{std}}$</span> 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 <span class="math-container">$1$</span>'s on the tape (relative to the head position).</p>
<p>Note that <span class="math-container">$\gamma_{\mathrm{std}}$</span> is <em>not</em> 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 <span class="math-container">$\gamma_{\mathrm{std}}$</span> were proper then any encoding would be proper, which is ont the case as I point out.</p>
<p>✱ “What is the point of this question?”</p>
<p>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 <em>per se</em> (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).</p>
<p>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.</p>
<p>Specifically, this question occurred in my teaching in at least two contexts:</p>
<ul>
<li><p>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 <em>input encoding</em>.</p>
</li>
<li><p>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 <em>output encoding</em> that is proper (and thanks to Joel David Hamkins's answer, we know that any one will do).</p>
</li>
</ul>

CC BY-SA 4.0
2023-11-18T13:17:15.210Z
When you say that $\gamma_i$ and $\gamma_o$ are computable, do you fix a default encoding of $\mathbb N$, like unary one ?

Why not imposing that $\gamma_o$ is the converse of $\gamma_i$ ? Then computably proper encoding just means that the encoding is computable both ways.
But in your framework, it seems to be just that both $\gamma_i$ and $\gamma_o$ are computable, or am I missing something ?
If your valid tapes are the ones with finitely many 1, then yes by your argument with $0^n1$ a surjective encoding can never be proper.
Denis
CC BY-SA 4.0
2023-11-18T16:19:58.717Z
@Denis Gro-Tsen's argument about $0^n1$ was for input encodings, but the surjective question was about the output encodings.
JDH
CC BY-SA 4.0
2023-11-18T19:04:22.570Z
Reiterating @Denis's question: what does it mean for $\gamma_0$ and $\gamma_1$ to be computable? Also, what is the motivation for the question? In terms of realizability, you're asking a strange question about replacing the natural numbers object with other kinds of objects.
Andrej Bauer
CC BY-SA 4.0
2023-11-18T20:05:37.130Z
They are computable in the usual sense. You can define it with unary encoding, but also with recursive functions if you prefer something outside of Turing machines (or, as always, with lambda-calculus, rewriting, and so on).
Jean Abou Samra
CC BY-SA 4.0
2023-11-18T22:22:44.017Z
@AndrejBauer I understand the point to be this: to speak of $f:\mathbb{N}\to\mathbb{N}$ being computable, we must represent numbers somehow on the tape, and there are choices about how to do that. These are the "encodings". To say that they are computable means simply that if we use the standard unary coding, then the map from numbers to string is computable in the ordinary sense. The point now is that we can't use bad input encodings, since we won't recognize the end of the input, but the Q is whether there is a limitation on the output encodings, and I argue in my answer that there isn't.
JDH
CC BY-SA 4.0
2023-11-18T22:24:43.523Z
Most CS theory people don't like the unary encoding, since it tends to wreck complexity theory by causing an exponential blow-up in the input size, and so it is normal to use a larger alphabet so that we can use more sensible input encodings.
JDH
CC BY-SA 4.0
2023-11-18T23:53:02.740Z
These questions are red herrings. As soon as the computational model is fixed (say, Turing machines as described by OP), the resulting realizability topos specifies how natural numbers are to be represented (up to unique computable isomorphism) because the universal property of the natural numbers object determines it up to isomorphism. One can of course ignore category theory and prove theorems about representations of objects by relying on one's "intuition", but what's the point?
Andrej Bauer
CC BY-SA 4.0
2023-11-19T00:34:09.580Z
It seems a perfectly reasonable question to me, and I don't see that this question involves any category theory at all. The point is that we have different ways of "fixing" the computational model, and the question is how they might interact and what the limitations are of those ways of fixing. Of course, we all agree that there are various standard models that work perfectly well. Gro-Tsen is asking about the limits of unusual models.
JDH
CC BY-SA 4.0
2023-11-19T00:38:13.913Z
For example, it is a standard observation in the theory of Turing machines that with 2-symbol Turing machines, you cannot expect to use binary representation of numbers as input (padded with $0$s), since you wouldn't be able to tell when the input ends. The question is what are the allowed limitations, and are there corresponding limitations of the representation of output values? I find this interesting and not a red herring.
JDH
CC BY-SA 4.0
2023-11-19T09:19:53.320Z
@AndrejBauer I've added some remarks at the end of the question to explain what it means for the $\gamma$ to be computable, as well as the reason for which I am (or was) asking the question.
Gro-Tsen
CC BY-SA 4.0
2023-11-19T16:45:13.357Z
@JDH: Just because the question does not mention category theory that category theory is irrelevant. I am not saying that the question is unreasonable, just that once one is familiar with realizability models, these questions often get "automatic" answers.
Andrej Bauer
CC BY-SA 4.0
2023-11-19T18:02:56.083Z
Sure, I agree with that. But in this case, I am skeptical that any category theoretic considerations would avoid the need for hands-on details of the Turing machine operations, which to my way of thinking are the core ideas at play. It would strike me as the wrong level of abstraction. You say, "once one fixes the model", but the main issue, of course, is how we might do that. Once we fix how numbers are represented, then they are represented that way "automatically", but we might have done it differently. Even in the realizability topos, there are alternative interpretations of arithmetic.
JDH
<computability><turing-machines>
Technical limitations of Turing machines due to the input and output encoding of values
Gro-Tsen
# Technical limitations of Turing machines due to the input and output encoding of values

(Asked by: username_0 on 2023-11-18)

**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).

**Tags:** computability, turing-machines

> **Comments:**
> **username_1**: When you say that $\gamma_i$ and $\gamma_o$ are computable, do you fix a default encoding of $\mathbb N$, like unary one ?  Why not imposing that $\gamma_o$ is the converse of $\gamma_i$ ? Then computably proper encoding just means that the encoding is computable both ways. But in your framework, it seems to be just that both $\gamma_i$ and $\gamma_o$ are computable, or am I missing something ? If your valid tapes are the ones with finitely many 1, then yes by your argument with $0^n1$ a surjective encoding can never be proper.  
> **username_2**: @username_1 username_0's argument about $0^n1$ was for input encodings, but the surjective question was about the output encodings.  
> **username_3**: Reiterating @username_1's question: what does it mean for $\gamma_0$ and $\gamma_1$ to be computable? Also, what is the motivation for the question? In terms of realizability, you're asking a strange question about replacing the natural numbers object with other kinds of objects.  
> **username_4**: They are computable in the usual sense. You can define it with unary encoding, but also with recursive functions if you prefer something outside of Turing machines (or, as always, with lambda-calculus, rewriting, and so on).  
> **username_2**: @AndrejBauer I understand the point to be this: to speak of $f:\mathbb{N}\to\mathbb{N}$ being computable, we must represent numbers somehow on the tape, and there are choices about how to do that. These are the "encodings". To say that they are computable means simply that if we use the standard unary coding, then the map from numbers to string is computable in the ordinary sense. The point now is that we can't use bad input encodings, since we won't recognize the end of the input, but the Q is whether there is a limitation on the output encodings, and I argue in my answer that there isn't.  
> **username_2**: Most CS theory people don't like the unary encoding, since it tends to wreck complexity theory by causing an exponential blow-up in the input size, and so it is normal to use a larger alphabet so that we can use more sensible input encodings.  
> **username_3**: These questions are red herrings. As soon as the computational model is fixed (say, Turing machines as described by OP), the resulting realizability topos specifies how natural numbers are to be represented (up to unique computable isomorphism) because the universal property of the natural numbers object determines it up to isomorphism. One can of course ignore category theory and prove theorems about representations of objects by relying on one's "intuition", but what's the point?  
> **username_2**: It seems a perfectly reasonable question to me, and I don't see that this question involves any category theory at all. The point is that we have different ways of "fixing" the computational model, and the question is how they might interact and what the limitations are of those ways of fixing. Of course, we all agree that there are various standard models that work perfectly well. username_0 is asking about the limits of unusual models.  
> **username_2**: For example, it is a standard observation in the theory of Turing machines that with 2-symbol Turing machines, you cannot expect to use binary representation of numbers as input (padded with $0$s), since you wouldn't be able to tell when the input ends. The question is what are the allowed limitations, and are there corresponding limitations of the representation of output values? I find this interesting and not a red herring.  
> **username_0**: @AndrejBauer I've added some remarks at the end of the question to explain what it means for the $\gamma$ to be computable, as well as the reason for which I am (or was) asking the question.  
> **username_3**: @username_2: Just because the question does not mention category theory that category theory is irrelevant. I am not saying that the question is unreasonable, just that once one is familiar with realizability models, these questions often get "automatic" answers.  
> **username_2**: Sure, I agree with that. But in this case, I am skeptical that any category theoretic considerations would avoid the need for hands-on details of the Turing machine operations, which to my way of thinking are the core ideas at play. It would strike me as the wrong level of abstraction. You say, "once one fixes the model", but the main issue, of course, is how we might do that. Once we fix how numbers are represented, then they are represented that way "automatically", but we might have done it differently. Even in the realizability topos, there are alternative interpretations of arithmetic.  

---

## 2 answers

### Answer by username_2 on 2023-11-18. Score: 1 | Accepted answer

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 by username_5 on 2023-11-18. Score: -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.

> **Comments:**
> **username_2**: I agree with your main conclusions—indeed, the main part of your post is essentially the same as my answer—nevertheless I find parts of your post puzzling or nonsensical. For example, you refer to using input in binary, but of course this is not generally possible in the 2-symbol alphabet, for reasons explained in the OP. Also, what do you mean by "given $\gamma_{\mathrm{i}}(x)$ in binary" and "output $\gamma_{\textrm{o}}(x)$ in unary", given that the former are infinite binary strings? Is this somehow part of the "identification" of integers with finitely-supported infinite binary strings?  
> **username_5**: By "given $γ_i(x)$ in binary" I mean "when the input tape is initialized with the binary representation of $γ_i(x)$ (padded with infinitely many zeros)". This was basically a way to avoid sprinkling the whole answer with phrases like "the interpretation of the input tape [that has finitely many 1s] as a number in binary", "the encoding of the input tape into a word in unary" (by converting to an integer through binary representation then encoding that integer in unary), etc. "Input" is meant as "initial state", not necessarily something you can delimit upfront (since that's the whole question)  
> **username_2**: "binary representation of $\gamma_{\mathrm{i}}(x)$" makes no sense, since $\gamma_{\mathrm{i}}(x)$ is already an infinite binary string (and there is no need for padding, since it is already infinite). Unless I have misunderstood, I think you have a different understanding of the notation here than the OP.  
> **username_4**: Since I am identifying binary strings with natural numbers I am also viewing $\gamma_i$ as a map $\mathbb{N} \to \mathbb{N}$. Then the binary representation of $\gamma_i(x)$ is the "original" $\gamma_i(x)$ and its unary representation is a way to encode the original for inputting it to a TM that uses the unary input convention. You might find this a stretch, but after all, the canonical definition of a computable function applies to functions $\mathbb{N} \to \mathbb{N}$ (e.g., recursive functions), so the assumption that $\gamma_i$ is computable already makes this type of identification.  
> **username_4**: Said differently, it's just that instead of speaking of an infinite, finitely supported binary string (X), its representation as a natural through binary encoding (Y) and the conversion of that back into an infinite finitely supported binary string using unary decoding (Z), I find it simpler and more concrete to speak about a natural (Y), its binary representation (X) and its unary representation (Z).  
> **username_5**: @username_2 I have attempted to clarify this in the answer.  

---

