Turing machines and computable functions

Use a deterministic machine with a two-way infinite tape, a finite alphabet containing blank B and symbol 1, finitely many states, and one head. A nonhalting transition reads the current state and symbol, writes a symbol, moves left or right, and chooses a state. A configuration records the state, head position, and finite nonblank tape content. Our halt state has no outgoing rule. Other standard machine conventions can simulate this one and do not change which partial functions are computable.

Encode n by n consecutive ones starting at position zero, with the head at zero; zero is the blank tape. Output is the length of a contiguous block of ones in the halting configuration for the example below. This encoding must be stated before interpreting the machine as a numerical function. Merely counting states or watching one run does not determine what function a program computes on all inputs, nor whether every run halts.

Fix an effective enumeration of machine descriptions and a standard computable encoding of inputs and outputs. The notation phi sub e denotes the partial function computed by description e. Its value is defined exactly when the run halts with a valid output under the adopted convention. A function is total computable when one machine returns its value on every input. A partial computable function may diverge outside its domain; divergence is absence of an output, not an additional numerical value.

Unbounded minimization illustrates the difference. To find the least y whose square equals x, test y=0,1,2 and continue. It halts with three at input nine, but never halts at input two. A total algorithm deciding whether x is a square can instead stop once the square exceeds x and return a negative answer. The first procedure's intended output is a root, while the second decides a property; these are different specifications with different termination obligations.

One can mathematically prove equivalence between specific models, such as Turing machines, partial recursive functions, and suitable register machines, by explicit simulations in both directions. The Church–Turing thesis identifies the informal notion of an effective procedure with these formal notions. Because the informal side is not independently formalized, this identification is a thesis supported by many simulations, not the same kind of theorem as a simulation between two fully specified models.

Computability also differs from practical efficiency. A terminating program can take a vast number of steps or use enormous encodings, while an undecidable task has no correct total algorithm at all under the specification. Our unary machine has an exact linear step count, which supplies a genuine termination proof. Later diagonal arguments will concern arbitrary programs with unbounded configurations; a finite-state residue orbit cannot stand in for that whole class.