Trying to figure out if a modern computer is capable of manipulating arbitrarily large pointers

Question

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.

Answer 1

The universe is finite, so you can't build a real turing complete computer.

The best you can do is build a computer which observes whether the program it is running is getting close to the limitations of the computer, and when it exceeds them, builds a new, bigger computer, with higher limits, transfers the code to the new computer, and starts all over again.

PS. It is quite possible (and not really very difficult) to build a computer with 256 bit pointers. Since the universe is not just finite, but has a known size, 256 bit pointers are enough for anything.

Answer 2

Only in any a hardware specific systematic way that I have ever found and I have been looking for examples of anything like this for sometime. I am an amateur, you may well know most of this but here goes;

Computing numbers larger than the wordsize can accommodate is called "bignums" and, as been commented, there are various software solutions to making use of large numbers easily found with google.

There is floating point which basically uses however many bits to represent the number of digits in an exceedingly large or miniscule number but this representation is obviously inaccurate as it represents every one of them as a zero and therefore cannot be used as an address scheme.

"having 64-bit pointers allows for an address space that probably surpasses all the memory currently in existence" I believe it is about 8Tb. As far as I know the 4GB limit is for programs assigning a memory location and is restricted for system security issues.

I googled "dereferencing pointers at the machine level instruction set" and found there is no current machine that can surpass this mechanically as the mechanical limit is set by the number of wires. The hardware itself can only use the timing and control signals that have been built into it.

You can, however, decide on which number of bits each address points to in various ways.

Addressing Modes How are bits of an address field interpreted to find the operand?

1.Immediate addressing.

2.Direct addressing.

3.Register addressing. Operand address is not contained in instruction but in a register

4.Register indirect addressing.

5.Indexed addressing.

6.Based-indexed addressing.

7.Stack addressing.

8.Addressing modes for branch instructions

If you look to point at individual bits the overall address space will be much smaller than if your addressing scheme points to whole words i.e. 64 bits per address, effectively transforming all of memory into a very large array. This as a hardware implementation makes looking for or setting the value of any particular bit necessitate a mask.

The wordsize can be extended to arbitrary amounts, I have no doubt, in that an instruction can use one, two or three dwords of 32 bits each - that is 32, 64 or 96 bits. For example. Instructions must be aligned to dword addresses. The first two bits (most significant bits) of the first dword of an instruction indicates the length: 00 = 1 dword 01 = 1 dword 10 = 2 dwords 11 = 3 dwords so your instruction could be "11 ...." and have an address 3 words long but to balance the computational effort of various tasks and security of the system they are hardwired to specific sizes. I might be mixing things up some.

I personally have envisaged hardware with a systematic structure allowing the address scheme to accommodate an insane number of user defined geometric volumes where the defined space, net or cubespace can also define the complexity of the calculation in order to represent and relate massively parallel 3Dimentional co-ordinates, rotations, waveforms and whatever else but any questions I have proposed on the subject have been closed remarkably quickly.

Hope ive been helpful.