Skip to content

Turing machine

Turing machine非常重要，对于一个software engineer，有必要了解一下它。

维基百科中关于Turing machine的介绍非常冗长，初读起来会比较费劲，所以找了一些其他的相对精简一些的文章，下面罗列了我觉得比较好的阅读顺序：

euston96 Turing machine

The Turing machine is a computer device which consists of a read and write header, what we know best today as a scanner and a paper ribbon that passes through the machine. This tape was divided into squares, and each of them had a symbol at the same time. It was responsible for the storage of the machine and was a kind of vehicle for entry and exit, as well as working memory to store the results of the intermediate steps of the calculation.

What is the Turing machine?

It is a more general language recognition module that any Finite and Stack automaton has, as it has the ability to recognize regular and context-independent languages, as well as many other types of languages.

Features of Turing Machine

The main features of the Turing machine were as follows:

  • The input that the tape has before the calculation begins, must consist of a finite number of symbols.
  • The machine tape has an unlimited length.
  • The read/write head can be programmable.
  • The Turing machine is capable of doing six types of fundamental operations: read, write, move left, move right, change state and stop.
  • It has the ability to compute anything any modern computer can calculate.
  • It consists of an input and output alphabet and a special symbol called white.

History of Turing machine

Alan Mathison Turing was the inventor of the Turing machine. He was known as an extremely talented man, who had great influences on the development of computing and on the formalization of the concept of algorithm and computation through his Turing machine, which played a very important role in the creation of the modern computer.

Turing described it for the first time in his 1936 article dealing with issues concerning computable numbers. In his article, Turing imagines that his creation is not a mechanical machine, but rather a person he decided to call a computer, which carelessly executes these deterministic mechanical rules.