2
$\begingroup$

Is a computer with infinite memory and infinite word size a Turing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we allow constant-time linked list element insertion (at the beginning of the list)?

I doubt this because element insertion requires memory allocation and allocation is usually not a constant-time operation.

$\endgroup$
2
  • $\begingroup$ gii.upv.es/tlsf claims constant-time memory allocation. But does that solution scale for systems of infinite memory (and infinite word size)? $\endgroup$
    – porton
    Commented Apr 16, 2021 at 10:27
  • $\begingroup$ A RAM computational model has no allocation cost. Infinite memory is there. You may assume zero-initialized memory. But initialization to another constant value should be assumed to take O(n) time. $\endgroup$
    – user16034
    Commented May 11, 2022 at 12:57

1 Answer 1

0
$\begingroup$

Oh, I've found an $O(1)$ allocation strategy:

Because our memory is infinite, we may never deallocate: Just add memory at the end of the used space by incrementing a pointer.

$\endgroup$
1
  • 1
    $\begingroup$ How would you implement a process that generates elements and stores them systematically in an unbounded array, and stores randomly selected ones (with probability 1/2) in another unbounded array ? $\endgroup$
    – user16034
    Commented Sep 8, 2022 at 15:42

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.