Decidability of Turing machines and misconceptions on the halting problem

Question

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.

Answer 1

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.

Answer 2

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.