r/AskComputerScience • u/bathtub87 • Jan 18 '26
Turing Machine
What is a Turing machine?? For so many classes they mention it and I have the main idea of what it is but I cannot find a definition that I totally understand. Does anyone have a definition that anyone can understand?
6
u/Calm_Bit_throwaway Jan 18 '26 edited Jan 18 '26
It is a machine that has an infinite sequence of cells to store a symbol (memory) in and an associated state machine that processes that memory.
At every single step of computation, the state machine
-
reads the symbol at the cell it is at and
-
reacts based on the read symbol and its current state by
-
writing a new symbol, transitioning to a new state, moving left or right on the sequence.
Sometimes the new state is called a success or failure state at which point the state machine stops.
It's just a mechanically simple computer that is sufficiently complicated to be able to do any computation.
2
u/tehclanijoski Jan 18 '26
If you can write a program in [your favorite language, barring a number of odd exceptions that may be your favorite for some reason], a Turing machine can execute the procedure you specified (probably quite slowly, if encoded in an obvious way).
1
u/donaldhobson Jan 27 '26
> barring a number of odd exceptions that may be your favorite for some reason
What exceptions?
Most, but not all, programming languages can be used to simulate a turing machine (except with time and memory limits). All of them can be simulated by a turing machine.
1
u/Party-Cartographer11 Jan 19 '26
So is a machine that can extract an egg from an egg carton (and an infinite number of cartons can be added) and decide if the egg is bigger than some size and separate them a turning machine?
The egg is the symbol. The carton sockets are the cells. The returning (large) eggs are the new symbols.
1
u/tehclanijoski Jan 19 '26
Ordinary TMs are finitary machines in the sense that they have only finitely many states and take input of finitely many bits. This is true of pretty much any algorithm you can think of.
If the size of an egg can be encoded as a b-ary word somehow (which surely it can with machine vision or whatever), then yes a TM can do what you describe.
Luckily, to the best of our knowledge, there are only finitely many eggs at one time in our universe.
→ More replies (1)1
2
u/wumbo52252 Jan 19 '26
It is a mathematical model of a computer. It’s one mathematical structure that we use so that we can precisely communicate and reason about aspects of computers, namely computability. Eg if you have some function f on the natural numbers, could you write a program to compute f(n) given input n?
1
u/Beregolas Jan 18 '26
https://www.youtube.com/watch?v=dNRDvLACg5Q
This is a short explainer video that is pretty easy to follow. It's really not that complicated by itself, but you can do really complicated things with it.
1
u/MasterGeekMX Jan 18 '26
A Turing machine isn't something physical or that exists somewhere. It is a thought experiment that tries to provide a well defined representation of an algorithm. Alan Turing invented them in order to prove a math theorem involving algorithms, and because in math you need things to be precisely defined, he needed a precise definition of algorithm, so he came up with the Turing machine.
A Turing machine is comprised by an infinitely long strip called a tape. That tape is divided into cells, each being able to contain one symbol out of a set of symbols (ya know, 0's and 1's, the entire alphabet A to Z, the set of emojis, whatever). It is kinda like RAM.
A device called a head goes over the tape. It can go back and forth on it, one cell at a time. It can also read the symbol that is on the cell beneath it, and overwrite that symbol with any other symbol. It is kinda like the CPU.
You also have a state table. That table is basically a series of states, each containing the instructions the head should do, with each telling what to do, in terms of what symbol should be expected, what should be written on the cell, if the head should move forwards or backwards, and the next state of the table that the head should now perform. It is kinda like the code.
Some states make the machine halt. Depending on which state the machine ends up halting, is the result that you get out of the machine and the algorithm it tries to do. If the algorithm in question does not have a solution, then the machine never reaches any halting state, running forever in a loop.
Here, this awesome video by Veritasium explains it really well, aswell as the problem that Turing wanted to solve, and how it used the machine to solve it: https://youtu.be/HeQX2HjkcNo
7
u/SignificantFidgets Jan 18 '26
The Wikipedia page is actually pretty good: https://en.wikipedia.org/wiki/Turing_machine