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
It’s a kind of a primitive imaginary computer that’s used in science to prove things about computers and algorithms in general. Basically if something can be done on a Turing Machine, then it should be possible to do on an actual computer.
[deleted]
To put it simply, early computers could only perform a single function. Imagine the early code breaking machines used during the 2nd Word War. Really advanced machines, but could only do a single job (or algorithm).
Turing machines are closer to modern computers that can be reprogrammed to perform any algorithm as required.
True Turing machines are more abstract that this, but this is a very simple example.
Turing Machines are not physical machines but abstract models meant for computer science theory. It is essentially a computer “boiled down” to its most fundamental parts – instructions (the accompanying state table) and memory (the tape itself and a head to read said tape). These models also make it a bit easier for the layperson to understand low-level computing concepts by abstracting the physical, real-world computer into a set of simple, easy to understand parts. Turing Machines are good theoretical analogues for real-world computers because if something can be done with a Turing Machine it is theoretically possible to do with a real-world computer.
Edit: Grammar
Alan Turing was one of the pioners in computer science. He was early enough that computers were not really built when he was active and most of the work was theoretical mathematics. You can compare it to modern quantum computers where there is lots of papers about it and lots of algorithms written for them, but so far nobody have built a practical one.
In order to explore the possible limits of computers Alan Turing designed a theoretical computer which used punched tape for instructions and magnetic tape for memory. This was not practical and not meant to be practical but was very simple to describe mathematically. Turing was able to prove that this simple computer was able to calculate anything given enough time. When more practical computer designs came about the researchers working on it could show that they could emulate this touring computer and by extension was also able to do all the same calculations. Even today in computer science we often distinguish between computers and environments which can emulate a Turing machine and those which can not.
It is the historically first way to describe a kind of computation machine that can somewhat be “programmed”. The expression “_universal_ Turing machine” attributes to that further, it is one that can _emulate_ (mimic given the right input) absolutely _any_ Turing machine.
They are mostly a theoretical product from before we had actual computers, but one can build them as-is if one wants to; it just turns out that other kinds of computers are easier to build from the basic components (relays, tubes, transistors). So we did that instead.
So, what is it actually?: They have a **tape/band**, a **head**, and a bunch of **instructions/rules**.
– The **tape/band** is an (in both directions) infinite chain of **cells**, in which we can write exactly one of several symbols. The tape is usually assumed to be initially filled with some input symbols, and all other cells with a fixed symbol meaning “nothing”; say we use 0 for that.
– The **head** is a device that is always positioned at one of the cells of the band. It can move left and right when told so, and has an **internal memory** (formally called the _state register_) which can have one of several states. It can only access the cell it is currently at, which it can both read and write to.
– The **instructions/rules** say how the head acts. At a given moment, the head has a certain internal memory state and looks at a specific symbol. For each such possibility there is one rule that tells the head what to write into that cell, what to change the internal memory to, and if to move to the left or right.
It turns out that the above can do exactly the same as any modern computer we build. One could theoretically convert any computer program you use right now into a Turing machine. It would however be a pointless endeavour, as there is little (or even no) use beyond the knowledge that it _can_ be done.
It’s an idea of a machine that is as simple as possible, but still complex enough to meet the technical definition of a general purpose computer.
So then we can say things like if a machine can do everything a turning machine can do then it is a computer. And subsequently if a task can be done by a Turing machine then it can be done by any computer.
Having Turing machines be very simple makes it easy to prove that specific things are true or false about them. And then per the above statements those things must be true or false for all Turing equivalent computers.
The classic example is the “halting problem”. We can prove that it’s impossible to write a program for a Turing machine that can look at any other program and always correctly say whether or not that program will eventually finish.
Thus it’s impossible for any computer to do that, which is a very interesting conclusion.
There are already some solid responses, but to tack onto them, what makes a Turing Machine notable is it’s ability to read data and perform operations on it. When something is referred to as “Turing complete” it means it can perform all the operations of a computer.
Fun fact: There were [Turing complete computers](https://en.wikipedia.org/wiki/Analytical_engine) designed roughly 100 years before the invention of the Turing Machine.
The idea is actually very simple.
It’s basically an imaginary machine with an infinitely long tape, and there are infinite rows of empty squares or boxes on it, and those boxes are numbered so that you can tell which box is which. Then there’s a “head” or a “scanner” that analyzes that box 1 at a time. That head can write any kind of arbitrary symbols such as a number in that box. Or the head can delete or rewrite the symbol in that box. Or the head can move left or right to the box and move onto another box. Or the head can stop or “halt” the operation.
Well, why would you wanna do that or make something like that? Well if you’re a clever person, then you can potentially give any kind of instructions to this Turing Machine, and then look at the tape to see the result to solve any kind of arbitrary problems. Basically it’s a theoretical machine or a theoretical idea that can be used to automate any tasks, provided that you know how to give such instructions.
Basically a modern computer works in the same way, you give instructions to the CPU, the CPU analyzes and solves that problem 1 at a time, and then writes that result to the RAM or the hard drive. The only difference is that modern CPUs are solving millions of problems or “instructions” in a single second.
It’s a computer science concept that reduces a problem into a single simple instruction, or several simple instructions.
If you have a problem that can be reduced this way, it’s potentially possible that a computer can solve that problem.
For example, your problem is writing something down when you get some numbers. You don’t want to write the numbers down yourself. The problem you have and the solution to solve the problem is considered a Turing Machine because you can have a computer do that for you (like a printer).
Latest Answers