0
$\begingroup$

Is the only reason for why a modern computer can't implement all computations is that the detailed specification of some algorithmic action (as a natural number) can be larger than what the storage space of the computer allows to process?

I am trying to understand the difference in input implementation between Turing Machines (TMs) and computers. As far as I understand, TMs could take any input because they have an infinite tape. But computers do not have an "infinite tape", and so some computations may be "larger" (in terms of their specification as a natural number) than the computers' own storage space, and so the computers will not even begin processing the input.

Is the above accurate? And if yes, isn't it the case that a computer could read and implement any computation if we are allowed to arbitrary increase the storage space of that computer until it exceeds the specification of the computation-input? Or is there another factor than storage space that also makes a difference between TMs and computers in terms of implementation that we should consider?

Thanks for feedback!

$\endgroup$

2 Answers 2

1
$\begingroup$

You can easily write a Turing machine simulator in your favourite programming language. A universal Turing machine does not need many states, so you can then run the simulator on a universal TM, and indeed the only issue is the tape.

If you implement the tape eg as a doubly-linked list, the simulator could could run into a problem because the pointer to the next cell would eventually exceed whatever bounds for a pointer sizes you have. Alternatively, the entire data structure could exceed the storage space of your harddrive.

Here is another idea how you could implement the tape: The programme could store a tape segment of a few gigabyte in size on a USB stick. If the TM tries to move to the left or right of that segment, the simulator just prompts you to exchange USB sticks, and then continues on the segment which is on the USB stick next. With this model, there is really nothing specific about computers that would limit the ability to simulate TMs. Instead, the limitation is just inherent in your ability to provide more and more USB sticks.

$\endgroup$
3
  • $\begingroup$ Thanks! So from what I understood, there can be two problems with a computer implementing an algorithm: 1) although the size specification of the algorithm as a whole is within the storage space of the computer, some (even simple) programs could need tremendous amount of working space to execute and terminate (like a small busy beaver program), and 2) some programs may simply exceed in size the storage space of my computer. Is that accurate? $\endgroup$ Commented May 13, 2023 at 16:25
  • $\begingroup$ @CharbelBejjani These aren't really separate issues. Memory is memory. $\endgroup$
    – Arno
    Commented May 13, 2023 at 17:57
  • $\begingroup$ Your answer goes in the way of "a computer cannot perform all computations because it can't simulate an arbitrarily large TM". I don't think that the argument is rigorous because performing the computation via a TM simulation is not mandated. $\endgroup$
    – user16034
    Commented May 15, 2023 at 9:07
0
$\begingroup$

TM's have no physical limitations (they are never built). Computers do.

TM's don't have a specific running time (they are never truly run). Computers die after some years.


If you are thinking of a "theoretical computer" of any kind, if it is Turing-complete then it can perform the same computations.

$\endgroup$
3
  • $\begingroup$ Also, they never run out of storage: there is somehow always more tape. Real computers have limited RAM and "disk" space. $\endgroup$
    – SamB
    Commented May 15, 2023 at 18:47
  • $\begingroup$ @SamB: is "physical limitations" so difficult to understand ? $\endgroup$
    – user16034
    Commented May 15, 2023 at 18:50
  • $\begingroup$ @SamB You could build a computer with a printer that prints out order forms for more RAM, bigger hard drives etc. so it would not be limited to the current hardware. $\endgroup$
    – gnasher729
    Commented May 17, 2023 at 7:33

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.