Model of computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized.[1] The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.
Models
Models of computation can be classified into three categories: sequential models, functional models, and concurrent models.
Sequential models
Sequential models include:
- Finite state machines
- Post machines (Post–Turing machines and tag machines).
- Pushdown automata
- Register machines
- Random-access machines
- Turing machines
- Decision tree model
Functional models
Functional models include:
- Abstract rewriting systems
- Combinatory logic
- General recursive functions
- Lambda calculus
Concurrent models
Concurrent models include:
- Actor model
- Cellular automaton
- Interaction nets
- Kahn process networks
- Logic gates and digital circuits
- Petri nets
- Synchronous Data Flow
Some of these models have both deterministic and nondeterministic variants. Nondeterministic models are not useful for practical computation;[citation needed] they are used in the study of computational complexity of algorithms.
Models differ in their expressive power; for example, each function that can be computed by a Finite state machine can also be computed by a Turing machine, but not vice versa.
Uses
In the field of runtime analysis of algorithms, it is common to specify a computational model in terms of primitive operations allowed which have unit cost, or simply unit-cost operations. A commonly used example is the random-access machine, which has unit cost for read and write access to all of its memory cells. In this respect, it differs from the above-mentioned Turing machine model.
See also
- Stack machine (0-operand machine)
- Accumulator machine (1-operand machine)
- Register machine (2,3,... operand machine)
- Random-access machine
- Abstract machine
- Cell-probe model
- Robertson–Webb query model
- Chomsky hierarchy
- Turing completeness
References
- ^ "Models of Computation" (PDF).
Further reading
- Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
- Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Addison-Wesley. ISBN 978-0201895391.
- v
- t
- e
- Interpreter
- Middleware
- Virtual machine
- Operating system
- Software quality
- Model of computation
- Formal language
- Automata theory
- Computability theory
- Computational complexity theory
- Logic
- Semantics
- Database management system
- Information storage systems
- Enterprise information system
- Social information systems
- Geographic information system
- Decision support system
- Process control system
- Multimedia information system
- Data mining
- Digital library
- Computing platform
- Digital marketing
- World Wide Web
- Information retrieval
- Interaction design
- Social computing
- Ubiquitous computing
- Visualization
- Accessibility
- Quantum Computing
- E-commerce
- Enterprise software
- Computational mathematics
- Computational physics
- Computational chemistry
- Computational biology
- Computational social science
- Computational engineering
- Differentiable computing
- Computational healthcare
- Digital art
- Electronic publishing
- Cyberwarfare
- Electronic voting
- Video games
- Word processing
- Operations research
- Educational technology
- Document management
- Category
- Outline
- WikiProject
- Commons