Multi-track Turing Machine - Proof of Equivalency To Standard Turing Machine

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, machine, proof and/or standard:

    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 machine is impersonal, it takes the pride away from a piece of work, the individual merits and defects that go along with all work that is not done by a machine—which is to say, its little bit of humanity.
    Friedrich Nietzsche (1844–1900)

    The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.
    Andrew Michael Ramsay (1686–1743)

    Any honest examination of the national life proves how far we are from the standard of human freedom with which we began. The recovery of this standard demands of everyone who loves this country a hard look at himself, for the greatest achievments must begin somewhere, and they always begin with the person. If we are not capable of this examination, we may yet become one of the most distinguished and monumental failures in the history of nations.
    James Baldwin (1924–1987)