I'm studying for a final exam coming up next week, and I'm still unclear on some of these halting reduction questions. Reading through older final exams (no solutions), they have a fairly common question in them. Can I get some feedback on the logic used in my solutions? I have a very light grasp on how this works and I'm not 100% comfortable with these kinds of problems yet.
Suppose there's some magical algorithm that determines if a Turing Machine M1 halts when started on blank tape.
a) Given a TM M2, prove that we can determine if M2 halts on the input "42" using the program developed that determines if M1 halts or not on blank tape.
For this, the best answer I can provide is drawing a generalized machine schema for a new TM Mx, which takes the blank input, overwrites the input with 42, and runs M2. Feeding Mx into this magical algorithm, we can then decide if Mx halts on a blank input, which tells us whether or not any M2 halts on an input of "42".
I feel like I'm missing something here, as this seems too easy for 5% of the total grade of the final exam.
b) Suppose a faster magical algorithm exists which can answer whether or not M2 halts on input "42". Explain how this can be used to determine if some M3 halts on a blank input.
For this I theorized a machine My that takes an input of "42", erases the input, and runs our M3. If this faster algorithm can decide if My halts with "42" as an input, it can decide if M3 halts on a blank input.
Same uncertainty goes for this part.
I feel like this is a really good question to help my understanding of this topic, but I'm not sure if I have a grasp on how to answer it. We have an absolute lack of solutions for this class and the prof provides incomplete and scribbly feedback. Your help is greatly appreciated. Cheers!
The questions are written a little confusingly, since the use of $M1$, $M2$, and $M3$ makes it seem as if these are all specific machines ... but I am pretty sure they mean that these are all supposed to be algorithms that can determine for any machine whether it halts on a blank tape or not, or with input "42" or not. Indeed, otherwise you would not be able to solve these problems.
So, rephrasing the first question: Prove that if there is a machine $H_B$ that can determine for any machine description $M$ whether or not $M$ halts on a blank tape, then there is a machine $H_{42}$ that can determine for any machine description $M$ whether $M$ halts with input "42" or not.
So your basic intuition is correct in that we construct $H_{42}$ out of $H_B$, but, as you expected, it is a good bit more complicated to make this work:
First, given any machine $M$, let $M_{42}$ be the machine that, when given an empty tape, first puts "42" on the input, and then runs machine $M$. Now let $Create_{M42}$ be a machine that, when given any machine $M$, creates machine $M_{42}$. Finally, îf we are given the existence of $H_B$, then we can construct machine $H_{42}$ out of that by appending machine $Create_{M42}$ and $H_B$:
Given any machine $M$, when presented to $H_{42}$, $H_{42}$ will first run routine $Create_{M42}$, and thus write the machine description of $M_{42}$ on the tape. This will then get fed into $H_B$ which, as we remember, checks whether the machine on the input will halt or not given a blank tape. Well, as part of $H_{42}$, $H_B$ will say "yes, halts!" if and only if $M_{42}$ halts on an empty tape which is if and only if machine $M$ halts when given input "42". Hence, as a whole, $H_{42}$ will say "Yes, halts!" If and only if machine $M$ halts when given input "42". ... which is exactly the desired behaviour.
Now that you see how to actually construct $H_{42}$ out of $H_B$, I am sure you can figure out how to do it the other way as well for question b)