Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Tweeted twitter.com/#!/StackCompSci/status/410948234358816768
Source Link
Zach
  • 33
  • 1
  • 3

Reducing from a Turing machine that recognizes is regular to the halting problem

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present.

This is the reduction they give:

PROOF We let R be a TM that decides REGULARTM and construct TM S to decide ATM . Then S works in the following manner.

S = “On input $M$, $w$ , where M is a TM and w is a string:

  1. Construct the following TM $M_{2}$ .

    $M_{2}$ = “On input x:

    1. If x has the form $0^{n} 1^{n}$ , accept .

    2. If x does not have this form, run M on input w and accept if M accepts w.”

  2. Run R on input $M_{2}$ .

  3. If R accepts, accept ; if R rejects, reject .”

So, we start with a machine that decides whether a language of a TM is regular. And we want to use that to decide if a TM halts on a given input.

My question: What if $w$ does have the form $0^{n} 1^{n}$? Well, $M_{2}$ accepts that string just cause of the form. But we never actually run $M$ on $w$. So how can we say that it will accept or reject it? We have no idea what it does because we never ran it on $w$.