15
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ yes indeed its called "complexity theory" =) .. seriously its helpful to think of the Turing machine as an abstraction which is realized in practice when the computer has large memory, which is quite real due to a variation on moores law in which memory prices have gone down and density/performance has gone up. so depending on the context & the mood of the computer scientist, computers are either said to exactly reflect Turing machines, or not! a real zen question at times. "is a real computer really a Turing machine?" "what is the sound of one hand clapping"? & like a blueprint vs the house $\endgroup$ – vzn Sep 26 '12 at 15:10
12
$\begingroup$

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}$).

$\endgroup$
  • 2
    $\begingroup$ Your answer is very good, and complexity theory seems to be along the lines of what I was interested in investigating. Thank you. Just a note: the sense I got from my professor was just that a Turing machine isn't equivalent to a computer and represents an upper boundary, not that it was irrelevant. Any implication of irrelevance was fully mine, and a mistake in my attempt to try to make clear where I was coming from. $\endgroup$ – JustAnotherSoul Sep 26 '12 at 14:02
5
$\begingroup$

You might consider Linear Bounded Automaton and corresponding languages are the context-sensitive languages. See Chomsky Hierarchy to know which languages are beyond the reach of such automata.

btw, in some sense, some "unreachable" problems now become within reach, because of the restricted computing power!

For instance, Halting Problem for Turing Machines is undecidable, but it is decidable for Linear Bounded Automata.

$\endgroup$
  • $\begingroup$ I hadn't considered the fact that there are problems we CAN solve because of the restrictions. Interesting. $\endgroup$ – JustAnotherSoul Sep 26 '12 at 13:41
4
$\begingroup$

The theory of computation is an abstraction of the real world. In many ways, the abstraction isn't a great fit for the real world. For one, we can't make computers with unbounded memory; so we can't even make machines to recognize arbitrary regular languages - or even arbitrary finite languages!

This turns out not to be too big of a problem, though; in the real world, we can't even construct inputs of any arbitrary size, and even if we could, we wouldn't be around long enough to see the answer.

In a strict sense, then, no: the class of physically realizable computers is strictly less powerful than the class of Turing machines. It's strictly less powerful than the class of finite automata, as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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