# Thread: Turning machine decidable or not

1. ## Turning machine decidable or not

Given
Code:
M = {<A> | A is  DFA and L(A) = empty set  }
and <A> is some encoding of machine A
Is M decidable?

Can someone work with me on how to solve these kinds of problems. This is example problem. We can walk trought similar problems. All online examples seems to be too abstract.
help would be much appreciated

thank you

2. ## Re: Turning machine decidable or not

You only need to construct a TM that decides on a ...null language!

So, regardless of input X, the DFA B for the complementary input, will obey L(compliment of X)=...

3. ## Re: Turning machine decidable or not

hi
thanks for response
how do you answer these questions in general.
i know DFA for empty is just machine with one state which is final as well
i am just confused how to build these TM . How do you use universal machine in these kinds of questions?

4. ## Re: Turning machine decidable or not

By the way, it is "Turing machine" (named for Alan Turing), not "turning".

5. ## Re: Turning machine decidable or not

Yes thank you
I am sorry about that

6. ## Re: Turning machine decidable or not

Many questions about DFAa are decidable because finite automata have finitely many instructions and finite memory, so they can be exhaustively explored. For example, to check if an automaton does not accept any words, one needs to follow all possible paths starting from the initial state and make sure that one cannot arrive at the accepting state. So this is a graph reachability problem.

To understand these things, the best thing is to read a good textbook, such as Elements of the Theory of Computation by Lewis and Papadimitriou. Feel free to post other questions here as well.