and (Bounded loop and Free loop) are simple

programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...

s designed by

Douglas Hofstadter Douglas Richard Hofstadter (born 15 February 1945) is an American cognitive and computer scientist whose research includes concepts such as the sense of self in relation to the external world, consciousness, analogy-making, Strange loop, strange ...

to illustrate a point in his book ''

Gödel, Escher, Bach ''Gödel, Escher, Bach: an Eternal Golden Braid'' (abbreviated as ''GEB'') is a 1979 nonfiction book by American cognitive scientist Douglas Hofstadter. By exploring common themes in the lives and works of logician Kurt Gödel, artist M. C. Esc ...

''. BlooP is a Turing-incomplete programming language whose main control flow structure is a bounded loop (i.e.

recursion Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...

is not permitted). All programs in the language must terminate, and this language can only express

primitive recursive function In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...

s. FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing-complete language and can express all

computable function Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...

s. For example, it can express the

Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...

, which (not being primitive recursive) cannot be written in BlooP. Borrowing from standard terminology in

mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

,Hofstadter (1979), p. 424. Hofstadter calls FlooP's unbounded loops MU-loops. Like all Turing-complete programming languages, FlooP suffers from the

halting problem In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...

: programs might not terminate, and it is not possible, in general, to decide which programs do. BlooP and FlooP can be regarded as

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

, and have sometimes been used in teaching computability.

BlooP examples

The only variables are OUTPUT (the return value of the procedure) and CELL(''i'') (an unbounded sequence of natural-number variables, indexed by constants, as in the Unlimited Register Machine). The only operators are ⇐ ( assignment), + (addition), × (multiplication), < (less-than), > (greater-than) and = (equals). Each program uses only a finite number of cells, but the numbers in the cells can be arbitrarily large. Data structures such as lists or stacks can be handled by interpreting the number in a cell in specific ways, that is, by Gödel numbering the possible structures. Control flow constructs include bounded loops, conditional statements, ABORT jumps out of loops, and QUIT jumps out of blocks. BlooP does not permit recursion, unrestricted jumps, or anything else that would have the same effect as the unbounded loops of FlooP. Named procedures can be defined, but these can call only previously defined procedures.Hofstadter (1979), p. 413.

Factorial function

Subtraction function

This is not a built-in operation and (being defined on natural numbers) never gives a negative result (e.g. 2 − 3 := 0). Note that OUTPUT starts at 0, like all the CELLs, and therefore requires no initialization.

FlooP example

The example below, which implements the

, relies on simulating a stack using Gödel numbering: that is, on previously defined numerical functions PUSH, POP, and TOP satisfying PUSH , S> 0, TOP USH [N, S = N, and POP USH [N, S = S. Since an unbounded MU-LOOP is used, this is not a legal BlooP program. The QUIT BLOCK instructions in this case jump to the end of the block and repeat the loop, unlike the ABORT, which exits the loop.

References

External links