13-11-2012, 12:16 PM
Numeric Functions
recursive functions.docx (Size: 26.84 KB / Downloads: 22)
Converting predicates to numeric functions
In some settings it is natural to consider primitive recursive functions that take as inputs tuples that mix numbers with truth values { t= true, f=false }, or that produce truth values as outputs (see Kleene [1952 pp. 226–227]). This can be accomplished by identifying the truth values with numbers in any fixed manner. For example, it is common to identify the truth value t with the number 1 and the truth value f with the number 0. Once this identification has been made, the characteristic function of a set A, which literally returns 1 or 0, can be viewed as a predicate that tells whether a number is in the set A. Such an identification of predicates with numeric functions will be assumed for the remainder of this article.
Computer language definition
An example of a primitive recursive programming language is one that contains basic arithmetic operators (e.g. + and -, or ADD and SUBTRACT), conditionals and comparison (IF-THEN, EQUALS, LESS-THAN), and bounded loops, such as the basic for loop, where there is a known or calculable upper bound to all loops (FOR i FROM 1 to n). No control structures of greater generality, such as while loops or IF-THEN plus GOTO, are admitted in a primitive recursive language. Douglas Hofstadter's Bloop in Gödel, Escher, Bach is one such. Adding unbounded loops (WHILE, GOTO) makes the language partially recursive, or Turing-complete; Floop is such, as are almost all real-world computer languages.
Arbitrary computer programs, or Turing machines, cannot in general be analyzed to see if they halt or not (the halting problem). However, all primitive recursive functions halt. This is not a contradiction; primitive recursive programs are a non-arbitrary subset of all possible programs, constructed specifically to be analyzable.
Subtraction
Because primitive recursive functions use natural numbers rather than integers, and the natural numbers are not closed under subtraction, a limited subtraction function is studied in this context. This limited subtraction function sub(a,b) returns if this is nonnegative and returns 0 otherwise.