Q&A
Q. Is it really possible to build a Turing machine that simulates a conventional computer like the microprocessor in my laptop?
A. Yes. This is precisely what the Church–Turing thesis says. The classic book by Minsky includes a blueprint for such a Turing machine.
Q. Isn’t the Turing machine model strictly more powerful than real computers, because Turing machines have infinite tapes while real computers have finite memories?
A. In a technical sense, yes. You can simulate a real computer with a massive DFA. However, that DFA would need more 21,000,000,000 states to model a computer with 1GB of memory! While a real computer can access only a finite amount of memory, in practice that amount is nearly limitless if you include the Internet. ...
Get Computer Science: An Interdisciplinary Approach now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
