Turing Machine Equivalents - Machines Equivalent To The Turing Machine Model

Machines Equivalent To The Turing Machine Model

Turing equivalence

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). 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). (The Church-Turing thesis hypothesizes this to be true: that anything that can be “computed” can be computed by some Turing machine.)

The sequential-machine models

All of the following are called "sequential machine models" to distinguish them from "parallel machine models" (van Emde Boas (1990) p. 18).

Read more about this topic:  Turing Machine Equivalents

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

    If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.
    John Updike (b. 1932)

    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)

    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)

    It has to be acknowledged that in capitalist society, with its herds of hippies, originality has become a sort of fringe benefit, a mere convention, accepted obsolescence, the Beatnik model being turned in for the Hippie model, as though strangely obedient to capitalist laws of marketing.
    Mary McCarthy (1912–1989)