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:
“The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
—Charles Baudelaire (1821–1867)
“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (1731–1800)
“Gentlemen, those confederate flags and our national standard are what has made this union great. In what other country could a man who fought against you be permitted to serve as judge over you, be permitted to run for reelection and bespeak your suffrage on Tuesday next at the poles.”
—Laurence Stallings (1894–1968)
“He is no more than the chief officer of the people, appointed by the laws, and circumscribed with definite powers, to assist in working the great machine of government erected for their use, and consequently subject to their superintendence.”
—Thomas Jefferson (1743–1826)