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:
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)
“This unlettered man’s speaking and writing are standard English. Some words and phrases deemed vulgarisms and Americanisms before, he has made standard American; such as “It will pay.” It suggests that the one great rule of composition—and if I were a professor of rhetoric I should insist on this—is, to speak the truth. This first, this second, this third; pebbles in your mouth or not. This demands earnestness and manhood chiefly.”
—Henry David Thoreau (1817–1862)
“The chrysanthemums’ astringent fragrance comes
Each year to disguise the clanking mechanism
Of machine within machine within machine.”
—Wallace Stevens (1879–1955)