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

    From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.
    Johan Huizinga (1872–1945)

    The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.
    Charles Baudelaire (1821–1867)

    Liberty requires opportunity to make a living—a living decent according to the standard of the time, a living which gives a man not only enough to live by, but something to live for.
    Franklin D. Roosevelt (1882–1945)

    I brush my hair,
    waiting in the pain machine for my bones to get hard,
    for the soft, soft bones that were laid apart
    and were screwed together. They will knit.
    And the other corpse, the fractured heart,
    I feed it piecemeal, little chalice. I’m good to it.
    Anne Sexton (1928–1974)