[Solved]: Formal notion of a call graph for Turing machines

Problem Detail: 

To most computer programs one can assign a "call graph". Is there a formal notion of call graphs of Turing machines?

Motivation is, that one could intuitively call a decidable language $L$ "irreducible" if every Turing machine which decides $L$ has a "trivial call graph" (Trivial here intuitively means, that the machine $M$ which decides $L$ can not call another machine $M'$ during the computation on words). This would intuitively correspond to the notion that "irreducible problems" cannot be solved by breaking them up into smaller problems, for example by divide and conquer.

Another motivation is to understand the concept of composition of Turing machines, which is "equivalent" to understand what is meant when one speaks of "subroutines" (which one could call a "submachine").

Asked By : stackExchangeUser

Answered By : David Richerby

Turing machines have no concept of "calling".

Tou can jump to another state and that can look quite a lot like a procedure call, especially if an author's description of the machine in English uses words that make it sound that way. But that's all you can do. In particular, there's no notion of "return" in a Turing machine. There's no way to say "OK, this procedure is finished – now go back to wherever we came from." All you can do is say "OK, this procedure is finished – now go to this specific point."

Of course, because Turing machines are Turing powerful, you can simulate these things. For example, you can write some notion of a return address on the tape as part of your simulation of a procedure call. But that's not intrinsic to Turing machines: it's just a property of the particular Turing machine you're writing at the moment. A coding convention, if you like.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61235