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. 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 of computation can be classified into three categories: sequential models, functional models, and concurrent 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 include:
Abstract rewriting systems
Combinatory logic
General recursive functions
Lambda calculus
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; 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.
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.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator.
In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. Like the counter machine, The RAM has its instructions in the finite-state portion of the machine (the so-called Harvard architecture). The RAM's equivalent of the universal Turing machine with its program in the registers as well as its data is called the random-access stored-program machine or RASP.
In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a mathematical function in that it receives inputs and produces outputs based on predefined rules. Abstract machines vary from literal machines in that they are expected to perform correctly and independently of hardware. Abstract machines are "machines" because they allow step-by-step execution of programmes; they are "abstract" because they ignore many aspects of actual (hardware) machines.
This course explains the mathematical and computational models that are used in the field of theoretical neuroscience to analyze the collective dynamics of thousands of interacting neurons.
This course explains the mathematical and computational models that are used in the field of theoretical neuroscience to analyze the collective dynamics of thousands of interacting neurons.
Covers the concept of quantum computation delegation and the relationship between MIP and RE, addressing common FAQs and discussing helpful materials and interactions with quantum devices.
By Meenakshi Khosla explores data-driven modeling in large-scale naturalistic neuroscience, focusing on brain activity representation and computational models.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
We will study the emergence of life-like phenomena, such as locomotion, resilience,, reproduction, and evolution in mathematical models, in particular in discrete and continuous cellular automata, dev
This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica
Though models describing the operating mechanism of organic electrochemical transistors (OECTs) have been developed, these models are unable to accurately reproduce OECT electrical characteristics. He
This article considers solving an overdetermined system of linear equations in peer-to-peer multiagent networks. The network is assumed to be synchronous and strongly connected. Each agent has a set o
Towards the end of the second trimester of gestation, a human fetus is able to register environmental sounds. This in utero auditory experience is characterized by comprising strongly low-pass-filtere