Is there an algorithm for deciding which statements of number theory are true? - Leibniz’s Question
Can the consistency of number theory be proved using only non-dubious principles of finitary reasoning? - Hilbert’s Question
Section 1 defines the URM.
The URM can store an infinite number of positive integers in registers R1 upto Rn and has the following instruction set:
( Name: Notation ; Effect )
Zero: Z(n) ; Replace the number in R(n) by 0.
Successor: S(n) ; Add 1 to the number in R(n).
Copy : C(m,n) ; Replace number in R(n) by number in R(m).
Jump : J(m,n,q) ; If R(m) = R(n) jump to q otherwise next.
From this limited instruction set a powerful programming language can be constructed.
Section 2 investigates which functions can be implemented on a URM.
The following URM program for example
implements -multiplication- on a URM.
So far. To be continued next week.
- Russell's Paradox. A is the set of sets which do not contain A.
- Russell and Whitehead proved that 1+1=2: more on this page.