Skip to content

Definition

Jump to bottom
Kelvin DeCosta edited this page Dec 23, 2019 · 2 revisions

Alan constructs Turing machines based on the following formal definition:

  • machine

    A Turing Machine.

  • states

    A finite, non-empty set of states.

  • start

    The starting state

  • endstates

    The set of final or accepting states.

    The machine is said to accept an input tape if it halts in one of these states.

  • tape

    A finite non-empty set of tape symbols.

  • blank

    A symbol which occurs infinitely often at any step during computation.

  • symbols

    The set of input symbols which are allowed to appear in the initial tape contents.

  • transitions

    A partial function describing the transitions in the Turing Machine.

    Whenever the machine is in a particular state and encounters a particular character in the tape, it is associated with a unique ordered triplet of a state, symbol and direction.

Navigation

Clone this wiki locally