P′′P′′ (P double prime) is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines. (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet , as follows: and are words in P′′. If and are words in P′′, then is a word in P′′. If is a word in P′′, then is a word in P′′. Only words derivable from the previous three rules are words in P′′. is the tape-alphabet of a Turing machine with left-infinite tape, being the blank symbol, equivalent to .
Elementary cellular automatonIn mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors. There is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation, and as such it is one of the simplest possible models of computation.
DatalogDatalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more. A Datalog program consists of facts, which are statements that are held to be true, and rules, which say how to deduce new facts from known facts.
BlooP and FlooPand () (Bounded loop and Free loop) are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book Gödel, Escher, Bach. BlooP is a non-Turing-complete programming language whose main control flow structure is a bounded loop (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express primitive recursive functions. FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing-complete language and can express all computable functions.
Stephen WolframStephen Wolfram (ˈwʊlfrəm ; born 29 August 1959) is a British-American computer scientist, physicist, and businessman. He is known for his work in computer science, mathematics, and theoretical physics. In 2012, he was named a fellow of the American Mathematical Society. He is currently an adjunct professor at the University of Illinois Department of Computer Science. As a businessman, he is the founder and CEO of the software company Wolfram Research where he works as chief designer of Mathematica and the Wolfram Alpha answer engine.
Meta-circular evaluatorIn computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta-circular evaluation is most prominent in the context of Lisp. A self-interpreter is a meta-circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously.
Random-access machineIn 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.
