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

From Machinelearning
Revision as of 06:47, 16 September 2018 by IssaRice (talk | contribs) (Created page with "(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 pro...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

(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 Xn0 that sets the value of the variable Xn to zero.
  2. The increment command XnXn+1 that increases the value of Xn by one.
  3. The copy command XnXm 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:NkN is loop-computable if there is a loop program such that for every xNk 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_1
    if counter != 0
        X_0 <- X_0 + 1
    endif
    counter <- counter + 1
endloop X_1