and (Bounded loop and Free loop) are simple

programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

s designed by

Douglas Hofstadter Douglas Richard Hofstadter (born February 15, 1945) is an American scholar of cognitive science, physics, and comparative literature whose research includes concepts such as the sense of self in relation to the external world, consciousness, a ...

to illustrate a point in his book ''

Gödel, Escher, Bach ''Gödel, Escher, Bach: an Eternal Golden Braid'', also known as ''GEB'', is a 1979 book by Douglas Hofstadter. By exploring common themes in the lives and works of logician Kurt Gödel, artist M. C. Escher, and composer Johann Sebastian Bach, t ...

''. BlooP is a non-Turing-complete programming language whose main control flow structure is a bounded

loop Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...

(i.e.

recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...

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 can be determined ...

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. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...

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 computable function that is not primitive recursive. All primitive recursive functions are total ...

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

mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...

,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, 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 forever. Alan Turing proved in 1936 that a ...

: 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 Assignment, assign or The Assignment may refer to: * Homework * Sex assignment * The process of sending National Basketball Association players to its development league; see Computing * Assignment (computer science), a type of modification to ...

), + (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 In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of h ...

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

: that is, on previously defined numerical functions PUSH, POP, and TOP satisfying

PUSH , S 





The comma  is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the  baseline o ...
> 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