Pergunta

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").

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top