Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm taking an introduction to computation theory class and we went over the chapter on undecidable problems and proving undecidability through reductions. I can't seem to grasp some of the simplest problems when it comes to reduction however.

For example there is the problem $\mbox{REGULAR}_{TM} = \{ \langle M \rangle \mid M\mbox{ is a Turing Machine and }L(M)\mbox{ is a regular language}\}$

Most of the time the answers involve creating your own auxiliary Turing Machine. For this example, my book decides to reduce from $A_{TM}$ my book uses $M_{aux}$. I show what $M_{aux}$ looks like within the decider $S$ for $A_{TM}$ they formulated ($R$ is the decider for $\mbox{REGULAR}_{TM}$):

$S = $ "On input $\langle M , w \rangle$, where $M$ is a TM and $w$ is a string:

  1. Construct the following TM $M_{aux}$:

    $M_{aux}$: "On input $x$:

    1. If $x$ has the form $0^n1^n$, then accept.
    2. If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$."
  2. Run $R$ to on $\langle M_{aux} \rangle$.

  3. If $R$ accepts, accept. If $R$ rejects, reject."

I don't really understand where $x$ comes from and how $M_{aux}$ uses $x$. According to the book, $M_{aux}$ works by automatically accepting all strings in $\{0^n1^n\mid n \ge 0\}$. If $M$ accepts $w$, $M_{aux}$ accepts all other strings. But what if $M$ doesn't accept $w$ in the second step? In that case it looks like $M_{aux}$ would reject. What happens then?

My main problem is just that I don't understand how $M_{aux}$ runs and how the decider for $R$ uses it. I've looked over many other examples and I understand how to actually create proofs like this, but what I don't understand is the subroutine machine that they create, like $S$ does.

share|cite|improve this question
up vote 1 down vote accepted

The point is that the behavior of $M_{\rm aux}$ depends only on what $M$ does to $w$:

  • If $M$ accepts $w$, then the language $M_{\rm aux}$ accepts is regular (namely everything).
  • If $M$ rejects $w$ (such as if it doesn't terminate), then the language $M_{\rm aux}$ accepts is not regular (namely $\{0^n1^n\}$ which is easily shown not to be regular, for example by the Myhill-Nerode theorem).

The input $x$ doesn't come from anywhere, because $M_{\rm aux}$ is never actually run -- we're just feeding it to $R$ to be analyzed, in order that $R$ can tell us which of the two above cases we're in.

It's not particularly important that the two languages $M_{\rm aux}$ may recognize are precisely $0^n1^n$ and $\{0,1\}^*$ -- the important thing is that they ought to be classified differently by $R$, and therefore we can use $R$ (if it works as assumed) to learn things about $M$'s behavior of $w$ that we already know we can't know in general.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.