Automata Theory

Automata theory studies idealized machines with inputs, outputs and limited operations that run in discrete time. There are various classes of such machines in automata theory. The combinational logic machines have outputs that only depend on inputs. The finite state machines have outputs that only depend on inputs and internal states. The pushdown automatons have outputs that only depend on inputs, internal states, and, a stack. The Turing machines have outputs that only depend on inputs, internal states, and, a tape. Many idealized machines are equivalent to Turing machines including random access machines and lambda calculus functions.