11.2 Computation Traces
11.2 Computation Traces A Turing machine does not compute in one large jump. It computes step by step. A computation trace records these steps. Each step changes the machine from one configuration to the next. A configuration contains all information needed to continue the computation: Component Meaning current state the machine’s internal state tape contents the symbols written on the tape head position the cell currently being scanned Once these...