Turing-machine traces and computability limits

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Turing-machine traces and computability limits

A Turing machine is a formal model with a finite control, a tape alphabet, a read/write head and transition rules. A transition depends on the current state and scanned symbol, and specifies a symbol to write, a head action and the next state. For the teaching model, the tape is infinite in one direction. A formal infinite tape is a modelling assumption, not a physical component that can be built. A state with no outgoing transition is a halting state. A Universal Turing machine can interpret an encoded machine and its input, which makes the idea of a general programmable computer precise.

Our original machine increments a unary natural number. Represent n by n consecutive 1s followed by a blank _, with the head initially at the first cell and state scan. On reading 1, leave it unchanged, move one cell right and remain in scan. On reading _, write 1 and enter halt. No move is needed after halting; if a supplied notation requires every transition to include a movement, moving right into a blank before halt is an equivalent convention for the output. State the convention rather than mixing formats in a trace. The empty unary input represents zero.

For input 111_, the head visits positions 0,1,2,3. Each 1 transition preserves the existing block. At position 3 it replaces the blank with 1 and halts, yielding 1111. After k scanning steps, the first k cells are unchanged 1s and the head is at k; this invariant establishes that the machine reaches the original first blank and writes exactly one additional 1. There are n scans followed by one write/halt transition. The supplied Python simulator stores only the initially needed finite tape prefix; it is a trace aid for this fixed machine, not a complete Universal Turing machine.

Computable means that a general algorithm can produce the required result on the defined input domain. Some computable tasks can be too costly for available hardware; this is an efficiency limit. Non-computable means no algorithm solves all instances of the stated problem. The halting problem asks for a total procedure that decides whether any arbitrary encoded program eventually halts on a specified input. Such a procedure cannot exist. This does not imply that termination of every individual program is unknowable: we already proved termination for the prefix loop and triangular recurrence on their domains.

The diagonal contradiction explains the distinction, although this study topic includes the halting problem's description and significance rather than a proof. Suppose a correct total predictor H(P,x) existed. Construct D(P) that loops forever when H(P,P) predicts halting and halts when it predicts non-halting. Applying D to its own encoding makes either prediction wrong. Simulation for a fixed number of steps cannot repair this: failure to halt within the bound does not distinguish a slower halting computation from an infinite one. A practical timeout is a resource policy and can be useful, but its result must be “not finished within the limit”, not a fabricated proof of nontermination.

Reading the diagram: The numbered scan rows are successive configurations, starting before any transition, not a count of transitions already executed. The head visits cells 0,1,2,3 without changing the original three ones, then writes 1 over the first blank and halts at 3. Thus five displayed configurations represent four transitions. The extra drawn blank and ellipsis indicate the one-way infinite-tape model; the Python trace stores only a finite prefix. The blank-to-halt transition uses the explicit stay convention, not an unnoticed extra move.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def unary_increment(n):
"""Trace a one-way-tape TM: scan unary 1s then replace blank with 1."""
if type(n) is not int or n < 0:
raise ValueError('nonnegative integer required')
tape = ['1'] * n + ['_']
head = 0
trace = [('scan', head, ''.join(tape))]
while tape[head] == '1':
head += 1
trace.append(('scan', head, ''.join(tape)))
tape[head] = '1'
trace.append(('halt', head, ''.join(tape)))
return ''.join(tape), trace
```

Worked example: Trace unary_increment(3) and compare its termination claim with a timeout on arbitrary programs.

Start at state scan, head 0, tape 111_. After three 1 transitions the head is at 3 and the tape is unchanged.

The blank transition writes 1 and halts; the final finite displayed tape is 1111. The domain invariant and n−head progress justify termination for this machine.

A timeout on a different program establishes only that it did not complete within the selected resource bound; the unary proof cannot be transferred to arbitrary code.

Answer: Unary output represents 4. This particular computation terminates after four transitions.

Check your understanding: 1. What happens for unary zero? 2. Is a computable exponential-time task necessarily non-computable? 3. A checker runs programs for a million steps and labels unfinished ones “never halts”. Give a counterexample and a correct result vocabulary.

Answer: 1. The first cell is blank; one transition writes 1 and halts. 2. No. Computability concerns existence of a solving algorithm, while efficiency concerns resource growth. 3. A program that performs two million finite loop iterations before halting is a counterexample. Use “halted within bound” and “undetermined beyond bound”, plus distinct input/runtime-error outcomes where applicable.

Why: A halting state is part of the formal control, not a timeout condition. Unbounded tape is an abstraction. Undecidability of a universal termination checker is compatible with rigorous proofs for specific programs. An unfinished run is evidence about the selected bound, not proof of an infinite computation.