Universal Computing Device

A universal Turing machine simulates another Turing machine from a description of that machine and its input. The model has finite control and an unbounded read/write tape.

Computational universality concerns the functions a model can compute given sufficient resources. A real computer has finite memory and time; not every device or finite-state machine is universal.

A deterministic computation has one next step for a given state and input. Nondeterminism in computation theory describes branching choices in a model; it is not simply a random output.

The halting problem has no algorithm that works for all arbitrary program/input pairs. It is undecidable for Turing machines as well as for general-purpose programming systems; it is not an example of a problem that a Turing machine can decide but a digital computer cannot.

Related: lecture-05, abstraction.

Source

Original retained in wisconsin-legacy.