Menu
What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?
405
What is a Turing Machine? A Turing machine consists of an infinitely long tape, which has been divided up into cells. Each cell can contain either a 1 , a 0 , or an empty space. Above one cell of the tape is a head, which can either move left or right, and can read the symbols written in the cells.
A Turing machine is a theoretical machine that manipulates symbols on a tape strip, based on a table of rules. Even though the Turing machine is simple, it can be tailored to replicate the logic associated with any computer algorithm. It is also particularly useful for describing the CPU functions within a computer.
A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine).
The reason that Turing Machines are a big deal has to do with the study of classical Computing Science or Theory of Computation type stuff. It's basically about analyzing the general properties of a computer, such as what theoretical abilities and limitations a computer has, as well as what we mean when we talk about "computing" something.
One example of something that one might study using Turing Machines is The Halting Problem. While this problem is something of an academic exercise, it has easily tangible real-world implications. Why not write a debugger that will simply tell you whether or not your program contains any infinite loops? The Halting Problem establishes that solving this problem for the general case is impossible.
The study of Turing Machines also lends itself to studying language grammars and classes of thereof, which leads into programming language development. The term "regular expressions" comes about because they are a regular grammar, and the study of these grammars (part of Theory of Computation) will tell you more about exactly what kinds of problems regular expressions can solve and what they can't. For example, a traditional regular expression syntax won't be able to solve the following problem: parse some number N of 'a' chars in input, and then parse the same number N of char 'b'.
If you're interested in a good text about this sort of thing, check out Introduction to the Theory of Computation by Michael Sipser. It's good.
173
The Turing machine is a theoretical computing machine invented by Alan Turing to serve as an idealized model for mathematical calculation, basically its a simple form of computer, its composed by a tape (a ribbon of paper), has a head that can read the symbols, write a new symbol in place, and then move left or right.
The Turing machine is said to be in a certain state, and then a program is a list of transitions, having a current state and a symbol under the head, what should be written on the tape, what would be the next state, and where the head should move.
Here is a Basic Turing Machine, implemented in JavaScript...
And a sketch:
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
