# Universal register machine that recognizes the image of a partial function

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!

• Are you familiar with dovetailing? May 16 at 10:41
• 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.
– Jr.
May 16 at 11:22
• According to Wikipedia, register machines are equivalent to Turing machines. In particular, they can do whatever a Turing machine can do, dovetailing included. May 16 at 12:20
• Yes, it's clear to me now-thank you very much
– Jr.
May 16 at 17:59