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 Gdel 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 Gdel numbers cannot be universal.problem of the RASP without indirect addressingSteven 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 Gdel numbers make a register machine universal?
Why does using an encoding trick like Gdel numbers make a register machine universal?
turing machines;computation models;turing completeness