REGULAR-TM is undecidable?
From: J.M.Roth (jm_at_roth.lu)
Date: 02/22/05
- Next message: Lester Zick: "Re: Existence of mathematical entities (Re: Successor Axiom: on what grounds TF?)"
- Previous message: wade_at_stoner.com: "Re: matrix handeling algorithms"
- Next in thread: Rick Decker: "Re: REGULAR-TM is undecidable?"
- Reply: Rick Decker: "Re: REGULAR-TM is undecidable?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 22 Feb 2005 08:07:57 -0800
Hi, I don't understand the following proof to show that the REGULAR-TM
problem (= M is a Turing Machine and L(M) is a regular language) is
not decidable.
It is done by reducing from the acceptance problem A-TM.
We suppose REGULAR-TM exists and give a reduction so that A-TM becomes
decidable, which we know it is not.
R = TM that decides REGULAR-TM
S = TM that decides A-TM
The following would decide A-TM:
S = On input <M,w>:
1. Construct TM X: On input x:
a) If x has the form 0^n1^n => accept
b) If x does not have this form, run M on w and => accept if M accepts
w.
2. Run R on X
3. If R accepts => accept, if R rejects => reject.
Now what is unclear to me is why this non-regular language is in 1a).
R can decide whether X accepts a regular language. But X also accepts
in the case that x=0^n1^n. How can R ever accept X, since X also
accepts this non-regular language?
Also there are many more non-regular languages than 0^n1^n, so I would
imagine something like
a) If x is not a REGEXP => reject
b) If x is a REGEXP => run M on w and accept if it accepts
Now this would be a fine mapping reduction, wouldn't it? (however I'm
not sure how to decide REGEXP).
Please explain steps 1a+1b in the original construction. Thanks!
- Next message: Lester Zick: "Re: Existence of mathematical entities (Re: Successor Axiom: on what grounds TF?)"
- Previous message: wade_at_stoner.com: "Re: matrix handeling algorithms"
- Next in thread: Rick Decker: "Re: REGULAR-TM is undecidable?"
- Reply: Rick Decker: "Re: REGULAR-TM is undecidable?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]