User:IssaRice/Computability and logic/Decrement command in loop programs

From Machinelearning
Revision as of 06:51, 16 September 2018 by IssaRice (talk | contribs)

(started typing this up as a question for math SE, but I think I got it)

Herbert Enderton’s Computability Theory: An Introduction to Recursion Theory defines a loop program as one made up of the following commands:

  1. The clear command Xn←0 that sets the value of the variable Xn to zero.
  2. The increment command Xn←Xn+1 that increases the value of Xn by one.
  3. The copy command Xn←Xm that sets the value of Xn to that of Xm and leaves the value of Xm unchanged.
  4. The loop command loopXn;P;endloopXn that takes a program P and executes it Xn times. Here the value of Xn may be changed inside the loop, but this will not affect the number of times P is executed. (This ensures the overall program always terminates, assuming P does.)

The output of a program is always stored in X0. A function f:Nk→N is loop-computable if there is a loop program such that for every x∈Nk the program started with (X1,…,Xk)=x (and zero in all the other variables) halts with f(x) in X0.

The book then states (without proof, as far as I can tell) that a function taking values in N is loop-computable if and only if it is primitive recursive.

I am confused that the above definition of a loop program does not have a decrement command. When I look at other definitions I see that they have a decrement command.

I have noticed that I can implement a decrement program given if-else conditionals, as follows:

loop X₁
    if counter != 0
        X₀ ← X₀ + 1
    endif
    counter ← counter + 1
endloop X₁

n≠0⟺n≥1, so we just need a program that checks if the input is at least 1:

loop X₁
     X₀ ← 1
endloop X₁