Abstract machine | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

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. A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former into the latter. They can be used for purely theoretical reasons as well as models for real-world computer systems. In the theory of computation, abstract machines are often used in thought experiments regarding computability or to analyse the complexity of algorithms. This use of abstract machines is fundamental to the field of computational complexity theory, such as finite state machines, Mealy machines, push-down automata, and Turing machines. Abstract machines are generally classified into two types, depending on the number of operations they are allowed to undertake at any one time: deterministic abstract machines and non-deterministic abstract machines. A deterministic abstract machine is a system in which a particular beginning state or condition always yields the same outputs. There is no randomness or variation in how inputs are transformed into outputs. In contrast, a non-deterministic abstract machine can provide various outputs for the same input on different executions. Unlike a deterministic algorithm, which gives the same result for the same input regardless of the number of iterations, a non-deterministic algorithm takes various paths to arrive to different outputs. Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly.

About this result

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.

Related concepts (45)

Related courses (5)

Related lectures (12)

State (computer science)

In information technology and computer science, a system is described as stateful if it is designed to remember preceding events or user interactions; the remembered information is called the state of the system. The set of states a system can occupy is known as its state space. In a discrete system, the state space is countable and often finite. The system's internal behaviour or interaction with its environment consists of separately occurring individual actions or events, such as accepting input or producing output, that may or may not cause the system to change its state.

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

Abstract machine

BIO-686(A): Scientific writing for biomedical articles (Fall)

The course is highly recommended for its excellent quality. Researchers will be apt to write a clear, well-structured article. We aim to make researchers aware of good writing and help them to face t

BIO-686(B): Scientific writing for biomedical articles (Spring)

The course is highly recommended for its excellent quality. Researchers will be apt to write a clear, well-structured article. We aim to make researchers aware of good writing and help them to face t

CS-173: Fundamentals of digital systems

Welcome to the introductory course in digital design and computer architecture. In this course, we will embark on a journey into the world of digital systems, exploring the fundamental principles and

Abstract Interpretation Idea CS-550: Formal verification

Covers abstract interpretation, fixpoints, control-flow graphs, and program state approximation.

Abstract Interpretation in Stainless CS-550: Formal verification

Explores abstract interpretation in Stainless, demonstrating its application in program verification and discussing future directions for the project.

Computer Architecture: Electronic Calculations with Transistors CS-119(d): Information, Computation, Communication

Covers electronic calculations with transistors, logical circuits, and processor capabilities.