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