Problem Detail: In a lecture a professor mentioned that modern computers don’t have as much computational power as a Turing machine because they don’t have infinite memory, and since no computer can have infinite memory the Turing machine is therefore unattainable and simply represents the upper limit of computing. Is there a measure, or definition of what problems (or class of problems) lie beyond the reach of our computing power because of this?
Asked By : JustAnotherSoul
Answered By : Kaveh
If we think of the universe as finite, then anything that needs more memory than that finite amount is beyond our computational ability. However this is not a good model for studying computability, the Turing machine model works much better in reality and that is the reason we use it for studying computation on real computers. A Turing machine doesn’t really need an infinite amount of memory, it only needs an unbounded amount of memory. For example, we can provide additional memory to a computer over time (as the computer needs more and more memory) and then we have something similar to a Turing machine. If we assume that we have unbounded amount of time and memory for finishing our computation then the Turing machine captures this concept of computability in principle quite nicely. Check the Wikipedia article about Turing machines, there is a section that discusses the relevance of the model. If you are interested in feasible computability, then complexity theory (where we consider various amount of resources like time and space for performing a computational task) is closer to the what we can really do in practice than computability theory. Many experts state that the feasible computations fall in the complexity class $mathsf{P}$ (and more recently in probabilistic and quantum versions of $mathsf{P}$, i.e. $mathsf{BPP}$ and $mathsf{BQP}$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4734
