1961: Minsky's Model of A Partial Recursive Function Reduced To A "program" of Only Two Instructions
In his inquiry into problems of Emil Post (the tag system) and Hilbert's 10th problem (Hilbert's problems, Diophantine equation) led Minsky to the following definition of:
- "an interesting basis for recursive function theory involving programs of only the simplest arithmetic operations" (Minsky (1961) p. 437).
His "Theorem Ia" asserts that any partial recursive function is represented by "a program operating on two integers S1 and S2 using instructions Ij of the forms (cf Minsky (1961) p. 449):
| Action: | Description: | ||
| a. | ADD ( r, Ij1 ) | + 1 → r; go to instruction Ij1. | Increment (add 1 to) contents of register r and go to instruction Ij1. |
| b. | SUB (r, Ij1, Ij2) | If ≤ 0 THEN go to instr. Ij2 ELSE -1 → r and go to instr. Ij1 | IF contents of register r equals zero THEN jump to instruction Ij2; ELSE decrement (subtract 1 from) contents of register r and jump to instr. Ij1. |
The first theorem is the context of a second "Theorem IIa" that
- "...represents any partial recursive function by a program operating on one integer S using instructions Ij of the forms":
| Action: | Description: | ||
| a. | MULT (Kj, Ij1) | *Kj → r1; go to instruction Ij1. | Multiply contents of register r1 by constant Kj |
| b. | DIV (Kj, Ij1, Ij2) | /Kj = 0 then go to instruction Ij2 else go to Ij1. | If division of contents of register 1 by constant Kj has no remainder then instr. Ij1 else instr. Ij2 |
In this second form the machine uses Gödel numbers to process "the integer S". He asserts that the first machine/model does not need to do this if it has 4 registers available to it.
Read more about this topic: Counter Machine Models, The Models in More Detail
Famous quotes containing the words program, reduced, function, instructions, partial and/or model:
“Most of the folktales dealing with the Indians are lurid and romantic. The story of the Indian lovers who were refused permission to wed and committed suicide is common to many places. Local residents point out cliffs where Indian maidens leaped to their death until it would seem that the first duty of all Indian girls was to jump off cliffs.”
—For the State of Iowa, U.S. public relief program (1935-1943)
“Man in general, if reduced to himself, is too wicked to be free.”
—Joseph De Maistre (1753–1821)
“The function of comedy is to dispel ... unconsciousness by turning the searchlight of the keenest moral and intellectual analysis right on to it.”
—George Bernard Shaw (1856–1950)
“Realizing that his time was nearly spent, he gave full oral instructions about his burial and the manner in which he wished to be remembered.... A few minutes later, feeling very tired, he left the room, remarking, ‘I have no disposition to leave this precious circle. I love to be here surrounded by my family and friends.’ Then he gave them his blessing and said, ‘I am ready to go and I wish you goodnight.’”
—For the State of New Hampshire, U.S. public relief program (1935-1943)
“You must not be partial in judging: hear out the small and the great alike; you shall not be intimidated by anyone, for the judgment is God’s.”
—Bible: Hebrew, Deuteronomy 1:17.
“For an artist to marry his model is as fatal as for a gourmet to marry his cook: the one gets no sittings, and the other gets no dinners.”
—Oscar Wilde (1854–1900)