Abstract machines and formal systems that define what computation is. The Turing machine, the lambda calculus and the actor model each give a complete account of computing in their own terms, while finite state machines, deterministic and nondeterministic finite automata and pushdown automata are simpler machines that recognise progressively richer families of languages, together with the context-free grammars that describe the structure of many programming languages.
Browse By
Models of Computation and Automata
Filter Results8 entries
Sources
Wikipedia: Turing machine
WikipediaHas Member: Turing Machine, LeadQuote, Has Member: Turing Machine, Lead
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.
Wikipedia: Finite-state machine
Wikimedia FoundationHas Member: Finite State Machine, LeadQuote, Has Member: Finite State Machine, Lead
In theoretical computer science, a finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.
Deterministic finite automaton - Wikipedia
Has Member: Deterministic Finite Automaton, LeadQuote, Has Member: Deterministic Finite Automaton, Lead
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA), also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA), is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string.
Nondeterministic finite automaton - Wikipedia
Has Member: Nondeterministic Finite Automaton, LeadQuote, Has Member: Nondeterministic Finite Automaton, Lead
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition.
Pushdown automaton - Wikipedia
Has Member: Pushdown Automaton, LeadQuote, Has Member: Pushdown Automaton, Lead
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
Context-free grammar - Wikipedia
Has Member: Context-Free Grammar, LeadQuote, Has Member: Context-Free Grammar, Lead
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context.
Lambda calculus - Wikipedia
Has Member: Lambda Calculus, LeadQuote, Has Member: Lambda Calculus, Lead
In mathematical logic, the lambda calculus (also written as λ-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution.
Actor model - Wikipedia
Has Member: Actor Model, LeadQuote, Has Member: Actor Model, Lead
The actor model in computer science is a mathematical model of concurrent computation that treats an actor as the basic building block of concurrent computation.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.