BlooP and FlooP: Difference between revisions

Content deleted Content added

Inline

Revision as of 00:45, 29 August 2011

BLooP and FLooP are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book Gödel, Escher, Bach.^[1] 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.^[2]

FLooP is identical to BLooP except that it supports unbounded loops; it is a Turing-complete language and can express all computable functions. For example, it can express the Ackermann function, which (not being primitive recursive) cannot be written in BLooP.

BLooP and FLooP can be regarded as models of computation, and have sometimes been used in teaching computability.^[3]

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^[4]). 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 can be handled by interpreting the number in a cell in specific ways, that is, by Gödel numbering the possible structures.

Factorial function:

DEFINE PROCEDURE ''FACTORIAL'' [N]:
BLOCK 0: BEGIN
        OUTPUT ⇐ 1;
        CELL(0) ⇐ 1;
        LOOP N TIMES:
        BLOCK 1: BEGIN
                OUTPUT ⇐ OUTPUT × CELL(0);
                CELL(0) ⇐ CELL(0) + 1;
        BLOCK 1: END;
BLOCK 0: END.

Subtraction function (this is not a built-in operation):

DEFINE PROCEDURE ''MINUS'' [M,N]:
BLOCK 0: BEGIN
        IF M < N, THEN:
        QUIT BLOCK 0;
        OUTPUT ⇐ 0;
        LOOP AT MOST M + 1 TIMES:
        BLOCK 1: BEGIN
                IF OUTPUT + N = M, THEN:
                ABORT LOOP 1;
                OUTPUT ⇐ OUTPUT + 1;
        BLOCK 1: END;
BLOCK 0: END.

References

^ Douglas Hofstadter (1979), Gödel, Escher, Bach, Basic Books, Chapter XIII.
^ Stanford Encyclopedia of Philosophy: Computability and Complexity
^ David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, Lecture 27.
^ Hofstadter refers to these cells as a set of "auxiliary variables."

External links

This programming-language-related article is a stub. You can help Wikipedia by expanding it.

[1] Douglas Hofstadter (1979), Gödel, Escher, Bach, Basic Books, Chapter XIII.

[2] Stanford Encyclopedia of Philosophy: Computability and Complexity

[3] David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, Lecture 27.

[4] Hofstadter refers to these cells as a set of "auxiliary variables."

[1]

[2]

[3]

[4]

@@ Line 4: / Line 4: @@
 <!-- End of AfD message, feel free to edit beyond this point -->
-'''BLooP''' and '''FLooP''' are simple [[programming language]]s designed by [[Douglas Hofstadter]] to illustrate a point in his book ''[[Gödel, Escher, Bach]]''.<ref>[[Douglas Hofstadter]] (1979), ''[[Gödel, Escher, Bach]]'', Basic Books, Chapter XIII.</ref> BLooP is a [[Turing completeness|non-Turing-complete programming language]] whose only control flow structure is a bounded [[loop (computing)|loop]] (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express [[primitive recursive function]]s.<ref>[http://plato.stanford.edu/entries/computability/ Stanford Encyclopedia of Philosophy:  Computability and Complexity]</ref>
+'''BLooP''' and '''FLooP''' are simple [[programming language]]s designed by [[Douglas Hofstadter]] to illustrate a point in his book ''[[Gödel, Escher, Bach]]''.<ref>[[Douglas Hofstadter]] (1979), ''[[Gödel, Escher, Bach]]'', Basic Books, Chapter XIII.</ref> BLooP is a [[Turing completeness|non-Turing-complete programming language]] whose main control flow structure is a bounded [[loop (computing)|loop]] (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express [[primitive recursive function]]s.<ref>[http://plato.stanford.edu/entries/computability/ Stanford Encyclopedia of Philosophy:  Computability and Complexity]</ref>
 FLooP is identical to BLooP except that it supports unbounded loops; it is a Turing-complete language and can express all [[computable function]]s. For example, it can express the [[Ackermann function]], which (not being primitive recursive) cannot be written in BLooP.