Computer Science : Theory of Computation : Turing Machines

From bitrary
Jump to: navigation, search

Computer Science : Theory of Computation


The classical Turing machine has an infinitely long tape of compartments that each always holds exactly one symbol from an alphabet that has at least 2 letters of which one of the letters is always an "empty_symbol", which is the default value for all of the compartments at the infinitely long tape, and then there is a read-write head that can move exactly one compartment to the right or one compartment to the left of its current position or stay at its current position. The program of the Turing machine is a state machine, a directed graph, where the outgoing edges are labeled with the symbols that the read-write head can find from the tape at that given state/vertex. Before leaving the current state/vertex the read-write head overwrites the letter at its current position, the overwriting can be done by re-writing the same letter that was there before, and carries out one of the 3 possible movement activities: move one compartment to the left, move one compartment to the right, stay at the current position id est do not move at all. All of the states/vertexes of the Turing machine have a label that says, whether the Turing machine should keep on working or it should halt. The states with the label value that tells the Turing machine to halt, are called passive states and the rest are called active states.


There are different variations of Turing machines. Some of the variations might have more than one tape, others may have more than one read-write head. The read-write head of some Turing machines might have more movement options than just the classical move-one-to-the-left, move-one-to-the-right, stay-at-the-current-position. A very similar general computation model is based on rewriting text, which might be implemented with something like the Racket.