Turing decidable/undecidable

Question

let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$.

can you prove whether $X$ is Turing decidable/undecidable?

this question could be on my exam this week and I need to understand it. please help.

score 1 · Answer 1 · edited Apr 13 '17 at 12:48

1

Per Rice's Theorem, since accepting the empty language is a nontrivial property, $X$ is undecidable. See also this CS link.

edited Apr 13 '17 at 12:48

Community

1

answered Dec 04 '13 at 17:12

Vladhagen

4,878

I think the asker wants to know about the case where $M$ is a DFA, not a Turing machine, though. – universalset Dec 04 '13 at 17:20
@universalset exactly! – Joe Dec 04 '13 at 17:30
Oh, yes. Right you are. – Vladhagen Dec 04 '13 at 18:55

score 0 · Answer 2 · answered Dec 04 '13 at 17:35

This is decidable. A description of a DFA is a directed graph with labelled edges, and to determine if the language accepted by the DFA is nonempty one need only determine if there is any path from the start state, following these directed edges, to some accepting state. Pick your favorite graph search algorithm to do this.

Turing decidable/undecidable

2 Answers2