TuringMachine

A model of computation studied in TheoComp?, CS81, CS60, and probably elsewhere. The most powerful model of computation there is, if you believe the Church-Turing Hypothesis, and I know I do.

Formally, it's a 7-tuple M = (Q, Sigma, Gamma, delta, q_0, q_accept, q_reject) where Q, Sigma, and Gamma are finite sets, and the following conditions hold:

• Q is the set of states (which makes no sense unless you know something about Finite State Automata, but I'll leave those for someone else to Wiki)
• Sigma is the input alphabet. Sigma may not contain " " (the blank symbol), since the blank symbol indicates the end of the input; it also may not contain epsilon (the null string).
• Gamma is the tape alphabet. Sigma is contained in Gamma, and the blank symbol is in Gamma, as are some finite number of special symbols for various and sundry devious computational purposes; epsilon, however, is not.
• delta is the transition function describing the behavior of the machine upon a certain symbol (by the way, imagine the machine as a little critter with an eye and a pencil that can roll left or right on semi-infinite tape that has symbols written on it... then the machine's actions include writing stuff on the tape and rolling left or right after doing so.)
• q_o (an element of Q, or this is just silly) is the start state
• q_accept (also an element in Q, see above) is the accept state
• q_reject (again, see above) is the reject state.

Turing Machines are named for AlanTuring, a brilliant British mathematician who deserves a Wiki page all his own.

The main CS server used to be a machine named Turing. It was not, however, just a TuringMachine.