1
$\begingroup$

It seems to me that any problem whose solution requires finite memory can be emulated on a Finite State Machine . This would make those problems that can't be solved by a Finite State Machine to require infinite memory ( like general multiplication of integers ).
My question is what "infinite memory" really means if "infinite" is used in some "completed sense" ( its the negation of finite ). To me the notion of "infinite memory" seems to me so weird and well-defined. How can a problem that requires infinite memory be computable ?

Can anyone help me clarify that ?

Thanks a lot in advance .

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

The correct distinction is between bounded memory and unbounded memory. For example, consider the regular language consisting of all strings of even length. The length of the input is unbounded, but always finite. The memory used by the machine is bounded. In contrast, a machine that accepts the non-regular language $\{ a^n b^n \}$ has unbounded input and also unbounded memory, but its memory usage is still much smaller than the input size, and in particular it only uses a finite amount of memory.

Any machine which always halts on every input is guaranteed to use a finite amount of memory. Only machines that never halt can use infinite memory, and even in their case, at every step they are only using finite memory; only in the limit are they using infinite memory. For example, consider a Turing machine that (ignoring its input) writes 0 on its work tape, moves right, and repeats. The machine never halts, and after $2t$ steps has accessed $t$ tape cells. If you consider the entire infinite computation as a whole, then this computation uses infinitely many memory cells; but at each finite time, only finitely many cells are used.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I still don't understand when my argment went wrong. Did it went wrong in assuming that any problem that requires finite memory can be solved by a finite state machine ? $\endgroup$
    – nerdy
    Commented May 14, 2015 at 15:08
  • 2
    $\begingroup$ Every problem that can be solved using a bounded amount of memory can be solved by a finite state machine. If the memory is not bounded, the state machine won't be finite, since the state machine itself contains in itself every potential amount of memory used by the algorithm. The fact that the actual amount of memory is always finite doesn't mean that the set of possible amounts of memory is finite. $\endgroup$
    – Yuval Filmus
    Commented May 14, 2015 at 15:10

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.