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:
“To motorists bound to or from the Jersey shore, Perth Amboy consists of five traffic lights that sometimes tie up week-end traffic for miles. While cars creep along or come to a prolonged halt, drivers lean out to discuss with each other this red menace to freedom of the road.”
—For the State of New Jersey, U.S. public relief program (1935-1943)
“Love is a taste for prostitution. In fact, there is no noble pleasure that cannot be reduced to Prostitution.”
—Charles Baudelaire (1821–1867)
“The intension of a proposition comprises whatever the proposition entails: and it includes nothing else.... The connotation or intension of a function comprises all that attribution of this predicate to anything entails as also predicable to that thing.”
—Clarence Lewis (1883–1964)
“They had supposed their formula was fixed.
They had obeyed instructions to devise
A type of cold, a type of hooded gaze.
But when the Negroes came they were perplexed.
These Negroes looked like men....”
—Gwendolyn Brooks (b. 1917)
“And meanwhile we have gone on living,
Living and partly living,
Picking together the pieces,
Gathering faggots at nightfall,
Building a partial shelter,
For sleeping and eating and drinking and laughter.”
—T.S. (Thomas Stearns)
“Your home is regarded as a model home, your life as a model life. But all this splendor, and you along with it ... it’s just as though it were built upon a shifting quagmire. A moment may come, a word can be spoken, and both you and all this splendor will collapse.”
—Henrik Ibsen (1828–1906)