Suppose $f$ is a $\mathbb N$-valued partial function over a subset of $\mathbb N$. If $f$ is computable by a universal register machine program, is the constant partial function $$ g:\text{image}(f)\to\mathbb N $$ defined by $g(x)=1$ for $x\in\text{image}(f)$ and undefined elsewhere also computable by a universal register machine program?

If $f$ is total then I can understand how to define a program for $g$: given input $x$, check if $f(0)=x,f(1)=x,\dots$ and if eventually I find $y$ such that $f(y)=x$ then return $1$. But this process does not seem to work when $f$ is partial: $f(0)$ may cause the program to loop, for instance. Any hints would be appreciated!

  • $\begingroup$ Are you familiar with dovetailing? $\endgroup$ May 16 at 10:41
  • $\begingroup$ I considered this form of dovetailing: compute $f(0)$ by one step; compute $f(0)$ and $f(1)$ by one step; compute $f(0),f(1),f(2)$ by one step, etc. Is this the correct approach? I'm having difficulty coming up with how such a program would be coded using the usual register machine instructions. $\endgroup$
    – Jr.
    May 16 at 11:22
  • $\begingroup$ According to Wikipedia, register machines are equivalent to Turing machines. In particular, they can do whatever a Turing machine can do, dovetailing included. $\endgroup$ May 16 at 12:20
  • $\begingroup$ Yes, it's clear to me now-thank you very much $\endgroup$
    – Jr.
    May 16 at 17:59


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.