Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

Question

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.

---

I had this problem on my exam. From my understanding, the halting problem involves a program with some input, and that program will either output yes or no as output when comparing the input to the desired value. Then there's another program that must determine if the original program will ever halt based on the input given to it.

Thing is, I'm not sure if I understand the entire concept here. It's undecidable because we are unable to write a program that can determine if a program will always halt or stay in an infinite loop? Since it will always output as a "yes, it halted" even though the original program either halted or remained in an infinite loop.

So, I'm pretty new to all this, so bare with me. If the original question was asking me to "reduce" from the halting TM, do I apply the same principles? Or am I working out the problem differently? What is a reduction exactly, and what was I supposed to do here?

Answer 1

Since you seem to want only a hint rather than a full solution, here is my attempt:

1. Undecidability of the Halting problem is one of the most famous impossibility results. It is not the most powerful one in the series (consider Rice's theorem) but it is a relatively simple in layman's terms and IMHO pretty impressive (in a bad way). The undecidability of the halting problem means that no matter which algorithm you try for the halting problem, it will fail on some inputs. It does not say that you can't predict if the program will halt for each (program, input data) pair, for example there are some very predictable programs. But it says that for every deciding program there will be some bad pair (possibly different for different programs, but even if you "combine" many such deciding programs, there still will be some bad cases).

2. Reduction is a general concept in math with several overlapping meanings. Here is one related famous joke about mathematicians:

An engineer and a mathematician were shown into a kitchen, given an empty pan, and told to boil a pint of water. They both filled the pan with water, put it on the stove, and boiled it.

The next day they were shown into the kitchen again, but this time given a pan full of water, and told to boil a pint of water. The engineer took the pan, put it on the stove, and boiled it. The mathematician took the pan and emptied it, thereby reducing it to a previously solved problem.

On a more serious note, reduction to the Halting problem is an argument that shows that a perfect anti-virus is impossible: the virus potentially can do its harm at any time during its whole runtime. So if the antivirus can catch all the viruses, it has to be able to solve the halting problem because I can put my virus "at the end" of any other program which the antivirus has to analyze first.

If you want a similar but I bit more formal argument take a look at wiki reduction of the Rice's theorem to the Halting problem

Generally in the CS-world reduction is mostly used in two ways:

1. To prove that some problem is undecidable by reducing it to some other well-known undecidable problem (and the Halting problem is often used here). In other words, if we could solve the problem X, we also must be able to solve the problem A which is known to be undecidable so X must be undecidable as well.

2. To prove some boundaries on complexity of some problem. For example, problem X is NP-complete because here is how to transform (reduce) an arbitrary input for a known NP-complete problem A into an input of the problem X and then how to transform the answer back.