0
$\begingroup$

I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples.

A(DFA) = {(M, w): M is a deterministic finite automaton that accepts the string w}

A(TM) = {(M, w): M is a turing machine that accepts the string w}

I know that A(DFA) is decidable and A(TM) is not. But, is A(DFA) a subset of A(TM)?

Improve this question
$\endgroup$
2
  • $\begingroup$ 1. Can you define what you mean by A(.)? Without a definition of that notation, the question is not answerable -- it's not clear what you are asking. 2. What have you tried? What are your thoughts? We don't want to just do your exercise for you; we want to help you understand -- but for that, we need you to show us your attempts. 3. Your title doesn't match the body of the question. Please edit the question to address all of these issues; it can then be considered for re-opening. Thank you! $\endgroup$
    – D.W. ♦
    Commented Apr 30, 2016 at 21:42
  • $\begingroup$ I edited the question. Does it fit the guidelines now? $\endgroup$
    – user6268553
    Commented May 1, 2016 at 3:02

1 Answer 1

Reset to default
4
$\begingroup$

No, A(DFA) is not necessarily a subset of A(TM). When you write "(M, w)" you actually refer to some encoding of M in some alphabet (usually {0,1}). These encodings of DFAs and TMs can be very different.

For a simple example: Let $A_1, A_2, \dots$ be an enumeration of all DFAs, and let $M_1, M_2, \dots$ be an enumeration of all TMs. You could say that you encode $A_i$ as the word $0 \text{bin}(i)$ and $M_i$ as $1 \text{bin}(i)$, where $\text{bin}(i)$ is the binary representation of the number $i$. Then the two langauges you presented are disjunct.

As it seems that this is part of your question: Being a subset and being computationally easier do not relate. Take the set $\Sigma^*$ of all possible words. It is easily decidable (even by a DFA) but every language, even undecidable ones, are subsets of it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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