Silence on the Wire

Turing and Instruction Set Complexity

As it turns out, the processor does not have to be complex. In fact, the set of instructions required for a chip to be able to execute just about any task is surprisingly small. The Church-Turing thesis states that every real-world computation can be carried out by a Turing machine, which is a primitive model of a computer. The Turing machine, named after its inventor, is a trivial device that operates on a potentially infinite tape consisting of single cells, a hypothetical, purely abstract storage medium. Each cell can store a single character from a machine “alphabet,” which is simply a name for a finite ordered set of possible values. (This alphabet has absolutely nothing to do with human alphabets; it ...