1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user80502 Jan 26 '18 at 12:06

Your Answer

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