It’s called a Turing Machine. Can you endlessly stuff more memory in your PC? No you can’t! Its data is indexed with absolute addresses, meaning that one day you will run out of addresses (even if you have endless cash to buy more memory). “Push it to the cloud!” you may say, but then IPV6 addresses are also finite, no matter how abundant.
These are some of the things a Turing Machine can do that your PC cannot:
- Multiply arbitrarily long numbers (your PC will run out of RAM at some point);
- Check if parenthesis are balanced on an arbitrarily long string;
- Be used in logical proofs about what is computable.
So how does the Turing Machine get to have infinite memory? By not having absolute addresses! Instead, its memory access is relative, we tell the machine “go one memory position further” or “go one memory position backwards” but never tell it to jump anywhere, because there would be no way to tell where that place is.
So you can always add more memory to your Turing Machine, as long as you have cash to buy it and atoms in the observable ocean to build it. The machine itself does not have to grow whenever the memory size grows.
This is not an issue for everyday-life computations where absolute addressing makes things a lot easier for computer architects, compiler developers, and app programmers. But it is an issue when we want to use the idea of a computer in a logical proof. And for that it beats the crap out of PC.
For a more complete and eloquent explanation, don’t hesitate to consult the master: Feynman Lectures on Computation.
metapuffer 