What is Turing machine?
[[File:Turing Machine Model Davey 2012.jpg|thumb|Model of a Turing machine]] '''Turing machine''' is a term from [[computer science]]. A Turing machine is a system of rules, states and transitions rather than a ''real'' machine. It was first described in 1936 by English mathematician and computer scientist [[Alan Turing]]. There are two purposes for a Turing machine: deciding [[formal_language|formal languages]] and solving [[mathematics|mathematical]] [[Function (mathematics)|functions]]. Turing machines are one of the most important formal models in the study of computer science. == Common basics == A Turing machine consists of the following components (simplified): * A limited set of states (with one state marked as ''start state''; while running, a Turing machine always has a ''current state'') * An infinite tape with storage cells and a ''read/write-device'' that can move on the tape * A definition of a so-called ''transition function'' Also, a working-[[alphabet]] (set of characters) has to be defined. When a Turing machine is started, a word (out of the working-alphabet) must be present on the infinite tape of the machine. The read/write-device on the first character now reads the first character and, depending on the current state of the Turing machine, the read/write-device overwrites the character with a new one or moves one cell to the left or to the right. Furthermore, the current state of the machine can be switched. === Turing machines that decide languages === For [[decidability theory]] a Turing machine is said to ''decide a [[language]]'' if it is always able to determine whether a given word is contained in a certain language or not. Therefore, the machine usually has two special states marked as ''Accept'' and ''Reject''. After a while one of the two states will be reached (depending on the input word) and the machine is halted. If only one of the two states will ever be reached, the Turing machine is said to ''semi-decide'' a language. === Turing machines that compute functions === If a T