Is checking equality of partial recursive functions recursive?

60 Views Asked by At

If I'm given a unary partial-recursive function $ f $, I am wondering if, given $ n $, $$ \{x:f(x) = n\} $$ is recursive. The issue that might come up is that given an $ x $, it might not be in the domain of $ f $, so checking if it is equal to $ n $ might be dubious.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $S$ be any recursively enumerable set which is not recursive. Then the partial function $f$ with domain $S$ and range $\{1\}$ is a partial recursive function, and $\{x:f(x)=1\}=S$ is not recursive.