# Problems with universal encoding format for Turing Machines?

When one talks about decidable and semi-decidable languages, it is inevitable that the concept of "encoding a Turing machine as a (binary) string" will come up. And at first glance this seems rather simple: say you have some Turing machine $$T$$, defined by a six-tuple $$(K, \Sigma, \Gamma, \delta, s, H)$$ Where $$K$$ is a finite set of states, $$\Sigma$$ is the alphabet of the input, $$\Gamma$$ is the alphabet of the tape characters, $$s \in K$$ is the start state, $$H \subset K$$ is the set of halting states, and $$\delta$$ is the transition function. If our states our $$q_1, q_2, ...q_n$$, you can convert each state to binary, with the delimiter $$q$$, that is $$q00, q01, ... qn_2$$. You can switch the $$q$$'s with $$h$$'s if it's a halting state. If our input alphabet, is say, $$\{a, b, c\}$$, then we can delimit $$a$$ as $$a00$$, $$b$$ as $$a01$$, and $$c$$ as $$a11$$, and so on. We can do this similarly for $$\Gamma$$, and so on, and once we've properly encoded everything, we can define $$$$ as basically all "instructions" from our $$\delta$$ listed out in their binary encodings.

This is all fine when talking about a single Turing Machine. Essentially, we just come up with a "translation key" between our states and alphabets to binary. This is also easy, when we consider the set of Turing machines $$M$$ which share their tape and input alphabets, as we can use one shared translation key, with the caveat that our translation key will have to have infinitely many entries to ensure that we can describe any $$n$$-state Turing machine (so we will have $$q0, q1, q10, q11, ...$$.

But problems, for me, start to arise when we start asking questions, using $$$$, for any $$M$$. For example, my textbook asks, if the Halting-type language

$$L = \{ : M \text{ is a Turing machine such that } a \in L(M) \}$$

Is semidecidability. I know how such a proof works, that isn't the problem. My problem is: How are we supposed to understand the statement $$a \in L(M)$$ for arbitrary $$M$$? Since $$< M>$$ is in string form, I presume that this is a binary encoding of $$M$$. But $$a$$ is just... $$a$$. It's a concrete instance of a character from an arbitrary alphabet. How do we confirm / deny if $$a \in L(M)$$ for the machine $$M$$ encoded by $$< M >$$, if we don't know what $$a$$ "looks like" to our machine $$M$$?

To emphasize this point, consider what would be considered an easy "solution" to this question. You would say "L is Semidecidable becuase the Turing Machine

T(<M>):
Run a on M
Accept


Semidecides $$L$$". That makes enough sense, but I feel like we've just sweeped the problem under the rug by saying, brazenly, in the first line: "Run a on M." What does this mean, exactly? How does our Turing Machine parse what $$a$$ means?

My first reaction would be to create some universal translation key: i.e, say that $$a = a01$$, $$b = a02$$, and then "standardize" our Turing machines accordingly, i.e if we have some Turing Machine $$T$$ that accepts, say, the language $$\{ab\}^*$$, that in our binary encoding $$$$, we use $$a01$$ and $$a02$$ to stand-in for $$a$$ and $$b$$.

But one of the many problems this seems to cause is that... there are, in the biggest sense of the word, infinitely (uncountably) many "symbols" we would have to account for in our translation key. There's a Turing Machine out there whose input alphabet consists of, say, all the Apple Emojis. There's nothing stopping my textbook author, it seems, from asking some absurd question like "is the language

$$\{ : \text{ M is a Turing Machine such that } đźĄ˛ \in L(M) \}$$

Decidable?" But I don't see why this is any more absurd than asking about $$a$$. From the perspective of a general, binary-encoded Turing machine $$$$, they both mean the same amount of nothing, since we don't have a translation key, and as established, we can't have a translation key, because we can always come up with a new Turing machine operating on a new alphabet--say, I don't know; a set made up of 10 pictures of the Empire State Building from different angles.

I'm guessing my problem here is I'm missing some sort of limiting assumption being made, or that I'm asking a wrong question altogether. But the more I think about it the less it makes sense.

Given an alphabet $$A$$ and an element $$a \in A^*$$, we can talk about the language $$L = \{\langle M\rangle : M \text{ is a Turing machine with alphabet }A \text{ such that } a \in L(M)\}.$$ (Well, we also have to define $$\langle M\rangle$$ appropriately: whatever method we use to encode Turing machines with alphabet $$A$$ should know what $$A$$ is.)
If we fix an alphabet once and for all and decide we're not going to consider Turing machines with other alphabets, then we might simply write "$$M$$ is a Turing machine" instead of "$$M$$ is a Turing machine with alphabet $$A$$".
• If I understand correctly: We define a Universal Alphabet $A$ (and possibly a Universal Tape Alphabet $\Gamma$) and consider only the Turing Machines that are defined on these alphabets. This is fine, because any Turing Machine which runs on different alphabets may be converted (through an "isomorphism," if you like) into something saying the same thing, but in our Universal Language. Commented Oct 26, 2023 at 0:16
• BUT: My practical issue with this is, we must have it such that our Universal Alphabet $A$ is finite, by the definition of an alphabet. So $|A| = n$. But surely there are Turing machines which operate on Alphabets $B$ with $|B| > n$? And I don't see how we could create an "isomorphism" between these Turing machines and some Turing Machine with a smaller alphabet. Commented Oct 26, 2023 at 0:18
• You can encode $B$ by sequences of $k$-tuples of elements of $A$, and build a more complicated Turing machine with alphabet $A$ that simulates a Turing machine with alphabet $B$. Commented Oct 26, 2023 at 0:19
• Ah; so in this case our $A$ could be something as simple as $\{0, 1 \}$, which I suppose, is the convention. Or $\{a, b \}$. I guess it is just that my textbook seems to have disregard for any idea of a "Universal Alphabet." The question underneath the one I references uses $x$'s and $y$'s, the one below uses 0's and 1's. I guess this is just underlining the point that it doesn't matter at all what our alphabet is. Commented Oct 26, 2023 at 0:23