CSE 410/510, PHI 498, Spring 2004 http://www.cse.buffalo.edu/∼rapaport/510.html

Structured Programming and Recursive Functions

Notes by William J. Rapaport (based on lectures by John Case)

Department of Computer Science & Engineering, Department of Philosophy, and Center for Cognitive Science

State University of New York at Buffalo, Buffalo, NY 14260-2000

rapaport@cse.buffalo.edu, http://www.cse.buffalo.edu/∼rapaport

Last Update: 2 February 2004 Note: NEW or UPDATED material is highlighted

1. Structured Programming:

(a) Classification of structured programs:

i. Basic programs: A. the empty program =def start halt. B. the 1-operation program =def start F halt.

(where ‘F’ is some primitive operation, e.g., an assignment statement). ii. Program constructors:

Let π, π′be programs with 1 halt-operation each. Then new programs can be constructed by: A. linear concatenation =def start π; π′halt. B. conditional branching =def

start

if P then π else π′

halt. (where ‘P’ is a Boolean test, i.e., a predicate; e.g., “x > 0”).

C. count looping (or “for-loop”, or “bounded loop”):

start

while y > 0 do

start π; y ← y − 1

halt halt.

D. while-looping (or “free” loop):

start

while P do π halt.

(b) Categories of structured programs (based on above classifications):

i. π is a count-program (or a “for-program”, or a “Bounded LOOP program”) =def A. π is a basic program, OR B. π is constructed from count-programs by:

• linear concatenation, OR

• conditional branching, OR

• count looping C. Nothing else is a count-program.

ii. π is a while-program (or a “Free LOOP program”) =def A. π is a basic program, OR B. π is constructed from while-programs by:

• linear concatenation, OR

• conditional branching, OR

• count-looping, OR

• while-looping C. Nothing else is a while-program.

2. Recursive Functions

(a) Classification of functions:

i. Basic functions:

A. successor: S(x) = x + 1 B. predecessor: P(x) = x ˙−1

(where a ˙−b =def \{ \begin{matrix}a − b, & if a ≥ b \\ 0, & otherwise \end{matrix} )

C. projection: P_{k}^{j}(x_{1},...,x_{j},...,x_{k}) = x_{j} ii. Function constructors:

A. f is defined from g,h_{1},...,h_{m} by generalized composition =def f(x_{1},...,x_{k}) = g(h_{1}(x_{1},...,x_{k}),...,h_{m}(x_{1},...,x_{k}))

• Cf. linear concatenation (e.g., first compute h; then compute g) B. f is defined from g,h,i by conditional definition =def

f(x_{1},...,x_{k}) = \{ \begin{matrix}g(x_{1},...,x_{k}), & if x_{i} = 0 \\ h(x_{1},...,x_{k}), & if x_{i} > 0 \end{matrix}

• Cf. conditional branch C. f is defined from g,h_{1},...,h_{k},i by while-recursion =def

f(x_{1},...,x_{k}) = \{ \begin{matrix}g(x_{1},...,x_{k}), & if x_{i} = 0 \\ f(h_{1}(x_{1},...,x_{k}),...,h_{k}(x_{1},...,x_{k})), & if x_{i} > 0 \end{matrix}

• Cf. while-loop (e.g., while x_{i} > 0, compute f)

(b) Categories of functions:

i. f is a while-recursive function =def A. f is a basic function, OR B. f is defined from while-recursive functions by:

• generalized composition, OR

• conditional definition, OR

• while-recursion C. Nothing else is while-recursive.

ii. A. f is defined from g,h by primitive recursion =def

f(x_{1},...,x_{k},y) = \{ \begin{matrix}g(x_{1},...,x_{k}), & if y = 0 \\ h(x_{1},...,x_{k},f(x_{1},...,x_{k},y − 1)), & if y > 0 \end{matrix}

• Cf. count-loop (e.g., while y > 0, decrement y & compute f) B. f is a primitive-recursive function =def

• f is a basic function, OR

• f is defined from primitive-recursive functions by:

– generalized composition, OR

– primitive recursion

• Nothing else is primitive-recursive. iii. A. f is defined from h by the μ-operator [pronounced: “mu”-operator] =def

f(x_{1},...,x_{k}) = μz[h(x_{1},...,x_{k},z) = 0], where:

μz[h(x_{1},...,x_{k},z) = 0] =def \{ \begin{matrix}min\{z: \{ \begin{matrix}h(x_{1},...,x_{k},z) = 0 \\ and \\ (∀y < z)[h(x_{1},...,x_{k},y) has a value] \end{matrix} \}, & if such z exists \\ undefined, & if no such z exists \end{matrix}

B. f is a partial-recursive function =def • f is a basic function, OR

• f is defined from partial-recursive functions by:

– generalized composition, OR

– primitive recursion, OR

– the μ-operator

• Nothing else is partial-recursive. C. f is a recursive function =def

• f is partial-recursive, AND

• f is a total function (i.e., defined ∀ elements of its domain)

3. The Connections:

f is primitive-recursive ⇔ f is count-program–computable
⇓  ⇓
f is partial-recursive ⇔ f is while-program–computable
⇕  ⇕

f is Turing-machine–computable

⇕ f is λ-definable, etc.

file:510/strdprogg.pdf  \begin{matrix}c \\ ◯ \end{matrix}2004, William J. Rapaport  rapaport@cse.buffalo.edu