# Turning machine decidable or not

• Dec 5th 2013, 06:25 PM
stribor40
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
• Dec 6th 2013, 03:05 AM
Rebesques
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)=...
• Dec 6th 2013, 03:50 AM
stribor40
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?
• Dec 6th 2013, 05:52 AM
HallsofIvy
Re: Turning machine decidable or not
By the way, it is "Turing machine" (named for Alan Turing), not "turning".
• Dec 6th 2013, 06:09 AM
stribor40
Re: Turning machine decidable or not
Yes thank you