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

  • 4
    $\begingroup$ Turing machines don't quite work this way. $\endgroup$ – Yuval Filmus Aug 3 '16 at 8:34
  • 6
    $\begingroup$ No, not really. It's just an informal description. A Turing machine is given by a set of states and a transition function - that's it. $\endgroup$ – Yuval Filmus Aug 3 '16 at 8:39
  • 1
    $\begingroup$ Also, there are many constructions where one constructs one machine which calls another machine. You gave an example yourself: cs.stackexchange.com/questions/60952/… $\endgroup$ – user41014 Aug 3 '16 at 8:39
  • 2
    $\begingroup$ These are all informal descriptions. In the end you construct a single Turing machine. $\endgroup$ – Yuval Filmus Aug 3 '16 at 8:39
  • 1
    $\begingroup$ @stackExchangeUser Sure you can. The necessary components are called "programming language" and "compiler". Then use the data-flow analysis tools that fit this language. $\endgroup$ – Raphael Aug 3 '16 at 9:10

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.

  • 4
    $\begingroup$ @stackExchangeUser No, it's not the same as that. First, there is a formal notion of algorithm: it's the Turing machine. Second, I've explained why there is no such thing as "calling" in a Turing machine. Sure, somebody could invent something and call it "calling" and construct a "call graph" based on it, but that thing would have nothing to do with call graphs of procedural programming languages, because general Turing machines have nothing to do with procedure calls. $\endgroup$ – David Richerby Aug 3 '16 at 9:34
  • $\begingroup$ @DavidRicherby I agree, but the argument in the second paragraph falls short. Real programming languages are compiled to assembler where, afaik, "calls" are just unconditional jumps with some maintainance code wrapped around; you get a "whole" program without any concept of procedure calls. Similarly, we could view TMs as assembler and formalize what "M simulates M'" means to create such a call graph. In essence, we'd create a programming language for TMs (and a compiler). I don't know that it has been done explicitly, but it's certainly possible. $\endgroup$ – Raphael Aug 3 '16 at 13:10
  • $\begingroup$ @Raphael OK, sure. So what's a "call graph" for assembler? If your assembly program happens to use the maintenance code you talk about in exactly the way you envisage it should be used, then the call graph makes perfect sense; if it uses it in any other way, then there's probably no call graph again. And the same applies to TMs: if they happen to use the "return" code in the envisaged way, a call graph would make sense. But the TM is free to write whatever it wants to the area of tape used for the call stack -- what's the call graph now? $\endgroup$ – David Richerby Aug 3 '16 at 13:16
  • $\begingroup$ @DavidRicherby Right. Of course, nobody actually writes monolithic assembler programs like that any more for the same reasons nobody gives big Turing machines in proofs explicitly. I think the OP wants to formalize a model that allows modularization, i.e. in which "M simulates M'" is a rigorous statement (even if they disagree). Your paragraph reads as if that were impossible because the underlying model are TMs. $\endgroup$ – Raphael Aug 3 '16 at 13:27
  • 1
    $\begingroup$ @Raphael OK. In that case, I think my claim is "This only works for TMs that are instances of the model in question" or, in more detail, "Sure, but that model isn't a Turing machine: it's a Turing machine with knobs on. You can have call graphs for Turing machines with knobs on but the concept still doesn't apply to standard Turing machines, except for the machines that are directly simulating knobbed Turing machines." $\endgroup$ – David Richerby Aug 3 '16 at 13:30

For TMs, there is no such notion and there can not be. Compare plain TMs with assembler: there are rudimentary operations which together create some effect, but there is little to know syntactic structure.

The concept of procedure calls you have in mind only exists in higher-level programming languages, namely such that have introduced abstractions you can use to modularize your code in a clear way. Compilers take these concepts and translate them into rudimentary code: procedure calls become unconditional jumps with some maintenance code around them.

Looking at the compilate, you won't be able to determine a call graph per se: there are no procedures anymore, just a huge blob of code with jumps in all directions.

The situations with TMs is similar. In proofs, we use higher-level descriptions in an informal way; we expect that every informed reader would, in principle, be able to create a real TM following our sketch -- to compile, essentially. The resulting machine would bear little resemblance to the original description.

Of course, you can happily talk about "call graphs" in these languages -- just don't expect the notion to carry over to TMs any more than a call graph in C carries over to, say, MIPS assembler.

  • $\begingroup$ Actually, instruction sets with CALL and RETURN opcodes (such as x86) allow us to locate procedures and form call graphs, whether statically or only dynamically. $\endgroup$ – Yuval Filmus Aug 3 '16 at 14:27
  • 1
    $\begingroup$ @YuvalFilmus OK, so the analogy between Turing machines and such instruction sets isn't perfect. But Turing machines don't have CALL and RETURN instructions. $\endgroup$ – David Richerby Aug 3 '16 at 14:40
  • $\begingroup$ @stackExchangeUser No. Your properties 4 and 5 are just that: properties, conditions that something must have if you're going to use a particular word to describe that thing. CALL and RETURN are operations, like "Write character $\sigma$, move left/right and go to state $q$." $\endgroup$ – David Richerby Aug 3 '16 at 14:47
  • $\begingroup$ @YuvalFilmus Fair enough. Edited to mention MIPS instead which, afaik, does not have such opcodes. $\endgroup$ – Raphael Aug 3 '16 at 22:08

Quoth Hopcroft and Ullman:

A Turing machine can be formally defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

  • $Q$ is a finite, non-empty set of states
  • $\Gamma$ is a finite, non-empty set of tape alphabet symbols
  • $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  • $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols
  • $\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is a partial function called the transition function, where $L$ is left shift, $R$ is right shift. (A relatively uncommon variant allows "no shift", say $N$, as a third element of the latter set.) If $\delta$ is not defined on the current state and the current tape symbol, then the machine halts.
  • $q_0 \in Q$ is the initial state
  • $F \subseteq Q$ is the set of final or accepting states. The initial tape contents is said to be ''accepted'' by $M$ if it eventually halts in a state from $F$.

Note that lack of a notion of "calling" anything. A Turing Machine executed the steps prescribed by its transition function. There is nothing you could call, because there is no program, no notion of a method, nothing but the transition function.

Other formalisms might be more amenable to defining a call-graph. Things like a RAM for example.

  • $\begingroup$ But how comes, that we construct a "submachine" in the halting problem? There must be a notion of one machine calling another machine. Or one machine is a "submachine" of another. $\endgroup$ – user41014 Aug 3 '16 at 9:03
  • 1
    $\begingroup$ @stackExchangeUser Some (expressions of) proofs of the undecidability of the halting problem might use the word "submachine" but that doesn't mean that there's any formal concept. It's just a word that the author finds convenient. $\endgroup$ – David Richerby Aug 3 '16 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy