I am working on a computability assignment, I want to define a helper predicate IsDefined by:

$IsDefinied(x,n) = \{ 1$ if $\Phi^{(1)}(x,n)$ is defined, $0$ otherwise. Where $\Phi^{(1)}$ is the universal $L$ program, $x \in N$ and $n = \#(P)$ for some program $P$.

I'm not sure if it is computable or not. It looks a lot like the HALT predicate, which leads me to believe that it is not.

I guess what I'm really asking is, what does it mean for a function to not be defined for some input?

  • $\begingroup$ Since you're the one defining $\mathrm{IsDefined}$, you can clarify what you mean by "is defined". What are you trying to do with this predicate? $\endgroup$ – cody Mar 1 '16 at 17:45
  • $\begingroup$ I am going to use this predicate to build a function that will return a value for all natural numbers, using a function that is only defined for most of them. My idea being that I could use unbounded minimization with this predicate to get the next largest natural number that is defined. As for "is defined", I'm not too sure as I stated in the question. I think it may mean "does halt" which would make IsDefined not computable. $\endgroup$ – McAngus Mar 1 '16 at 17:58
  • $\begingroup$ I see. Indeed if you use the standard definition of "defined", which is equivalent to "halting", then $\mathrm{IsDefined}$ is not recursive/computable (by a straightforward reduction to the halting problem). $\endgroup$ – cody Mar 1 '16 at 21:30

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.