Here the author describes the Random Access Stored Program machine and the problem of indirect addressing.

The author states:

But this does not solve the problem (unless one resorts to Gödel numbers). What is necessary is a method to fetch the address of a program instruction that lies (far) "beyond/above" the upper bound of the finite state machine's instruction register and TABLE.

However, with only 4 registers, this machine has not nearly big enough to build a RASP that can execute the multiply algorithm as a program. No matter how big we build our finite state machine there will always be a program (including its parameters) which is larger. So by definition the bounded program machine that does not use unbounded encoding tricks such as Gödel numbers cannot be universal.

problem of the RASP without indirect addressing

Steven Wolfram weighs in saying:

The results of page 100 suggest that with 2 registers and up to 8 instructions no universal register machines (URMs) exist.

My question is: Why does using an encoding trick like Gödel numbers make a register machine universal?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.