Turing Machine - Models Equivalent To The Turing Machine Model

Models Equivalent To The Turing Machine Model

See also: Turing machine equivalents, Register machine, and Post–Turing machine

Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)

A Turing machine is equivalent to a pushdown automaton that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack.

At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.

Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.

Read-only, right-moving Turing machines are equivalent to NDFAs (as well as DFAs by conversion using the NDFA to DFA conversion algorithm).

For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language.

Read more about this topic:  Turing Machine

Famous quotes containing the words models, equivalent, machine and/or model:

    ... your problem is your role models were models.
    Jane Wagner (b. 1935)

    For some men the power to destroy life becomes the equivalent to the female power to create life.
    Myriam Miedzian, U.S. author. Boys Will Be Boys, ch. 4 (1991)

    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)

    The striking point about our model family is not simply the compete-compete, consume-consume style of life it urges us to follow.... The striking point, in the face of all the propaganda, is how few Americans actually live this way.
    Louise Kapp Howe (b. 1934)