Are real computers finite state machines?

Problem Detail: 

They have finite resources so they can be modeled by finite number of state what is the same that a finite state machine. There are any proof that it is not true?

Thanks.

Asked By : MRuizEscribano

Answered By : David Richerby

Yes, real computers are finite state machines: they have finite memory so there's a finite number of states the machine can be in. One consequence of this is that a real computer can't recognise $\{a^nb^n\mid n\geq 0\}$.

"But hang on a second!" you're saying, "Any idiot could write a program that recognises that language." Well, suppose your computer has $n$ bits of total storage (memory, disk, anything else you might have plugged in). Even if you use all of that storage to count how many $a$'s you've seen, you can only count up to $2^n$. That means your program can't tell the difference between a string that starts $a^{(2^n)}$ and one that starts $a^{(2^n+1)}$.

But you need to consider the scale of these numbers. A typical computer has, say, 1TB of storage. That means that $n=8\times 2^{40}$ and $2^n \approx 10^{2,600,000,000,000}$. In contrast, the number of atoms in the universe is only about $10^{80}$ and some physicists estimate that the universe will cease to exist in any interesting way in only about $10^{100}$ years, which is about $3\times 10^{116}$ nanoseconds. (Fun fact: the number of seconds in a year is within half a percent of $\pi\times 10^7$.)

In other words, your 1GHz computer only has time to read in about $3\times 10^{116}$ characters before the heat death of the universe, and that's a looong way short of the number of characters you need to feed it to verify that it can't actually accept $a^nb^n$. So, in practical terms, you can consider your computer to be a Turing machine instead of a finite state machine.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16729