In a Turing machine specified as a transition table, what exactly does one computation step do?
answer
- only one cell is visible
- state and symbol pick the entry
- write, then move one cell
- snapshot is state, tape, position
- finite control, unbounded tape
basics
~20 sA Turing machine step reads the one symbol under the head and, using the table entry for that state-symbol pair, writes a symbol into that same cell, moves the head one cell left or right, and enters the next state.
solid answer
~50 sThe machine is a finite control over one unbounded tape: a finite state set, a finite tape alphabet containing a distinguished blank, a head sitting over exactly one cell, and a table of entries shaped `(state, scanned symbol) -> (next state, symbol to write, direction)`. A step does three things together: it overwrites the scanned cell, moves the head exactly one cell left or right, and switches state. Nothing else is read or touched. The snapshot that fixes everything the machine does next is the configuration, written as state plus tape plus head position — for example `11 q0 +1` means the tape holds `11+1` with the head on the `+`. A computation is a chain of configurations, each yielding the next through one entry, and the machine stops when no entry matches the current pair.
code
pseudocode · 7 lines# tape alphabet: 1, +, blank ; states: q0, q1, q2, halt
# input: a block of 1s, a +, a block of 1s ; head on the leftmost cell
(q0, 1) -> (q0, 1, right)
(q0, +) -> (q1, 1, right)
(q1, 1) -> (q1, 1, right)
(q1, blank) -> (q2, blank, left)
(q2, 1) -> (halt, blank, left)go deeper
Recall the parts: a finite set of states, an unbounded blank-filled tape, a head over one cell, and a table of entries. A step writes into the scanned cell, moves one cell, and changes state.
Explain a configuration as state plus tape plus head position, and derive the next one from a named entry. Be ready to walk a short run out loud and say where the machine stops and why.
Use the model as a costing device: one step touches one cell, so any claim that the machine inspects a region is a loop whose length you should be able to state, and the step count is the work.
Judge when this level of formality pays. An explicit state set and transition table turn a scanner or protocol specification into an enumerable object you can review for gaps, at the price of a document few people will read.
## The parts of the machine A Turing machine is a finite control attached to one tape. Written out, it is a tuple: - a **finite set of states**, with one start state and a halting condition; - a **finite tape alphabet** containing a distinguished **blank** symbol (written `_` below) alongside the input symbols; - a **tape** of cells stretching without bound, holding the input at the start and blanks everywhere else; - a **head** over exactly one cell — the only cell the machine can see; - a **transition table**, whose entries have the shape `(state, scanned symbol) -> (next state, symbol to write, direction)`, where direction is one cell left or one cell right. Two finiteness conditions carry the whole model: the state set and the alphabet are finite, the tape is not. Anything that has to grow with the input must therefore be written on the tape and walked back to later, and walking costs steps. That is what makes a step count an honest measure of work. ## What one step does 1. **Read** the symbol in the cell under the head. 2. **Look up** the pair (current state, that symbol) in the table. 3. **Write** the entry's symbol into that same cell — frequently the symbol that was already there. 4. **Move** the head exactly one cell, left or right, as the entry says. 5. **Enter** the entry's next state. Nothing else happens. No second cell is read, the head never jumps to a remembered position, and no counter outside the tape is updated. When the table has no entry for the current pair the machine stops, and the tape as it stands is the output. Some presentations instead name explicit halting states; the two conventions describe the same behaviour. ## Configurations: the unit you reason about A **configuration**, also called an instantaneous description, is the full snapshot that fixes the future: current state, tape contents, head position. It is conventionally written as a string with the state name immediately left of the scanned cell, so `11 q0 +1` says the tape holds `11+1`, the state is `q0`, and the head is on the `+`. A computation is a sequence of configurations in which each yields the next by exactly one entry. For a deterministic machine the snapshot determines everything that follows, so two runs that reach identical configurations behave identically from then on. A repeated **state** says nothing at all — states recur constantly while the head walks along a block of symbols — which is why the configuration, not the state, is the thing you compare. ## A worked run Here is a whiteboard-sized machine for a unary tallying task. The input is a block of `1` marks, a `+`, and a second block of marks; the machine leaves the total as a single block. Five entries over the alphabet `1`, `+`, `_`: | entry | what it is for | |---|---| | `(q0, 1) -> (q0, 1, right)` | walk right across the first block | | `(q0, +) -> (q1, 1, right)` | overwrite the `+` with a mark, joining the blocks | | `(q1, 1) -> (q1, 1, right)` | walk right across the second block | | `(q1, _) -> (q2, _, left)` | end of input reached; step back | | `(q2, 1) -> (halt, _, left)` | rub out one mark and stop | On input `11+1` the run is six steps: `q0 11+1` -> `1 q0 1+1` -> `11 q0 +1` -> `111 q1 1` -> `1111 q1 _` -> `111 q2 1` -> `11 halt 1` The tape ends as `111`, which is the right total for two marks plus one. Overwriting the `+` was what joined the blocks, and it added one mark too many, which is exactly the mark the final entry rubs out. ## What the shape of the model buys - A step is **local**: it touches one cell. Any sentence of the form 'then the machine checks the rest of the tape' is shorthand for a loop of many steps. - The finite control cannot hold input-sized data, so the tape is the only memory that scales. - A halting run visits finitely many cells even though the tape is unbounded; unbounded means no fixed limit, not that infinitely much gets used. - The table is indexed by state and symbol, never by position, so it stays the same size however long the input grows. - Because the table is a fixed finite object, writing a specification this way makes it enumerable: every reachable pair either has an entry or is a deliberate stopping point.
- What happens when the table has no entry for the current state and scanned symbol?The machine halts there, and the tape as it stands is the result. A partial table is one of the two standard conventions for stopping; the other is to name explicit halting states and give them no outgoing entries. They describe the same behaviour, so a specification only has to say which one it uses.
- Why must the tape be unbounded if every halting run touches only finitely many cells?Each halting run does touch a finite stretch, but no single number bounds that stretch across all inputs: longer inputs need more room. The tape is unbounded so one fixed machine handles inputs of any length. Unbounded is a statement about the absence of a limit, not a claim that infinitely much tape is ever used.
- Why is the state set required to be finite?If states could grow with the input, the machine would carry unlimited memory outside the tape and the step count would stop measuring work — anything could be precomputed into a state name. Finiteness forces every piece of input-sized bookkeeping onto the tape, where reaching it costs head movement, one cell per step.
A clerk at a long drawer of cards may look at only the one card in front of them. A rule sheet says: given what you are doing and what this card says, rewrite this card, step one slot left or right, and change what you are doing.
saying these in an interview costs you the question
- Thinks the head can jump to any remembered cell in one step
- Says the machine reads the whole tape on each step
- Believes the tape is fixed at the length of the input
- Thinks a step either writes or moves, never both at once
- Claims the finite state set can hold the whole input