3
$\begingroup$

Say we have a particular decision problem and that we have an alphabet and an encoding scheme, which gives us a language L that we say is not recursive (i.e. we do not have a Turing Machine that can decide (YES or NO) the problem).

Is it possible to use a different encoding scheme to make the problem solvable?

I have thought about suggesting that we can reduce all such problems to the halting problem, which would imply that no new encoding will allow us to make one solvable (since this would contradict the unsolvability of the halting problem).

$\endgroup$
6
$\begingroup$

Ultimately, no.

First, remember that a language is, literally, a set of strings over some alphabet. There is no coding at this level: a string (a sequence of characters from the alphabet) is either in the language or it's not. For example, the language of even-length strings over $\{0,1\}$ is what it is; if you change it at all, it's a different language.

However, you probably don't mean for your question to be interpreted so literally, and you're presumably asking about languages such as "the set of strings that encode Turing machines with property $X$." Strictly speaking, the description of such a language should always say, "Fix an encoding scheme $f$ of Turing machines as strings. Now consider the language of strings $f(M)$ such that $M$ is a Turing machine with property $X$." After all, if you don't say what the encoding is, you can't know if a particular Turing machine is in the language or not. So, presumably, your question is "Well, what if I use some other encoding scheme, instead?"

As long as there's a computable translation between the two encoding schemes, changing the encoding can't alter the computability of the language. To see this, fix any set $S$ of Turing machines and consider codings $f$ and $g$ of these machines as strings. Suppose there's a computable translation between $f$ and $g$, i.e., a computable function $t$ such that, for all $M$, $g(M) = t(f(M))$. If the language $L_g = \{g(M)\mid M\in S\}$ is decidable, then we can decide $L_f = \{f(M)\mid M\in S\}$, too. To decide whether $w\in L_f$, just ask if $t(w)\in L_g$. The reason people tend to be quite informal and just talk about "the language of Turing machines with some property" is precisely this: it doesn't matter what encoding you use, as long as you stick to encodings you can computably translate to the "standard" encoding, whatever reasonable encoding you want to view as standard.

In a strong sense, it's impossible to use any other encoding. For example, consider an encoding $f$ that isn't computably translatable to some standard encoding. Now, suppose I describe a Turing machine to you by listing the symbols in the alphabet, the states, the transition function and so on. You can't even compute $f(M)$, so you can't do anything useful with that encoding.

There are even encodings that make the halting problem decidable but they're a trick: they're not computable, so you can't actually use them. For example, fix a computable encoding $g$. Now, define $f(M)$ (uncomputably) as follows. If $M$ halts when started with a blank tape, let $f(M)$ be $2n$ written in binary, where $n$ is the number of Turing machines $M'$ such that $M'$ halts when started with a blank tape and $g(M')$ lexicographically precedes $g(M)$. Otherwise, let $f(M)$ be $2n+1$, where $n$ is the number of Turing machines $M'$ that do not halt when started with a blank tape and whose encoding $g(M')$ lexicographically precedes $g(M')$. Now, the language $\{f(M)\mid M \text{ halts when started with a blank tape}\}$ is decidable: it's just the set of even numbers in binary. But, as I said, this is a trick: it doesn't really let you decide the halting problem because, again, you can't compute $f(M)$ given a description of $M$. (In particular, you can't even tell if $f(M)$ is even or odd.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.