How to write a program from a predecessor function using only the clear, successor, copy, for loop and while loop commands?

Question

This is a question from the first chapter of Herbert Endertons Computability book

I've been stuck on it since yesterday and its been driving me crazy. The basic commands from this language are as follows:

1) x <- 0 - to assign the value 0 to x

2) x <- x + 1 - the successor command

3) x <- y - the copy command (leaves the value of y unchanged)

4) loop x, P, endloop x - loops the instructions P by the number k times, where k is the initial value of x

5) while x \neq 0, P, endwhile x \neq 0 - the program keeps executing P so long as x is not equal to zero, and therefore running P can affect the value of x and the number of times it is run

I don't know why but I just can't seem to get a program for computing x-1 out this. It seems easy enough using primitive recursive functions... any help would be greatly appreciated!

Answer 1

I think you are probably looking for how to make the function $\mathrm{subtract1}:\mathbb{N} \rightarrow \mathbb{N}$ which is basically $subtract1(x)=x-1$ with the exception that $subtract1(0)=0$.

How about this? I suppose you are looking for something similar to this.

$\mathrm{function \,\,\,\,\, subtract1 \,\,\,\,\, // \,\,x \,\, is \,\, the \,\, input \,\,argument} \\ \mathrm{t:=0 \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, // \,\, temporary \,\, variable} \\ \mathrm{y:=0} \\ \mathrm{Loop \,\,\,\,\, x} \\ \,\,\,\, \mathrm{Loop \,\,\,\,\, t} \\ \,\,\,\,\,\,\,\, \mathrm{y:=y+1} \\ \,\,\,\, \mathrm{End} \\ \mathrm{t:=0} \\ \mathrm{t:=t+1} \\ \mathrm{End} \\ \mathrm{return \;\; y} \\ \mathrm{End \,\,\,\,\,\,\,\,\,\,\,\, //\,\, Ends \,\, the \,\, function} $

Answer 2

If we can assume that $x > 0$, then the following program in the restrictive language looks like it should work.

y <- 0
loop x
    z <- y
    y <- y+1
endloop x

At completion of the program, $z = x-1$.