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:
“In the reproof of chance
Lies the true proof of men.”
—William Shakespeare (1564–1616)
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“An indirect quotation we can usually expect to rate only as better or worse, more or less faithful, and we cannot even hope for a strict standard of more and less; what is involved is evaluation, relative to special purposes, of an essentially dramatic act.”
—Willard Van Orman Quine (b. 1908)
“But a man must keep an eye on his servants, if he would not have them rule him. Man is a shrewd inventor, and is ever taking the hint of a new machine from his own structure, adapting some secret of his own anatomy in iron, wood, and leather, to some required function in the work of the world. But it is found that the machine unmans the user. What he gains in making cloth, he loses in general power.”
—Ralph Waldo Emerson (1803–1882)