Let $M$ be a deterministic Turing machine with totally defined transition function $\delta$ and working alphabet $\Gamma$. Let $Q$ denote the statespace of $M$'s finite control. Let $G_M$ be the graph induced by $\delta$ which is defined as $G_M = (V,E)$ with $V = Q$ and $(q,q') \in E$ iff there exist $a,b \in \Gamma$ and $m \in \{\pm 1\}$ such that $\delta(q,a) = (q',b,m)$. Are there any results which translate properties of the machine $M$ to graph theoretic properties of $G_M$ and vice versa?


1 Answer 1


Not likely: almost every property of a Turing Machine is undecidable, and almost every property of a graph is decidable.

If you ignore tape contents, you don't have Turing machines, you have finite automata. But graphs can't really represent tape content.

You can perform some trivial dead code analysis, but there may be unreachable states which are reachable in your graph.


Your Answer

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