In his famous article, "Computing Machinery and Intelligence", Allan Turing talks about discrete-state machines and the largeness of the number of states provided by that time "state-of-the-art" machine, "Manchester Machine", which he states is about 2^165,000. Link to the article

Well, that was 1950's. I'm trying to compare it with modern day computers and get an average number of states for a usual commercial machine. How can I find it?

Is it related to memory size (Turing calculates it by the number of "stores", or sheets of paper available)? If so, would this make the number of states tend to infinity due to the current possibility of writing/erasing memory at will?

  • 1
    $\begingroup$ Hint: How many distinct states can 1 bit be in? 1 byte? 4 bytes? $n$ bytes? $\endgroup$ Mar 15 '17 at 12:44
  • $\begingroup$ Regarding main memory or secondary or both? $\endgroup$ Mar 15 '17 at 12:57
  • $\begingroup$ Use whatever you consider to be "part of" the computer. $\endgroup$ Mar 15 '17 at 13:02
  • $\begingroup$ So, if taking only main memory for the calculation, a 8Gb machine would be something like 2^(2^33)? $\endgroup$ Mar 15 '17 at 13:37
  • 1
    $\begingroup$ Tiago Sirious, would you like to write an answer to your question, based on the understanding you've gained? That might be helpful to anyone else who has a similar question. $\endgroup$
    – D.W.
    Mar 15 '17 at 16:58

Acording to the suggestions that were given in the comments to the question, the number of distinct discrete states possible by a machine are related to the size the machine's of memory (or "stores" space, using Turing's nomenclature).

Since a bit has two distinct discrete states, a byte then have $$ 2^{2^3}=2^8 $$ discrete states.

Two bytes, $$2^{2*2^3}=2^{16}$$

Hence, a commercial availabe 4GB DDR3 RAM machine would roughtly be $$ 2^{2^2*2^{30}*2^3} =2^{2^{35}}=2^{34,359,738,368} $$

Further, today's (March 2017) world fastest computer, Sunway TaihuLight, with more than 1 PB memory, would have rougthlty $$ 2^{2^{50}*2^3}=2^{53}=2^{9,007,199,254,740,992}$$ distinct discrete states.

Correct math if wrong, but the idea is this, taking in account only main memory (disregarding cpu registers, secondary memory and cache, as j_random_hacker stated that could be done).


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.