I was just thinking about Turing-completeness and its relationship with modern computers. I've always thought that a real computer is not technically Turing-complete. It is equivalent to a linear-bounded automaton; a Turing machine has infinite memory, whereas a real computer has only finite memory.
However, you can add memory to a computer through expansion cards, external mass storage drives, etc. The limiting factor then becomes the maximum size of pointers. Obviously, a 64-bit CPU can store a 64-bit pointer in its general-purpose registers, and languages like C/C++ can easily be modified to support 64-bit pointers. However, I'm not sure if they would be able to manipulate arbitrarily large pointers, and thus an arbitrarily large address space.
My thoughts are as follows: Most modern CPUs include instructions that allow for arithmetic involving arbitrarily large integers. For example, the Intel architecture has the ADC
and SBB
instructions, where the carry flag from the last operation is added or subtracted from the result of the current operation. This allows for addition and subtraction of arbitrarily large numbers in a piecewise fashion.
Theoretically, this could also be done with pointers. Say you want to increment a 1024-bit pointer by some amount. You simply add an immediately addressed value to the pointer using the ADC
instruction in 16 successive operations.
The problem comes when you actually have to dereference the pointer. Intel CPUs, and probably most other CPUs as well, are incapable of operating directly on variables in memory, while simultaneously being incapable of storing an entire arbitrarily large pointer in the registers all at once. You can't dereference a pointer in a piecewise fashion; you have to dereference the entire thing. So it all boils down to the question of whether a pointer can be dereferenced in this fashion. It has occurred to me that I don't actually understand how pointer dereferencing is done at the machine level, and I would like someone to explain how this works.
Of course, this question is of no practical importance, because simply having 64-bit pointers allows for an address space that probably surpasses all the memory currently in existence. I am simply interested in this question from a theoretical standpoint.