Talk:Primitive recursive function: Difference between revisions

Revision as of 16:49, 31 May 2008

Revision as of 18:31, 31 May 2008

Line 83:

If you feel that the material is a difficult concept, then please abandon the approach of providing strict declarative knowledge, which really says nothing precisely about a topic at all, only relationships relevant to that topic.

Since this particular topic is of interest to computer scientists, a strictly mathematical approach is of good use but not sufficient. I look forward to seeing an updated page. 14:39, 9 May 2008 <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Org322001|Org322001]] ([[User talk:Org322001|talk]] • [[Special:Contributions/Org322001|contribs]]) </small><!-- {{unsigned|Org322001}} -->

---

The simple one-accumulator [[register machine]] might offer a (non-strict) example of the five axioms. In this example the axioms boil down into a few primitive machine operations:

#:1 '''Constant function''': 0 is primitive recursive: CLEAR r, (abbreviated CLR r) where "r" is any register that the machine has access to, symbolized as 0 --> r.

::Suppose we have four registers A, P, Q, R. Then CLR P will cause the contents of register P to be 0 (in other words, P will be empty of counts): 0 --> P. Registers A, Q and R will be unaffected.

#:2 '''Successor function''': INCREMENT r (abbreviated: INC r)

:: Example: INC P will add one count to register P, the ''contents'' symbolized with brackets around the register (cf. Boolos-Burgess-Jeffrey symbolism): [P]+1 --> P

#:3 '''Projection function''': i.e. we have access to any register in the machine. We need to distinguish the two types: COPY and MOVE. COPY r1,r2 i.e. copy the contents of r2 into r1. This is easier to see if we restrict our model to a machine with a special "accumulator" register that we call "A", and the instruction "LOAD r" ( LDA r) that does the following: [r] --> A.

:: Example: LDA P, symbolized [P] --> A

:: Example: LOAD A,P symbolized [P] --> A

#:4 '''Composition''': STOREA r (abbreviated: STA r). COPY the contents of A -- the contents may be the result of many operations -- into any register (including itself); the contents of A is left untouched.

#:5 '''Primitive recursion''': The IF ... EQUALS ... THEN GOTO ... operation. We need any two of the following 3 versions:

:* 5.1: IF the contents of register A EQUALS the contents of register r, then JUMP_TO instruction 7 (abbreviated: JE A,r or perhaps, JEA r)

:* 5.2: IF the contents of register A is ''not'' equal to the contents of register r then GOTO instruction x (abbreviated: JNE A,r,x or perhaps JNEA r,x. 7: Jump if A is Zero to instruction 7)

:* 5.3: "Unconditional jump" (JUMP_TO instruction x, appreviated J x ).

Primitive recursion actually involves incrementing too, so really, primitive recursion is an IF-THEN LOOP that counts up until the IF THEN is satisfied, at which point the function either terminates (HALT) or leaps to another instruction.

Line 108 ⟶ 110:

:: 1 CLEAR A ;register A is a counter to be used in the two recursions

:: 2 CLEAR R :register R is where the result will appear

:: ;First primitive recursive loop -- copies the count in register P into result-register R:

::: ;1st primitive-recursive loop:

:::: 3 JEA P,7 ;Is (contents of) A equal to (contents of) P? If so then go to instruction 7 else continue to next instruction.

:::: 4 INC R

:::: 5 INC A

:::: 6 JUMP_TO 3

:: Second primitive recursive loop:

:: 7 CLEAR A ;A will again be used as a counter to add the counts in Q to the counts in R

::: ;2nd primitive-recursive loop:

:::: 8 JEA Q,12 ;Is A equal to Q? If so then go to instruction 12 else continue to next instruction.

:::: 9 INC R

:::: 10 INC A

:::: 11 JUMP_TO 8

:: 12 HALT ; [R]=[P]+[Q]

The above is only one version of ADD -- maybe the reader can suggest a better one -- but it illustrates the point. I don't know whether something like this would help a reader or not. One thing that comes out of it is that we know from [[Turing equivalence]] that other "instruction sets" are sufficient. Indeed, there are other sufficient axiom sets besides the "Peano set" given in this article. Who is it ... [[Laszlo Kalmar]] (1943) it was ... who originated another set similar to the [[counter machine]] (i.e. his set starts with constant 1, has INCREMENT, a subtraction (DECREMENT) and the finite sum and finite product -- these are where recursion appears (cf Kleene 1952/1971:285 and p. 526 citing Kalmar 1943). Bill [[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 16:56, 9 May 2008 (UTC), slight emendation [[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 18:31, 31 May 2008 (UTC)