How do we know that the reduction is correct?

Question

I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable.

Here's my reasoning:

Let's say that we want to find out if the following problem is decidable: given any machine $M$ and a string $y$ find out whether the machine $M$ ever writes an $@$ symbol on the tape.

So, I intuitively think that this is an undecidable problem and I try to reduce the halting problem to our problem.

1. Let's have an arbitrary machine $N$ and a string $x$. If $N\#x \in HP$ then $N$ halts on input $x$ else if $N\#x \not\in HP$ then $N$ loops on input $x$ where $HP = \{ M\#x\ |\ M\ \text{halts on}\ x\}$.

   Here's my first question: how do we know if $N\#x$ belongs to $HP$ or not? I thought that we cannot tell and that's the whole idea behind the halting problem.

2. Now we typically construct a machine $M'$ which has $N\#x$ hardcoded inside and which output doesn't depend on its input. Here's how $M'$ works:

   1. Erase the input.
   2. Run $N$ on $x$.
   3. If $N$ halts on $x$ then have $M'$ write $@$ to the tape. Otherwise, if $N$ loops on $x$ then have $M'$ make sure $@$ is not written on the tape.

   From what I understand, the proof is over as the behaviour of $M'$ is similar to $HP$ (I am not sure if this is the correct way to formulate this) and since the halting problem is undecidable then our problem is undecidable as well.

   Here comes my second question: why does it prove anything? It looks like any problem could be treated this way leading us to the conclusion that everything is undecidable as we were able to incorporate the halting problem in our algorithm. How do I know that there is no way to avoid an undecidable problem in my algorithm? I feel like we're showing that we can use the halting problem to solve my problem instead of showing that solving my problem would result in solving the halting problem as well.

I'm sorry if my explanation is a little bit vague – I've already consulted my professor, read related chapters in Automata and Computability by Kozen and tried to read tutorials and presentations on the Internet but I still cannot understand the logic behind the reduction. I'd be grateful if someone could explain my misunderstanding.

Answer 1

Your first question is easy to answer: you are confusing "we know" with "it is the case". It can happen that something is the case but we do not know it. In particular, it is the case that $M\#x$ halts or it does not halt, but we do not know which. It will rain a year from now or not, but we do not know which.

To answer the second question, let us see what goes wrong if we try to reduce the Halting Problem to a decidable problem. Consider the problem:

Given a single-tape Turing machine $M$ and input $x$, decide whether $M\#x$ halts in fewer than $\mathrm{length}(x)$ steps.

Now we need to come up with a reduction, i.e., given any machine $M$ and input $x$, we must produce a machine $M'$ and input $x'$, such that $$\text{$M$ halts on $x$} \iff \text{$M'\#x'$ halts in fewer than $\mathrm{length}(x')$ steps}$$ Here is an idea: let $x'$ be the pair $(x, 0^k)$ where $0^k$ is a a string of $k$ zeroes, where we are going to determine $k$ later (this trick is know as "padding the input"). The machine $M'$ takes this input $(x, 0^k)$, ignores $0^k$ and just does whatever $M\#x$ would do. Now, for this reduction to work, we just need $k$ such that $$\text{$M\#x$ halts} \iff \text{$M'\#(x,0^k)$ takes fewer than $\mathrm{length}(x,0^k)$ steps of execution}$$ Such a $k$ exists because $M\#x$ halts if, and only if, $M'\#(x,0^k)$ halts. So there are two cases:

1. If $M\#x$ halts then so does $M'\#(x,0^k)$ in some number of steps, say $m$, and we can take $k = m + 1$.
2. If $M\#x$ does not halt then we can take any $k$.

There is a small technical issue: the number $m$ should not depend on $k$. We can arrange this in several ways. One possibility is to allow $M'$ to have an extra symbol which it uses as "ignore input from here onwards". In any case, this is not essential for the discussion at hand.

Can you spot the problem? A reduction needs to be computable, that is, we need a computable procedure which generates $M'$ and $x'$ from $M$ and $x$. We have not given a procedure for computing $k$, even though such a $k$ exists. Perhaps if we think harder we can come up with the required procedure for computing $k$. Or perhaps it does not exist, and our attempt is not worth anything. We just do not know.

So, this is one way in which an attempt at a reduction may fail. It is in fact typical: if we are allowed to use non-computable reductions, then we can reduce any problem to any other non-trivial problem. I leave it as an exercise. (Here "non-trivial" means that the problem has an instance where the answer is "yes" and an instance where the answer is "no".)