0
$\begingroup$

I was going through the classic text "Introduction to Automata Theory, Languages and Computation" by Hopcroft,Ullman,Motwani where I came across the simulation of a turing machine using a real computer. There the author argued that it shall be almost impossible to carryout the above simulation (not considering universal turing machine) if the number of tape symbols are quite huge. In such a situation it might happen that the code of a tape symbol might not fit in the single hard-disk of a computer.

Then the author makes a claim as:

There would have to be very many tape symbols indeed, since a 30 gigabyte disk, for instance, can represent any of $2^{240000000000}$ symbols.

Now I can't figure out the specific mathematics that the author does...

I assume the usual encoding as we do in digital logic say to encode $8$ symbols we need atleast $3$ bits of code. Then to represent $n$ symbols if $k$ bits are required then we should have the following relation,

$2^{k} = n$

$\implies$ $k=log_2(n)$

Now,

$30$ $gigabytes$ $= 30 \times 2^{33}$ $bits$ $= \beta (say)$

Now if our disk can hold all the $n$ symbols then we shall have the following relation true:

$Disk$ $size$ $= (Bits$ $required$ $for$ $each$ $symbol$) $\times$ ($number$ $of$ $symbols)$

$\implies$ $\beta = k \times n = (log_2(n)\times n)$

Solving graphically I have:

SOLUTION

$n= 7.8 \times 10^{9}$ , which is no where close to the number $2^{240000000000}$

Where am I making the mistake?

$\endgroup$
2
$\begingroup$

You are interpreting this statement backwards - he is not calculating how many symbols can 30 gigabytes represent, he is calculating how many symbols can be represented by using 30 gigabytes to represent a single symbol! That would be necessary to be able to approximate a calculation where each symbol is an infinitely-precise real number.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I got it what you said. so, if no of bits for a single symbol (say $k$) = $30 \times 2^{33} \approx 2.57 \times 10^{11}$ which is close to(but greater than) $2.4 \times 10^{11}$ and we know know, total no. of symbols $\approx$ $2^{k}$ which is an upper bound for the value given in text,i.e. we can surely have total symbols less than the upper bound. But I did not get your last statement That would be necessary to be able to approximate a calculation where each symbol is an infinitely-precise real number. $\endgroup$ – Abhishek Ghosh Apr 21 at 18:11

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.