0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.