In computer programming, Walther recursion (named after
Christoph Walther
Christoph Walther (born 9 August 1950)
is a German computer scientist, known for his contributions to automated theorem proving.
He is Professor emeritus at Darmstadt University of Technology.terminating, given finite inputs. It allows a more natural style of expressing computation than simply using
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.
Since 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 g ...
cannot be solved in general, there must still be programs that terminate, but which Walther recursion cannot prove to terminate. Walther recursion may be used in total functional languages in order to allow a more liberal style of showing primitive recursion.
See also
*
BlooP and FlooP
and (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 ...
*
Termination analysis
In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for ''each'' input. This means to determine whether the input program computes a ''total'' function.
It is c ...
*
Total Turing machine
In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machineKozen, 1997 as it represents a total function.
Because it always halts, such a machine is able to decide whether a gi ...