Proof of Equivalency To Standard Turing Machine
This will prove that a two-track Turing machine is equivalent to a standard Turing machine. This can be generalized to a n-track Turing machine. Let L be a recursively enumerable language. Let M= be standard Turing machine that accepts L. Let M' is a two-track Turing machine. To prove M=M' it must be shown that M M' and M' M
If all but the first track is ignored than M and M' are clearly equivalent.
The tape alphabet of a one-track Turing machine equivalent to a two-track Turing machine consists of an ordered pair. The input symbol a of a Turing machine M' can be identified as an ordered pair of Turing machine M. The one-track Turing machine is:
M= with the transition function
This machine also accepts L.
Read more about this topic: Multi-track Turing Machine
Famous quotes containing the words proof of, proof, standard and/or machine:
“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (1872–1945)
“Right and proof are two crutches for everything bent and crooked that limps along.”
—Franz Grillparzer (1791–1872)
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)
“Man is a beautiful machine that works very badly.”
—H.L. (Henry Lewis)