Model of computation

Short description: Mathematical model describing how an output of a function is computed given an input

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.

## Contents

* 1 Models
* 1.1 Sequential models
* 1.2 Functional models
* 1.3 Concurrent models
* 2 Uses
* 3 See also
* 4 References
* 5 Further reading

## 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

1. ↑ "Models of Computation". https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.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

Computer science

Note: This template roughly follows the 2012 ACM Computing Classification System.

Hardware|

* Printed circuit board
* Peripheral
* Integrated circuit
* Very Large Scale Integration
* Systems on Chip (SoCs)
* Energy consumption (Green computing)
* Electronic design automation
* Hardware acceleration

Computer systems
organization|

* Computer architecture
* Embedded system
* Real-time computing
* Dependability

Networks|

* Network architecture
* Network protocol
* Network components
* Network scheduler
* Network performance evaluation
* Network service

Software organization|

* Interpreter
* Middleware
* Virtual machine
* Operating system
* Software quality

Software notations
and tools|

* Programming paradigm
* Programming language
* Compiler
* Domain-specific language
* Modeling language
* Software framework
* Integrated development environment
* Software configuration management
* Software library
* Software repository

Software development|

* Software development process
* Requirements analysis
* Software design
* Software construction
* Software deployment
* Software maintenance
* Programming team
* Open-source model

Theory of computation|

* Model of computation
* Formal language
* Automata theory
* Computational complexity theory
* Logic
* Semantics

Algorithms|

* Algorithm design
* Analysis of algorithms
* Algorithmic efficiency
* Randomized algorithm
* Computational geometry

Mathematics
of computing|

* Discrete mathematics
* Probability
* Statistics
* Mathematical software
* Information theory
* Mathematical analysis
* Numerical analysis

Information
systems|

* 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

Security|

* Cryptography
* Formal methods
* Security services
* Intrusion detection system
* Hardware security
* Network security
* Information security
* Application security

Human–computer
interaction|

* Interaction design
* Social computing
* Ubiquitous computing
* Visualization
* Accessibility

Concurrency|

* Concurrent computing
* Parallel computing
* Distributed computing
* Multithreading
* Multiprocessing

Artificial
intelligence|

* Natural language processing
* Knowledge representation and reasoning
* Computer vision
* Automated planning and scheduling
* Search methodology
* Control method
* Philosophy of artificial intelligence
* Distributed artificial intelligence

Machine learning|

* Supervised learning
* Unsupervised learning
* Reinforcement learning
* Multi-task learning
* Cross-validation

Graphics|

* Animation
* Rendering
* Image manipulation
* Graphics processing unit
* Mixed reality
* Virtual reality
* Image compression
* Solid modeling

Applied
computing|

* E-commerce
* Enterprise software
* Computational mathematics
* Computational physics
* Computational chemistry
* Computational biology
* Computational social science
* Computational engineering
* Computational healthcare
* Digital art
* Electronic publishing
* Cyberwarfare
* Electronic voting
* Video games
* Word processing
* Operations research
* Educational technology
* Document management

* Book
* Category
* Outline
* WikiProject
* Commons

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Model of computation. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Model_of_computation&oldid=2356962"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template