Turing machine equivalents

A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm. While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model. Turing equivalence Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power. They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (The Church–Turing thesis hypothesizes this to be true: that anything that can be "computed" can be computed by some Turing machine.) The sequential-machine models All of the following are called "sequential machine models" to distinguish them from "parallel machine models". Turing's a-machine model Turing's a-machine (as he called it) was left-ended, right-end-infinite. He provided symbols əə to mark the left end. A finite number of tape symbols were permitted. The instructions (if a universal machine), and the "input" and "out" were written only on "F-squares", and markers were to appear on "E-squares". In essence he divided his machine into two tapes that always moved together. The instructions appeared in a tabular form called "5-tuples" and were not executed sequentially. The following models are single tape Turing machines but restricted with (i) restricted tape symbols { mark, blank }, and/or (ii) sequential, computer-like instructions, and/or (iii) machine-actions fully atomised. Emil Post in an independent description of a computational process, reduced the symbols allowed to the equivalent binary set of marks on the tape { "mark", "blank"=not_mark }.