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.


  • $\begingroup$ What are "A(TM)" and "A(DFA)"? $\endgroup$ – David Richerby May 15 '14 at 15:36

$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$ – Abdussami Tayyab May 16 '14 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$ – Abdussami Tayyab May 16 '14 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$ – Abdussami Tayyab May 16 '14 at 17:18
  • $\begingroup$ @AbdussamiTayyab Please visit our chat - we have some good discussions there occasionally :) chat.stackexchange.com/rooms/2710/computer-science $\endgroup$ – Patrick87 May 16 '14 at 17:26

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.

  • $\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$ – Abdussami Tayyab May 15 '14 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$ – Abdussami Tayyab May 15 '14 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$ – Patrick87 May 15 '14 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$ – Patrick87 May 15 '14 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$ – Rick Decker May 15 '14 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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