(Sorry for my previous ill-posed question; I deleted it. This question is a refinement.)

For every computer we use, it has finite RAM. In perspective of complexity theory, it's one giant memory that is accessible in constant time. However, Turing machines have unbounded memory, and thus cannot be represented in finite RAM.

I can imagine the unbounded counterpart of RAM; not hardware-wise, but theoretically. A pointer is now not as long as size_t, but rather, is an arbitrary-length integer.

Given that an arbitrary-length integer with $n$ bits is given as the index, a random-access Turing machine would take a time proportional to $n$ to read the index, and immediately jump as much as the index. This gives a non-constant time complexity.

However, I see a vicious circle. As far as I know, implementations of arbitrary-length integers use a pointer, either pointing to the dynamically allocated contiguous array, or pointing to the front of a linked list of digits, or maybe being a null-terminated string. In other words, arbitrary-length integers require pointers, and in the model above, pointers are arbitrary-length integers.

How can I resolve this?


1 Answer 1


Arbitrary-length integers don't require pointers. There are many ways to store an arbitrary-length string without using a pointer. Here is a simple way: encode the $n$-bit string $s_1 \cdots s_n$ as the bit-string

$$1 s_1 1 s_2 \cdots 1 s_{n-1} 0 s_n.$$

This can be stored in contiguous memory. Of course, you can store an arbitrary-size integers in this way too, by converting it to binary, treating it as an arbitrary-length string, and encoding it as above.

  • $\begingroup$ That's analogous to null-terminated strings. How be sure where the string starts? $\endgroup$ Apr 23, 2023 at 4:18
  • $\begingroup$ @DannyuNDos, It starts wherever it starts, you don't need a special mechanism for that. To access memory, the programmer must provide the address (the index into memory) to access; and it will be the programmer's responsibility to provide the appropriate address for the start of the integer. $\endgroup$
    – D.W.
    Apr 23, 2023 at 4:19
  • $\begingroup$ So... Just push the null-terminated string into the stack? $\endgroup$ Apr 23, 2023 at 4:23
  • $\begingroup$ @DannyuNDos, The RAM model does not define a stack. If the program wants to create a stack data structure, it can, and it is the program's responsibility to manage it. All you need to be able to write general-purpose code are load, store, arithmetic, and (conditional) branch instructions. $\endgroup$
    – D.W.
    Apr 23, 2023 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.