5
$\begingroup$

So, I'm familiar with the halting problem and its proof. However, I also understand that the proof is for any universal machine $U$; that is, the set $\{(x,y)\in\{0,1\}^{<\omega}\times\{0,1\}^{<\omega}: U(x,y)\downarrow\}$ is not computable. Specifically, I've seen the proof by contradiction that the set's complement is not semicomputable.

However, given a specific, non-universal machine $M$ with alphabet, say, $\{0,1\}$, could you define a machine $M^\prime$ such that, say, $M^\prime(w)=M(w)$ if and only if $M(w)$ halts, and $M^\prime(w)=0$ if $M$ does not halt on input $w$? Or would this, in some way, solve the halting problem, so such a machine $M^\prime$ cannot exist?

Sorry, in advance, if this seems like too basic a question or if it's been asked before. I can't really think of a way to phrase the question simply to look up whether or not it's been answered before. Thank you!

$\endgroup$
  • 2
    $\begingroup$ I would presume that it depends strongly on the choice of $M$ - clearly, there are choices which are trivial (e.g. if they ignore their input, or halt no matter what). I'd assume that there are non-universal machines $M$ for which $M'$ is uncomputable - someone more expert than I will hopefully provide such an instance as an answer $\endgroup$ – Milo Brandt May 10 '15 at 3:14
1
$\begingroup$

First, a remark. As I understand the concept, "universal Turing machine" describes a machine's functionality rather rigidly: the machine has to take inputs in a certain format, and then behave in a very specific way. It's not a robust concept for the sort of question you're asking; you could just take a universal machine and modify it in some trivial way so that it is essentially the same, but isn't technically a "universal machine."

That said, I'll say a bit about what I think is really behind your question. You're asking about when it is possible to make an algorithm to solve the halting problem for particular machines. You can ask this more generally: given a particular set of natural numbers, is there an algorithm to decide which numbers are in the set, and which numbers are not in? In your case, the set is the set of inputs for which the machine halts. Only some sets arise like that; they are called, by definition, the "computably enumerable" sets. On the other hand, sets for which it is possible to make an algorithm to decide which elements are in and which are out are, by definition, "computable sets." The halting problem argument shows that there is a computably enumerable set that is not computable.

What I believe you observed is that a universal Turing machine is fairly powerful in that it can do everything any other Turing machine can. It is a natural question to ask if there are "less powerful" sets that are still not computable. That may seem a bit nebulous, but we're in luck: there is a good way to compare the power of two sets, called Turing degree. The basic idea is that a set A is "stronger" than another set B (has a higher degree) if you can build a machine to compute B (i.e. decide which elements are in and which are out), if that machine can consult A as an "oracle." This turns out to be a rich and robust concept.

Anyway, the answer to my version of your question is yes. There is a rich variety of sets that are computably enumerable (i.e. are the halting set of some machine), not computable, and are strictly weaker than the halting set of any universal machine (in terms of Turing degree). I don't know of any simple constructions, but I hope I've given you some ideas to try and learn about.

$\endgroup$
  • $\begingroup$ As a remark, some sources say "recursive" instead of computable, and "recursively enumerable" instead of computably enumerable. I think those terms are a bit archaic, but it's something to be aware of when looking stuff up. $\endgroup$ – Mike Haskel May 10 '15 at 4:42
1
$\begingroup$

As stated, $M'$ is a well defined function. Sometimes $M'$ is computable, as in simple cases such as when $M$ is a machine that always halts or never halts. Is $M'$ always computable? It turns out not.

Consider the case of a semidecidable set $\Gamma$. Let $M$ be a Turring machine that outputs $1$ for all $\alpha\in\Gamma$, and outputs $0$ or loops for $\alpha\notin\Gamma$. First, note that $M$ is not a universal Turring machine. Proof: If $M$ is universal, then $M(\alpha)$ simulates $\alpha(0)$. Then we have $\alpha\in\Gamma$ iff $\alpha(0)=1$. Therefore all $\alpha\in\Gamma$ output $1$ when run on a blank tape. $\Gamma$ was an arbitrary semidecidable set, so the result holds as well for all semidecidable sets. However, the set of all Turing machines is decidable, and thus, semidecidable. But there are some Turring machines that do not output $1$ when run on a blank tape. Therefore, $M$ is not universal.

Since $M$ is not universal, we can define $M'$. Assume $M'$ is computable (to show a contradiction). Now $M'$ outputs $1$ for all $\alpha\in\Gamma$ and outputs $0$ otherwise. Therefore, $\Gamma$ is decidable. That means that all semidecidable sets are decidable. A contradiction, and thus, $M'$ is uncomputable.

Finally, your question is whether we can define a machine (as opposed to a function) $M'$ for all non-universal $M$. As shown above, we cannot define such a machine when $M$ is a machine that enumerates a semidecidable set.

In general, for what $M$ can we define (the machine) $M'$, and when can't we? A machine $M'$ exists iff the set $G$ of all values for which $M$ halts is decidable. Proof: Suppose the machine $M'$ exists. $M(\alpha)$ halts iff $M'(\alpha)=1$, and $M(\alpha)$ does not halt iff $M'(\alpha)=0$, so $G$ is decidable. Suppose $G$ is decidable. Then there is a machine that accepts $\alpha$ if $M(\alpha)$ halts, and rejects $\alpha$ if $M(\alpha)$ does not halt. That is machine $M'$.

$\endgroup$
0
$\begingroup$

The standard proof that the halting problem is unsolvable gives a machine $M$ such that there is no total machine $M'$ can determine correctly the set of $n$ for which $M(n)$ halts.

This machine $M$ is not universal in the sense of computability theory. Rather $M(e)$ attempts to compute $\phi_e(e)$; if $U(e,e)$ halts and returns a number greater than $0$ then $M(e)$ does not halt, while if $U(e,e)$ halts and returns $0$ then $M(e)$ halts and returns $1$. If $U(e,e)$ does not halt then neither does $M(e)$. You can check that this gives a sound definition of a machine $M$, and that no machine $M'$ can solve the halting problem for $M$ in the sense given in the question.

$\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.