|Re: HP-15C Turing Complete?|
Message #12 Posted by pascal_meheut on 29 Nov 2011, 12:17 p.m.,
in response to message #11 by Howard Owen
This is not the problem. No real machine has indeed infinite memory but they (or any language) are considered Turing complete if they had so.
Another way is to look at the question is this: let's consider a problem which can be implemented by a Turing machine using N "memories" (or tape spaces). Can a give machine, given sufficient memory solves this problem for any value of N?
If so, it is equivalent to a Turing machine.
Now, let's suppose an HP10C with more memory and more registers and let's check if we can implement an NxN Game Of Life.
We store the status of Cell x/y in register x*N+y obviously and then for each cell, we write the code which computes its next state (and stores it in register N*N+x*N+y).
Basically, we write N*N times the same code adressing different registers.
Then we write the code to copy the new state over the old one. Once again, N*N instructions but nothing complicated.
Basically, we unroll the loops we would have written if we had indirect register adressing.
Finally, we test for a counter or a condition and we exit or go back to instruction 0.
This implements the Game of Life on a HP-10C with a lot of memory.
As the Game of Life is proved to be a Turing machine, the HP-10C is too...
Unless I'm wrong of course.