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)
“Right and proof are two crutches for everything bent and crooked that limps along.”
—Franz Grillparzer (1791–1872)
“As in political revolutions, so in paradigm choice—there is no standard higher than the assent of the relevant community. To discover how scientific revolutions are effected, we shall therefore have to examine not only the impact of nature and of logic, but also the techniques of persuasive argumentation effective within the quite special groups that constitute the community of scientists.”
—Thomas S. Kuhn (b. 1922)
“All day long the machine waits: rooms,
stairs, carpets, furniture, people
those people who stand at the open windows like objects
waiting to topple.”
—Anne Sexton (1928–1974)