3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ That's not a question of proof, it's a question of modelling. $\endgroup$ – Yuval Filmus Nov 5 '13 at 8:37
  • 1
    $\begingroup$ Do you mean a computer with no external connections? If you allow a network connection, data can be uploaded and downloaded so the number of states is unbounded (unless you start making "universe is finite" type arguments). $\endgroup$ – Vijay D Nov 5 '13 at 9:36
  • $\begingroup$ I dont know if universe is finite or not, but I know that Earth it is. For now we are not able to obtain resources from other planets, therefore the number of states that we can handle is bounded. $\endgroup$ – MRuizEscribano Nov 5 '13 at 9:56
  • $\begingroup$ This is not a modeling question if there are any proof showing that real computers (read abstract machines with finite resources) are more powerful than finite state machines. In my knowledge abstract machines with finite resources can not output things that need infinite memory to compute (e.g. {a^nb^n} or {a^nb^nc^n} but not {a^n} that can be done with a simple loop). These machines can only generate/recognize a finite subset of these languages, so they can be described by regular languages. Am I wrong? $\endgroup$ – MRuizEscribano Nov 5 '13 at 9:57
  • 1
    $\begingroup$ This question is not clear in intent, and has probably been answered here, here and here. (In order to have a proof you first need a formal model -- chicken or egg?) $\endgroup$ – Raphael Nov 5 '13 at 13:05
12
$\begingroup$

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.

$\endgroup$

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