0
$\begingroup$

Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.

My Thoughts :
To think of decidability given a graph I could run DFS on each node and see that all the nodes
are reachable from the original node. So it can be determined if the graph is strongly connected
in polynomial time.
But I am confused about the formal automata definition of decidability. Which says a language is
decidable if there is a Turing machine such that this language is the one exactly accepted by the
Turing machine. Now given the above logic of DFS is that enough to prove decidability
or does one have to build a turing machine ?

$\endgroup$
0
$\begingroup$

Yes, the DFS is an algorithm, and hence has an equivalent turing machine. The definition of the decidability as you have said, is for the language to be exactly accepted by some turing machine.

The formal definition of the turing machine accepting the language of strongly connected graphs probably is waaaay too hard to explicitly write, so I guess your teacher meant for you to show an algorithm and state that an algorithm is equivalent to a turing machine.

Btw, as a side note, you can run DFS only twice in total instead of $n$ times - once per node. If you have free time, its a good exercise in algorithms :)

$\endgroup$

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.