We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable?
I couldn't find an example or theory.
Thanks
$\begingroup$
$\endgroup$
1
-
$\begingroup$ What are "A(TM)" and "A(DFA)"? $\endgroup$– David RicherbyCommented May 15, 2014 at 15:36
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
$A(TM)$ is undecidable because a Turing machine can fail to halt on its input. $A(DFA)$ is decidable since a DFA must always halt on any input. We can always decide whether a DFA accepts some string just by running the DFA on the string and seeing whether the DFA ends up in an accepting state. Not so with a Turing machine.
It is extraordinarily unlikely that there is a valid reduction of $A(TM)$ to $A(DFA)$; that would be a bit like effectively demonstrating that triangles have actually always had 3.5 sides, not 3. If you've got such a proof you should buy as many futures in mops as you can, since there will be a lot of brain matter to clean up after all the computer scientists' and mathematicians' heads explode.
I suspect the real question may really be more about whether proofs of the form "A reduces to B. B is decidable. Therefore, A is decidable." are valid. The answer is that, as you probably expect, of course they're valid: if you ever find yourself needing to prove a problem is decidable, this is the gold standard way to do it. If you've never seen a proof like this, per se, the reasons could be either that the default assumption is that problems are decidable until proven otherwise, or because this proof method is tantamount to just designing an algorithm to solve the problem (in which case, it might not appear to be a proof of anything so much as a description of an algorithm).
To give an example: consider Bubble Sort. This can be viewed as a proof that the Sorting problem is decidable, since it reduces $Sort$ to $\{GreaterThanOrEqualTo, Swap, Loop\}$, which we know are decidable. All right, there's some hand-waving there, but you get the idea.
-
$\begingroup$ Wow, that was some perfect explanation. Cheers. $\endgroup$ Commented May 16, 2014 at 17:01
-
$\begingroup$ The confusion was in the fact that in the examples I read, they reduced A(TM) to EQ(TM) and then assumed a decider for EQ(TM) exists, and then constructed a decider for A(TM) using the decider for EQ(TM), but at the end our claim was wrong because such a decider for A(TM) exists, missing the fact that actually EQ(TM) was undecidable too. They never pay attention to the problem to which A(TM) is being reduced. $\endgroup$ Commented May 16, 2014 at 17:03
-
$\begingroup$ Given the theorem that if A is reducible to B, and if B is decidable so is A. But for instance if A is undecidable, then suddenly we take the contrapositive of the theorem claiming if A is reducible to B, then if A is undecidable, so is B. Hmm, that is really strange, i've reached a point where a mutual conversation with someone would help me understand. $\endgroup$ Commented May 16, 2014 at 17:18
-
$\begingroup$ @AbdussamiTayyab Please visit our chat - we have some good discussions there occasionally :) chat.stackexchange.com/rooms/2710/computer-science $\endgroup$ Commented May 16, 2014 at 17:26
$\begingroup$
$\endgroup$
7
If you could reduce A$_\text{TM}$ to A$_\text{DFA}$, you would have shown that A$_\text{TM}$ is decidable, which it certainly is not, so that approach won't work. To show that A$_\text{DFA}$ is decidable, you need a decider, namely an algorithm that would take a DFA $M$ and a word $w$ and always correctly answer the question "does $M$ accept $w$ or not?" Put yourself in the place of the decider: if someone gave you a DFA and a word, how would you answer the question? That should give you the algorithm.
answered May 14, 2014 at 17:35
-
$\begingroup$ What I don't understand is why do all the reducibility problems I study never show that a problem is decidable? Kindly tell me this please. $\endgroup$ Commented May 15, 2014 at 6:22
-
$\begingroup$ If A < B, then if B is decidable then A is decidable. Similarly, if A is undecidable, then so is B undecidable. What if A is undecidable and B is actually decidable? $\endgroup$ Commented May 15, 2014 at 6:27
-
$\begingroup$ @AbdussamiTayyab "What if A is undecidable and B is actually decidable?" Then either A does not reduce to B or mathematics is wrong. This isn't outside the realm of possibility, but it's an extraordinary claim requiring extraordinary evidence. It would be akin to showing that astrology is real. That's actually significantly more likely than everybody being wrong about mathematics, since we at least have the advantage of having defined mathematics ourselves. $\endgroup$ Commented May 15, 2014 at 15:10
-
$\begingroup$ (Your observation about not seeing many proofs of the type "A reduces to B; B is decidable; therefore, A is decidable" is likely correct: I think the default assumption is that interesting problems are decidable unless shown to be otherwise. This isn't a particularly smart bet, since most problems are undecidable, but through a combination of arrogance, hope, complacency and luck, most problems humans care about are decidable... may be a self-fulfilling prophecy (e.g., humans avoid problems that are undecidable.) $\endgroup$ Commented May 15, 2014 at 15:12
-
$\begingroup$ @Patrick87. Another factor here is that once one has established the result that any (non-trivial) decidable problem is reducible to any other decidable problem, there's a disincentive on the part of instructors and textbook authors to spend a lot of effort in doing such reductions, especially since it's frequently more instructive just to build a decider, as I did here. $\endgroup$ Commented May 15, 2014 at 16:05