# Determining whether Turing machine halts on input: primitive recursive?

In Elements of the Theory of Computation by Lewis and Papadimitriou, the authors use a specific function for proving that application of unbounded minimization on a primitive recursive function need not be regular. They choose a peculiar function to prove so, defined as follows.

Let $$M=\{K,\Sigma,\Delta,s\}$$ be a Turing machine. Define $$G(n,m)=0$$ if $$n$$ does not belong to $$\Sigma^*$$ or if $$m$$ is the output of Turing machine $$M$$ when presented with input $$n$$, and let $$G(n,m) = 1$$ otherwise.

They then go on to show why an application of unbounded minimization on the above reduces to the problem if $$M$$ halts for every $$n$$. My question is why is $$G$$ even primitive recursive? Because $$M$$ may not be primitive recursive.

• You probably got something wrong, but it is hard to tell without taking a look at the book. You can prove this using a slightly different function: $G(n,t) = 0$ if the $n$'th Turing machine halts on the input within $t$ steps, and $G(n,t) = 1$ otherwise. Then $\min_t G(n,t)$ solves the halting problem. – Yuval Filmus Feb 9 '19 at 4:55