# How does one formally show that bounded search with some property $R(a,x)$ is computable i.e. $\exists x \in \mathbf N (x < y \to R(a,x) )$?

Everything here is in the L-structure $$\mathbb N = (\mathbf N;0,S,+,\cdot,<)$$. I was following these notes and got stuck with the lemma 5.1.11 page 84 of paper (88 pdf):

In this context we assume that +,$$\cdot$$,$$R$$,$$I^n_i$$ are computable where $$R$$ are relations and $$I^n_i$$ is the coordinate function (just indexes). We assume composition of computable functions are computable and that search s.t. some property holds is computable i.e. $$\mu x( G(a,x) = 0 ) = arg \min_{x \in N}\{ G(a,x) = 0 \}$$ if $$\exists x$$ s.t. $$G(a,x) = 0$$ is computable. Also, $$F_R(a,y) := \mu x( R(a,x) \lor x = y )$$ has already been shown to be computable.

So the goal is to show that the indicator/characteristic function of the relations $$P$$ and $$Q$$ are computable. Let's consider the relation $$P$$ first. We want to show the following is computable (in the formal sense defined here and the notes):

$$X_P(a,y) = \begin{cases} 1 & \text{ if } \exists x \in \mathbf N (x < y \to R(a,x) ) \\ 0 & \text{ if } \forall x \in \mathbf N (x \geq y \land \neg R(a,x) ) \end{cases}$$

the solution seems to be $$X_P(a,y) := X_<(F_R(a,y),y)$$ which doesn't make sense to me.

The reason is that we want the indicator function that returns true if there does exist a real number s.t. the implication $$x is true. My claim is (if I understand things correctly) that this indicator function is really boring because it always returns 1. This is because it requires the implication $$x to be true for some $$x$$. But such an $$x$$ always exists because we are only allowed to use natural numbers (i.e. we are in the L-structure $$\mathbb N$$), so we can trivially find such an $$x$$ by setting $$x=y$$ (then it doesn't matter if $$R(a,x)$$ is false or not because the antecedent is false). Thus since $$\mu x (x = y)$$ and that always exists then we have $$X_p(a,y) := X_=(\mu x (x = y),y)$$. Which seems extremely silly. So I must have some very weird misconception or something.

In fact I just noticed that it is possible for some $$R$$ for this function to want to return both 1 and 0 at the same time. By my previous argument $$x=y$$ makes the antecedent false so it returns 1. Now consider when it returns 0. For it to return zero we must not have a natural number x s.t. $$(x. Equivalently we must have that $$\forall x \in \mathbf N, (x. If we just choose an $$R$$ such that its always false for $$x (say x is not zero), then we have that the condition for false is satisfied simultaneously to the condition to true. Which obviously doesn't make sense and something must be wrong in my reasoning of course (since the conditions for the function seem quite sensible to me, intuitively, I don't see why they encode the halting problem in any funky way, so I assume I wrong somewhere).

Do I have a misunderstanding or misinterpret something?

• $\exists x_{<y} R(a,x)$ means $\exists x(x<y \land R(a,x)),$ not $\exists x(x < y \to R(a,x)).$ You are confusing it with the $\forall x_{<y}$ abbreviation which means $\forall x (x < y \to R(a,x)).$ – spaceisdarkgreen Nov 10 '18 at 18:35
• @spaceisdarkgreen how did you know what each abbreviation meant? I've been confused about this for days. – Pinocchio Nov 10 '18 at 18:42
• $(\exists x < y)R(a,x)$ must mean "there exists an $x$ less than $y$ such that $R(a,x)$ holds". This is expressed by $\exists x ( x< y \land R(a,x)).$ Similarly with "for all $x$ that are $<y,$ $R(a,x)$ holds." – spaceisdarkgreen Nov 10 '18 at 18:47
• @spaceisdarkgreen why can't the second one be $\forall x ( x < y \land R(a,x) )$. It's totally symmetrical. I don't see why that's not a sensible definition, especially based on the previous definition. – Pinocchio Nov 10 '18 at 18:48
• No, $\exists x (x< y \to R(x,a))$ is simply true regardless of $y.$ Since there is always an $x$ such that $x<y$ is false, and therefore $x< y\to R(x,a)$ is true. – spaceisdarkgreen Nov 10 '18 at 18:59

## 1 Answer

Natural number bounded quantifiers are computable if their formula arguments are computable. In the simplest case you can see that in that you provide a primitive recursive def.

$$P(a,0) \leftarrow \bot$$
$$P(a,y+1) \leftarrow P(a,y) \vee R(a,y)$$

$$Q(a,0) \leftarrow \top$$
$$Q(a,y+1) \leftarrow Q(a,y) \wedge R(a,y)$$

Computable predicates are closed over primitive recursion. The $$μ_{x operator from the script in Lemma 5.1.10 is a form of primitive recursion.

Disclaimer: I am assuming that computable means here nothing more primitive than primitive recursive, rather something above. I didn't read the full script.

• what do you mean by "their arguments are computable"? – Pinocchio Nov 10 '18 at 19:06
• though your answer only makes sense after the horrible notation in those notes is clarified. Thanks though! – Pinocchio Nov 10 '18 at 19:14
• fantastic! thanks so much! I think with that link you've resolved my confusion for sure. – Pinocchio Nov 10 '18 at 19:17
• "Computable" (= "recursive") is much broader than "primitive recursive." – Noah Schweber Nov 10 '18 at 20:05