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 .
Asked By : nerdy
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42555
0 comments:
Post a Comment
Let us know your responses and feedback