There are many references to it in public discussions, but trying to learn about it from Wikipedia is like reading in a new foreign language.
In: 283
A Turing Machine is an idea for a simple computer. The idea was revolutionary at the time for a couple reasons.
1. Most machines at the time only did one thing. The Turing Machine could be programmed to do many different things, just like our modern computers nowadays.
2. It turns out that being programmable is extremely powerful, and that a simple Turing Machine can actually do anything a modern computer can, it just might do it way slower and be less practical about it.
3. A Turing Machine was used to help crack the Nazi encryption, providing a massive advantage to the allied powers in WWII. In this case, it wasn’t just an idea. An actual usable Turing Machine was built.
Lots of people mention that a Turing Machine uses tape. The tape is just a way to write down instructions to program the machine. They didn’t have hard drives or discs back then, so they used tape like in old fashioned VHS. Ya know, where the video needed to be rewinded after because it was on actual tape instead of a disc.
Some people mentioned “state machine.” This means that a Turing Machine has rules about how it operates that can be programmed. Once you start running a program, the TM will use it’s rules. Each “state” is one freeze frame of the machine running. It sees one piece of the tape and decides what to do next. If the program doesn’t work right, that’s because it made the wrong choice at some state, and the rules for that state should be fixed.
It’s a simplified imaginary computer. Imagine
* An infinite tape consisting of cells which can store some data (numbers or letters or whatever).
* A “computing unit” which can read and write from one tape cell directly below it. This unit also stores a single datum which we call it’s state (also a number or letter or something, maybe a different kind than those on the tape).
That unit has a list of rules, looking like:
“If I am in state S, and the cell below me contains A, change my state to T, store B into the tape and move the tape one cell to the right/left”
You describe starting situation (computing unit’s state and what’s stored on the tape), then the machine chooses a possible rule from the list (the one which condition is fulfilled by current situation) and executes it. Then chooses another rule applicable to the new situation and executes it, and so on, and so on, until no rule is possible (may or may not actually stop). If it stops you can read the results of the computation from the tape (or the state).
It’s very different than how real computers work, but it’s much simpler to mathematically reason about Turing machines than computers. It also turns out that things that *can* be computed on Turing machine can also be computed on a real computer and vice versa (if you ignore the fact that in reality computers have finite memory and can’t be run for an infinitely long time).
In other words, Turing machine can implement any computation/algorithm.
For example, there are some problems which can’t be computed on *any* computer, even though the problem itself is stated correctly. Mathematical proof of that fact usually uses Turing machines in some way.
A Turing machine is a basic model of a computer that can perform any mathematical calculation by following a set of rules to manipulate symbols on the tape
Turing machines are useful because they provide a simple and fundamental model for how a computer works. They help computer scientists understand what can and cannot be computed by a machine, which is important for developing and analyzing algorithms and programming languages. By using a Turing machine, computer scientists can determine whether a given problem is computable or not, and if it is computable, how much time, space, and resources it will require for a machine to solve it
A turing machine is a theoretical construct, with infinite memory, and a VERY limited set of instructions. Like 3 of em.
What is intersting about them is that they can (with infinite time) replicate all the instructions from any digital conputer. So if you can run a program, on any computer and get some result, that program can be translated into something that will run (generally MUCH MUCH SLOWER) and create the same output with the same functional intermediate steps (they wont necessatily look the same, as memory layout is different, but will be analogous.
So Alan Turing proves that anything that can be done by any computer, can eventually be done with this simple (theoretical : again, infinite memory– not lots of finite memory, infinite memory) machine.
So if something is “Turing complete” it can be shown to be able to (eventually, given infinite time) compute anything that any other turing complete machine/system can compute (not talking about efficiency here. Just possibility. Some arrangements are clearly much more efficient for some tasks, than others).
With those things proven, he then shows that there are programs where it is indeterminite if they will complete or if they will enter an infinite loop. So there are systemsnand processes that, even with infinite reaources, and infinite time. Aka there exist “unsolveable” problems.
Major interssting upshots:
All computing systems (cause almost all have instructions that map turing complete instructions) are essentially equivalent (forgetting the infinite memory/time requirement).
Certain well formed questions are unanswerable.
earlier, you had computers built with parts for a specific task. you’d have a computer for addition, one for subtraction, one for integration, and so on. these computers didn’t resemble our modern computers, in that a programmer will write code to tell it what to do. they were more like very advanced abacuses, using physical objects to perform calculations.
a turing machine was the first conception of the modern computer- one that doesn’t need to be purpose built for a task, but could be programmed to do anything.
with this definition, you’ll see that many things are turing machines, even minecraft!
I’m going to give you a roll of toilet paper and a pencil.
Then we’re going to come up with some set of symbols and some rules.
You will only be able to see one square of the toilet paper in front of you at a time and each square is either blank or has one (and only one) symbol in it.
Your only abilities are to move the toilet paper to the right, move it to the left, erase the symbol that is in the square in front of you, or write a new symbol in the square in front of you.
All of the rules are of the form “if the symbol in front of you is X then do Y” where Y is one of the things above.
Well there you go. That’s a Turing Machine.
Why is this important? Because what you have in front of you is a machine capable of doing everything every computer has ever done. Everything.
With enough toilet paper, rules, and symbols, you can calculate the digits of Pi, play Doom, fly a jet, or even browse the internet if you figure out some way to do the network communication.
That’s what makes it so interesting. Turing reduced all of the items necessary for modern computation down into its simplest form.
I see a lot of answers describing the machine, but I want to give a little background on why this machine was even thought up.
The core idea that the Turing machine tries to capture is *computability*. Think of a problem with a numeric answer. How many ways are there to arrange a deck of cards? Or what is the shortest amount of time it would take to get from San Francisco to LA by car? Those questions have *computable* answers. The cards question is pretty simple, just take a deck and methodically count the arrangements. The car question is a bit more complex, but given a map you could calculate which route would be the shortest.
But it turns out there are some problems with numeric answers that *aren’t computable*. You can verify the answers, but there’s no way to calculate the answer from scratch. One such problem is called the halting problem: how long will a computer take to run an algorithm? This is easy to verify if you have the answer, just run the algorithm and see if it matches your answer. But it turns out that it’s impossible to calculate this before hand. You can make educated guesses, but you cannot compute an exact answer
This is where Turing machines come in. Once you prove a few things about Turing machines, you can use them to prove things about algorithms and whether or not they are computable.
Not technically a response but I’d recommend the movie the Imitation Game! Take with a grain of salt but it’s an engaging way to see a depiction of Alan’s story, true or not
A Turing machine is the most powerful class of theoretical machine we know of, meaning it can solve any computation problem that is possible to solve. All modern computers are essentially Turing machines, but with some limitations, like size, speed, and subjectivity to the environment.
The basic setup is this: a Turing machine has an infinite “tape” which is used in the archaic sense, so it just means an infinite strip of paper with boxes. The machine is attached to this tape and hovers over one box at a time. There are only four operations it knows how to do: read what’s written in the box below it, change what’s written in the box below it, move left, or move right. Each box can either be empty, or have a single mark in it.
The brains of the machine can accept any “program” which is specified as a set of states, with rules about what to do at each state and when to go from one to another. If this sounds confusing, just think of it like a big flowchart, with circles and arrows between the circles with labels like “if box below reads empty, go here.” In order to use a Turing machine, you feed it input by writing marks on the tape, and then you read the output off of the tape when the machine reaches its “done” state.
It may not seem like it, but this machine can be programmed to compute anything a modern computer can, and more. It’s setup is very basic, but even if you invent a much more complicated setup for a machine, like one with two infinite tapes, or an infinite grid, or one with two heads moving along the tape, none of them are capable of computing anything the basic Turing machine can’t.
A Turing machine is a finite-state machine that is hooked up to a length of tape (usually the tape is considered infinite, I believe). The concept of a finite-state machine is quite simple: it is a machine with a limited (finite) number of states, and those states will change depending upon the previous state and external inputs.
The machine can do three things to the tape, depending upon it’s state: move the tape backwards and forwards, read a number off the tape, or write a number to the tape. Numbers that the machine reads off the tape can be considered inputs and will change the state of the machine. The analogy to today’s modern computers should be fairly obvious: the finite-state machine is the CPU, and the tape is the memory.
There are several important results that can be derived from a Turing machine. The most important is that if the machine is “Turing-complete” then it can simulate any other Turing machine. It’s surprising just how simple a Turing machine can be to be Turing complete. I believe there are computer languages with only one or two commands that are considered Turing complete. Excel spreadsheets are Turing complete. So is the template macro system for C++.
Latest Answers