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.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 9 '19 at 4:55

Your Answer

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

Browse other questions tagged or ask your own question.