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 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.
Latest Answers