In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability only arises when we are talking about a class of a problem.

As a rebuttal to the original argument someone replied that if we have a Turing machine and we give it an input w it'll be undecidable to say will it halt or not and was proven by Turing himself.

Is this a correct argument because skimming through wikipedia it looks that's not what Turing actually proved

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist

What he proved was that no general solution exists for all possible program-input pairs and not that we can't have a specific algorithm to solve this on a single machine (e.g if we take a halting Turing machine a simple solution would be to say yes for all inputs).

In support of my original statement look at the PCP, no general solution exists but if we are given two string we can sure brute-force them by looking at all possible subsequences and tell whether a correspondence exists or not.

So what I am asking here does my original statement hold weight and what exactly did Turing proved.

Edit: I've realized this question doesn't make much sense and is just not useful to anyone. But because it has answers it can't be deleted.

  • 1
    $\begingroup$ The question of undecidability only arises when we are talking about a class of a problem. Yes - and when the machine is fixed, the class is formed by the infinity of potential input strings. $\endgroup$ – reinierpost Jan 6 at 11:11

The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable.

If a Turing machine $T$ is fixed, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$).

As an example in which this problem is decidable consider the trivial Turing machine $T$ that immediately halts. As an example in which this problem is undecidable consider an universal Turing machine $T$ in which $w$ encodes a pair $\langle M, w'\rangle$ where $M$ is some other Turing machine, and $w'$ is $M$'s input. The machine $T$ simply simulates $M'$ on $w'$. Clearly if we could solve the halting problem for this fixed $T$ and any $w$, we could also solve it in the general case.

If a word $w$ is fixed but the machine $T$ is part of the input of the problem, then the problem is undecidable regardless of $w$. Suppose towards a contradiction that this problem was decidable, then given a Turing machine $M$ and a word $w'$ as input, you could decide whether $M(w')$ halts. To do so you construct a new Turing machine $M'$ that clears its tape, writes $w'$, and then simulates $M$ (an encoding of such a machine $M'$ is computable given $M$ and $w$). Clearly $M'(x)$ halts iff $M(w')$ halts, regardless of $x$. In particular, for $x=w$, $M'(w)$ halts iff $M(w')$ halts. It then suffices to decide whether $M'(w)$ halts, which we can do by our hypothesis.

If both a Turing machine $T$ and a word $w$ are fixed, then the problem does not make much sense since you do not have a class of instances anymore... Notice that, in this case, either $T(w)$ halts or it does not, meaning that one of the following two Turing machines must answer correctly: 1) Always halt and accept. 2) Always halt and reject.

  • $\begingroup$ Can you explain the last part when both the machine and word are fixed, why doesn't it make sense? $\endgroup$ – Abhishek Kaushik Jan 6 at 10:02
  • $\begingroup$ A decision problem can be formalized as the problem of deciding whether an input $x \in \Sigma^*$ belongs to some set (language) $L\subseteq\Sigma^*$. What role does $x$ play in the last case? What is $L$? If you ignore $x$ and answer yes or no depending on whether $T(w)$ halts, then either you always accept and $L=\Sigma^*$, or you always reject and $L=\emptyset$ ($T$ and $w$ are fixed!). These 2 languages are not really interesting (and admit trivial algorithms). In general, problems in which $L$ or $\Sigma^* \setminus L$ are finite are not really interesting. This is an extreme example. $\endgroup$ – Steven Jan 6 at 10:13
  • $\begingroup$ In other words, the concept of decidability applies to problems (i.e., languages $L$), not specific instances (i.e., words in $L$). There is always an algorithm that answers correctly (and in constant time) for any fixed instance of a problem. You'll have to define what problem you want to look at if both $T$ and $w$ are fixed. The "natural" way to do that results in uninteresting problems with trivial algorithms. $\endgroup$ – Steven Jan 6 at 10:20
  • $\begingroup$ So it would not be wrong to say a single instance is decidable (trivially) but it has no importance $\endgroup$ – Abhishek Kaushik Jan 6 at 10:23
  • $\begingroup$ It would be "wrong" in the sense that it is not defined what it means for an instance to be decidable. The notion of decidability only applies to problems. $\endgroup$ – Steven Jan 6 at 10:25

Unfortunately I cannot comment on Steven's answer, but I think the crux of the matter here is a confusion between the terms "problem", "class of problem" and "problem instance" (that is, when the machine and word are fixed, you have an instance of the halting problem, not a problem).

As a side note, Turing did not prove in his 1936 paper the halting problem in this form. The machines in his paper mostly compute binary digits of numbers and he proved you cannot tell whether one of these ever stops or runs forever. So his problem only has a machine as input, not a (machine, word) pair.

  • $\begingroup$ It is exactly what you just said, a single instance of a problem must always be decidable is the actual question $\endgroup$ – Abhishek Kaushik Jan 6 at 10:17

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.