# Detect whether one Turing machine invokes another

Given two Turing machines $M,M'$, is it possible to check whether $M$ invokes $M'$?

In other words, is the following problem computable/decidable?

Inputs: Turing machines $M,M'$
Question: Does $M$ ever invoke $M'$?

Perhaps we can look whether $M$ includes the code of $M'$ in it? In a C program we can check whether a function f invokes a function g, right? Can we do this for Turing machines too?

The notion of "one machine invokes another" is ill-defined. To emphasize the point of @AbdousKamel, let us observe an even trickier example:

function g():
do_something;


And now:

function f():
k = 0
while not "k encodes a proof of Riemann hypothesis":
k = k + 1
"simulate the Turing machine encoded by k"


In order to tell whether f "invokes" g, you have to:

1. Decide whether Riemann hypothesis is provable, and
2. Calculate whether the smallest k which encodes a proof of Riemann hypothesis also happens to encode a Turing machine whose behavior is equivalent to the behavior of g.

Question: does f invoke g?

Following the comments of the post, i will try this example, and hope that it shows how hard it is to decide if a function f calls a function g.

Here is function g :

function g()
do_something;


Here is function f, we will use a function called foo whose declaration and definition is not needed :

function f()
foo();
g();


Now, does f calls g ? If I look at the code of f I will say yes, because the call to g is trivially apparent. But how do I know that the call to foo will return ? Maybe foo loops forever and never halts, in this case, f never calls g because it never returns from foo. So deciding in a program if a function calls another needs you to decide if some pieces of programs halt, which is in fact as hard as an undecidable problem can be.

• I'd like to add that if by invocation you mean that a call is present in the code, this example doesn't show anything. But if you want a call to effectively happen, you'll need to consider halting of programs. – user80502 Jan 26 '18 at 12:06