Editing BlooP and FlooP (section)

{{Short description|Simple programming languages}}
{{abbr|'''BlooP'''|Bounded loop}} and {{abbr|'''FlooP'''|Free loop}} ('''Bounded loop''' and '''Free loop''') 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|Turing-incomplete programming language]] whose main control flow structure is a bounded [[loop (computing)|loop]] (i.e. [[Recursion (computer science)|recursion]] is not permitted{{citation needed|date=October 2023}}). 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. Borrowing from standard terminology in [[mathematical logic]],<ref name="Hofstadter424">Hofstadter (1979), p. 424.</ref><ref>Thomas Forster (2003), ''[https://books.google.com/books?id=mVeTuaRwWssC&pg=PA130 Logic, Induction and Sets]'', Cambridge University Press, p. 130.</ref> Hofstadter calls FlooP's unbounded loops MU-loops. Like all Turing-complete programming languages, FlooP suffers from the [[halting problem]]: programs might not terminate, and it is not possible, in general, to decide which programs do.

BlooP and FlooP can be regarded as [[model of computation|models of computation]], and have sometimes been used in teaching computability.<ref>David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, [http://www.cs.umass.edu/~barring/cs601f04/lecture/27.pdf Lecture 27].</ref>