Back

ⓘ Turing machine



                                               

Turing

Turing may refer to: Turing machine, an idea in computer science Alan Turing, a computer scientist Turing test, a test to see if a computer can act like a person

Turing machine
                                     

ⓘ 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 languages and solving mathematical functions. Turing machines are one of the most important formal models in the study of computer science.

                                     

1. 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
  • A definition of a so-called transition function
  • An infinite tape with storage cells and a read/write-device that can move on the tape

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 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.

                                     

1.1. Common basics 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.

                                     

1.2. Common basics Turing machines that compute functions

If a Turing machine is used for the computation of functions it only has one end state. When the machine comes to that state it is halted and the result of the function depending on the input can be found on the tape.

                                     

2. Impact of Turing machines

Turing machines were not invented to be built in reality, but they are very important for theoretical computer science as they are one of the simplest models for computers. The Church-Turing thesis states that all computers are only as powerful as Turing machines. This can be used to prove if a problem is solvable by a computer or not.

                                     

3. Variations

  • A Turing machine can consist of multiple infinite tapes and multiple read/write-devices. However it is proven that such machines are only as powerful as single-tape machines. Multi-tape machines are useful when dealing with more complex problems.
  • If a Turing machine has a nondeterministic transition function there can be multiple transitions from one state to many others when reading a character. Again this does not enhance the power of Turing machines. However nondeterministic Turing machines as they are called then may possibly decrease the computation time by a strong amount. This question is covered in the P versus NP-discussion and is not solved yet. Most scientists assume however that nondeterministic machines can work much faster on certain problems.
  • A Universal Turing Machine is a variation which can simulate a Turing Machine with an input.
Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →