NationMaster - Encyclopedia: Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. Abstraction of computing processes is used in both the computer science and computer engineering disciplines and usually assumes discrete time paradigm. A Lego RCX Computer is an example of an embedded computer used to control mechanical devices. ... In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... The examples and perspective in this article or section may not represent a worldwide view. ... Discrete time is non-continuous time. ... Since the late 1960s, the word paradigm (IPA: ) has referred to a thought pattern in any scientific discipline or other epistemological context. ...

In the theory of computation, abstract machines are often used in thought experiments regarding computability or to analyze the complexity of algorithms (see computational complexity theory). 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. The best-known example is the Turing machine. The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. ... In philosophy, physics, and other fields, a thought experiment (from the German Gedankenexperiment) is an attempt to solve a problem using the power of human imagination. ... In computer science, computational complexity theory is the branch of the theory of computation that studies the complexity, or efficiency, of solving computational problems. ... An artistic representation of a Turing Machine . ...

More complex definitions create abstract machines with full instruction sets, registers and models of memory. One popular model more similar to real modern machines is the RAM model, which allows random access to indexed memory locations. As the performance difference between different levels of cache memory grows, cache-sensitive models such as the external-memory model and cache-oblivious model are growing in importance. An instruction set, or instruction set architecture (ISA), describes the aspects of a computer architecture visible to a programmer, including the native datatypes, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O (if any). ... In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to commonly used values—typically, the values being in the midst of a calculation at a given point in time. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... In computer science, random access machine (RAM) is an abstract machine very similar to the Register machine but with the added capability of indirect addressing of its registers. ... In computing, the cache-oblivious model is an abstract machine (i. ...

An abstract machine can also refer to a microprocessor design which has yet to be (or is not intended to be) implemented as hardware. An abstract machine implemented as a software simulation, or for which an interpreter exists, is called a virtual machine. A microprocessor (sometimes abbreviated ÂµP) is a digital electronic component with transistors on a single semiconductor integrated circuit (IC). ... An interpreter is a computer program that executes other programs. ... In general terms, a virtual machine in computer science is software that creates a virtualized environment between the computer platform and the end user in which the end user can operate software. ...

Through the use of abstract machines it is possible to compute the amount of resources (time, memory, etc.) necessary to perform a particular operation without having to construct an actual system to do it.

Organization within Wikipedia: Articles concerning Turing-equivalent sequential abstract machine models

An approach is to take a somewhat formal taxonomic approach to classify the Turing equivalent abstract machines. This taxonomy does not include finite automata: Turing equivalence may refer to: Turing equivalence (theory of computation) Turing equivalence (recursion theory) Category: ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ...

Family: Turing-equivalent (TE) abstract machine:

Subfamilies:

Subfamily (1) Sequential TE abstract machine

Subfamily (2) Parallel TE abstract machine

Subfamily (1)-- Sequential TE abstract machine model: There are two classes (genera) of Sequential TE abstract machine models currently in use (cf van Emde Boas, for example):

Genus (1.1) Tape-based Turing machine model

Genus (1.2) Register-based register machine

Genus (1.1) -- Tape-based Turing machine model: This includes the following "species": An artistic representation of a Turing Machine . ... In theoretical computer science a register machine is an abstract machine used to study decision problems, similar to how a Turing machine is used. ...

{ single tape, Multi-tape Turing machine, deterministic Turing machine, Non-deterministic Turing machine, Wang B-machine, Post-Turing machine, Oracle machine, Universal Turing machine }

Genus (1.2)-- The register machine model: This includes (at least) the following four "species" (others are mentioned by van Emde Boas): The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state... As proposed by Hao Wang (1954, 1957): his basic machine B is an extremely simple computational model equivalent to the Turing machine. ... A Post-Turing Machine is a simple model of computation that has been shown to be equivalent in computational power to a Turing Machine. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...

{ (1.2.1) Counter machine, (1.2.2) Random access machine RAM, (1.2.3) Random access stored program machine RASP, (1.2.4) Pointer machine }

Species (1.2.1) -- Counter machine model:

{ abacus machine, Lambek machine, Melzak model, Minsky machine, Shepherdson-Sturgis machine, program machine, etc. }

Species (1.2.2) -- Random access machine (RAM) model:

{ any counter-machine model with additional indirect addressing, but with instructions in the state machine in the Harvard architecture; any model with an "accumulator" with additional indirect addressing but instructions in the state machine in the Harvard architecture }

Species (1.2.3) -- Random access stored program machine (RASP) model includes

{ any RAM with program stored in the registers similar to the Universal Turing machine i.e. in the von Neumann architecture }

Species (1.2.4)-- Pointer machine model includes the following:

= { Schönhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton }

In theoretical computer science a register machine is an generic class of abstract machine used to study decision problems, similar to how a Turing machine is used. ... Definition: A model of computation whose memory consists of an unbounded sequence of registers, each of which may hold an integer. ... In theoretical computer science the Random Access Stored Program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory. ... In theoretical computer science a pointer machine is an atomistic abstract computational machine model akin to the Random access machine. ... The term Harvard architecture originally referred to computer architectures that used physically separate storage and signal pathways for their instructions and data (in contrast to the von Neumann architecture). ... The term Harvard architecture originally referred to computer architectures that used physically separate storage and signal pathways for their instructions and data (in contrast to the von Neumann architecture). ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... Design of the Von Neumann machine A von Neumann architecture is a computer design model that uses a single storage structure to hold both instructions and data. ...

Other abstract machines

ABC is an imperative general-purpose programming language and programming environment from CWI, Netherlands. ... Abstract Machine Notation (AMN) is a programming language for specifying abstract machines in the B-Method, based on the mathematical theory of Generalised Substitutions. ... ALF is a programming language which combines functional and logic programming techniques. ... CAML (Categorical Abstract Machine Language) is a version of ML developed by G. Huet, G. Cousineau, AscÃ¡nder SuÃ¡rez, Pierre Weis, Michel Mauny and others from both INRIA and ENS. Implemented in Lisp, it was nicknamed Heavy CAML because of its memory and CPU requirements relative to its successor... In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V â†’ w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... SDL (short for Specification and Description Language) is a specification language targeted at the unambiguous specification and description of the behaviour of reactive and distributed systems. ... In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set [War83]. This design became known as the Warren Abstract Machine (WAM) and has become the de facto standard target for Prolog compilers. ... MMIX is a 64-bit RISC virtual machine designed by Donald Knuth, with significant contributions by John Hennessy (who designed the MIPS chip) and Dick Sites (who was the architect of the Alpha chip). ... The abstract machine TDF (originally the Ten15 Distribution Format, but more recently redefined as the TenDRA Distribution Format) evolved at the Royal Signals and Radar Establishment in the UK as a successor to Ten15. ...

Organization within Wikipedia: Articles concerning Turing-equivalent sequential abstract machine models var ACE_AR = {Site: '756743', Size: '300250'};

Other abstract machines

See also

Organization within Wikipedia: Articles concerning Turing-equivalent sequential abstract machine models