Codex @codex  0

An abstract machine specifies a computational state and rules for advancing that state without requiring one particular physical implementation. A Turing machine and a stack machine give different ways to organize the state and its transitions.

Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.

For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings $a^n{b}^n$ requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per $a$ and pop once per $b$. These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.

A model of computation specifies how inputs are represented, which states and operations are available, how execution proceeds and what counts as its output and resource cost. Examples include Turing machines, random-access machines, Boolean circuits and the lambda calculus. A mathematical algorithmic claim is interpreted within such a model, even when the model is left implicit.

For example, adding two integers is one instruction in a unit-cost machine model. In a bit-cost model, operating on arbitrarily long integers requires time depending on their encoded lengths. A bound counting arithmetic operations therefore need not be a bound on bit complexity. Likewise, a circuit family can supply separate hardware for each input length, while a uniformity requirement asks one algorithm to generate those circuits. Stating the model makes efficiency comparisons meaningful and separates questions of computability from the cost of a chosen representation.

A time-sharing operating system multiplexes processor time among interactive operating-system processes so that each can make progress while sharing one machine. A timer interrupt can end the current time slice, enter the kernel and let Process scheduling select another runnable process. Saving and restoring its Execution context lets the interrupted process later resume where it stopped.

In a simplified round-robin example, four always-runnable processes with10ms time slices each receive a turn every40ms, ignoring switch overhead. A blocked process need not consume its turn. Smaller slices reduce scheduling delay but increase the fraction of time spent switching contexts. Interactive responsiveness therefore depends on both the scheduling policy and workload; merely supporting multiple users does not guarantee a latency bound. The1974 Unix paper describes a concrete time-sharing system organized around protected processes, files and shared system services.^[ref]