# Show this function is partially computable

Let B(x) be a computable predicate. Show that \begin{equation} G_B(r)= \begin{cases} 1 \;\;\;\;\;\text{ if there are at least r numbers n such that B(k) = 1 } \\ \uparrow \;\;\;\;\; \text{ otherwise} \end{cases} \end{equation} I want to write a program with just these four instructions to compute $G_B$(r)

\begin{array} \\ \;\;\;\;\;\;\;\;\;Y \gets 0 \\ \;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\ [E] \;\;\;\text{ GOTO } E \\ [A]\;\;\;\; Y \gets Y+1 \end{array}

The book gives examples for writing programs to compute $G(x_1,x_2)$ but does not give any when predicates are involved. Could someone give just an example for even a completely different function with predicates or just point me in the correct direction.

Since $B$ is a computable predicate, there is one procedure that computes it. We can call this procedure in any point of our program.

K <- k
i <- 0
LOOP
RESULT <- B(i)
IF RESULT != 0 GOTO TRUE
GOTO ELSE
TRUE
K<-K-1
ELSE
IF K != 0 GOTO KEEP_GOING
GOTO BREAK
KEEP_GOING
i <- i+1
GOTO LOOP

BREAK
RETURN 1


You will need to substitute the instruction K <- K-1 by an appropriate procedure.

To understand what is going on, we are looping through every natural number and checking whether it satisfies the predicate $B$, keeping a counter that diminishes every time we find one such number. So when the counter K reaches zero we know that the function should return 1, and we proceed to do exactly that.