Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the deterministic finite automata (DFA), so why do we use the Turing machines instead?

Let's consider a popular example. The language $$L = \{a^nb^n, n\in \mathbb{N} \} $$ is recognizable by a Turing machine, but not by a DFA. Suppose that you are getting a string from a server, and you need to determine whether it belongs to $L$ or not. I'd say you can't do it, because you might, in fact, run out of memory.


1 Answer 1


First, I want to clear a misconception:

On the other hand the input can be external and could therefore potentially be infinite.

Usually unless specified otherwise for some purpose, we do not consider TM inputs to be infinite, only unbounded in length (similar to DFA input strings, as a normal DFA cannot accept or reject a string that never ends). This distinction might be hard to grasp, but it will be useful. If you're curious, you can read up on $\omega$-automata, a class of automatons specifically modeling problems with infinite-length inputs.

It is true that an individual computer is, strictly speaking, more akin to an extremely big DFA than a TM. However, by modeling algorithms as TMs, we are trying to make a more general statement about computability, one that transcends individual computers. The theory of computation seldom concerns itself with the need to establish that a particular student laptop, ancient server or supercomputer can perform a particular computation.

Rather, by modeling a problem as a TM and comparing it to a real computer, we're establishing that the computation is possible in the sense that while a given machine might not be able to actually finish it, the only obstacles are the impractical logistics of acquiring a machine with enough RAM/paper/tape/you-name-it and possibly waiting impractically long, too. Alternatively, we're establishing that a given computer or model (eg. a programming language) can be used to simulate a Turing Machine and therefore compute anything computable under the same logistic constraints. And since the inputs are finite, the amount of memory you need to scrounge up (for a working, terminating algorithm) is finite too.

So yes, the TM does conveniently ignore that a given computer has a bounded memory, but since it doesn't need to represent a "given" computer but any computer, this slip is easy to forgive and doesn't prevent the comparison from serving its purpose. If you need to make formal proofs about a single computational device with bounded memory where the finite amount of states is likely to present an interesting issue, a DFA-equivalent model might indeed be better.


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.