Rules on Reductions from Halting Problem

From: Blake Manner (blakman211_at_hotmail.com)
Date: 02/09/04 

Date: 8 Feb 2004 20:09:42 -0800

I'm currently trying to teach myself some things about complexity
theory, and although today I purchased a book, "Computational
Complexity" by Christos H. Papadimitriou, I have so far been just
going through notes from different sites on the web. One problem that
I have right now is that I am seeing a lot of theory and very little
examples of things. This was fine for the early stuff like turing
machines because I learned that stuff in undergrad. However, right now
I am trying to get an understanding of m-reductions from the halting
problem and I am not quite sure I understand these reductions.

THe way I am understanding it is that If I want to prove a decision
problem undecidable, I assume that it is decidable, and use this new
machine to solve the halting problem.

The example that I have seen repeatedly is the proof that A = (e | M_e
halts on all input}. Suppose we can solve this problem. We will then
solve the halting problem in the following way.
1. Input x, y
2. Create machine M(z)
     If M_x(y) halts
          then halt
     else
          do not halt
3. Get the index of machine M, M = M_e
4. Now run the program that decides A on e, M_A(e).

If (x,y) belongs to halt, then M_x(y) halts, so M_e halts on all
input, so e belngs to M
If (e) belongs to M, then M_e halts on all input, then M_x(y) halts,
then (x, y) belongs to HALT.

I think I get this proof and get all the steps and why each step was
taken, but maybe I don't. What I am confused about, though, is how I
should construct my own proof. I mean, what are the rules for the
machine. Since we are creating a turing machine, I figure the same
rules apply. Then I look at this machien and I am forced to wonder
about the step "If M_x(y) halts". How would we code that into a turing
machine? That seems like an ambiguous command, but since it is allowed
I wonder if we can do other things. Can we ask something like if the
set A is decidable then do blah blah blah? Or can we create more than
this one machine? can we define what this machine does on more than
one input?

My most important question from this post is just in general, what are
we allowed and not allowed to do in m-reductions?

Also, if anyone knows any good books for me to study this information
from, it would be greatly acceptable.

Thank you so much
Blake Manner