Lec 21: Encodings & Extended Recursion Schemes - CSCI 381 - Goldberg

Administrative — Upcoming Schedule

Same as that of Lecture 20

New Inbox Policy

Log into Outlook via @login.cuny.edu (not @qmail.cuny.edu) to receive emailed notes — Qmail is returning errors.

Encodings

In previous classes we assumed that primitive recursion is based on induction and as such, just as simple induction has one base case and access to one previous level’s output, so too recursion. The question was asked how does one deal with a function such as Fibonacci:

$$\text{Fib}(0) = 0, \quad \text{Fib}(1) = 1, \quad \text{Fib}(n+1) = \text{Fib}(n) + \text{Fib}(n-1)$$

Davis realized that the manner to prove that Fibonacci (and any recurrence relation) can be consistent with the formal definition of primitive recursion, is to encode all the previous levels’ outputs into a single number and then formulate a primitive recursive recursion based on that one number.

Godel (with others) suggested three genres of mathematical encodings:

a) Pairing Function based on Odd/Even and Exponentiation

A pairing function encodes two numbers as one single number. This encoding is “lossless”, which guarantees us that we can retrieve the original data values without error. As opposed to “lossy” which is used by JPEG to encode images and compresses the data in a manner that cannot guarantee the retrieval of the original exact data. The reason that this approach is acceptable for imaging is that psychological studies have shown that the brain imaging system is not as discerning for each dot of color (unless you make a special effort to do so) but is rather interested in explaining away the image in the simplest possible manner. The theory however is concerned with lossless encoding (related to compression, but the distinction being that the theoreticians would accept an encoding that expands the data to a longer amount of data and does not demand per se the compression of the data). The theoreticians are only interested in how many numbers: 1 vs. 2.

Consider two numbers $X$ and $Y$ that will be encoded by the pairing function into one number $Z$:

$$Z_g = \langle X, Y \rangle = 2^X \cdot (2Y + 1)$$

For example, $\langle 0, 0 \rangle = 2^0 \cdot (2 \cdot 0 + 1) = 1 \cdot 1 = 1$.

The $2^X$ factor extracts all of the “evenness” and what necessarily remains is an odd number, hence $2Y+1$. So, using the even/odd dichotomy the pairing function was born. Since computer theory ultimately means to encode storage of memory (cf. the definition of snapshot $(i, \sigma)$ where $i$ indicates which line of a program is about to be executed and $\sigma$ is an encoding of the storage of variables and their values; originally on a Turing tape, but eventually in RAM), every configuration of memory has to be explained as to its encoding and has to be lossless (i.e., encode and decode totally).

The problem is that the pairing function is always greater than zero, and hence positive, so that the encoding that results in the value zero cannot be decoded. In order to ensure that the encoding and decoding process are total functions, many of the encodings suggested in the theory literature had to subtract a constant from the encoding formula to guarantee that the value zero is covered. Here, we have:

$$Z' = \langle X, Y \rangle - 1, \qquad \text{or equivalently} \qquad Z' + 1 = \langle X, Y \rangle$$

Example: $X = 3$, $Y = 0$

$\langle 3, 0 \rangle = 2^3 \cdot (2 \cdot 0 + 1) = 8$

• $Z_g = 8$ (Godel)
• $Z_d = 7$ (Davis, $Z_g - 1$)

	$\langle 0, 0 \rangle$
Godel: $Z_g$	$1$
Davis: $Z_d$	$0$

Now, the revised pairing function allows for $X = Y = 0$ and as well $Z' = 0$. $Z' = 0$ corresponds to the initial memory configuration where the memory has all zeros: $Z' = 0 \Rightarrow \langle X, Y \rangle = 1$ and $1 - 1 = 0$. That can only occur when $X = Y = 0$.

b) General Godel Encoding based on Prime Number Factorization

$$P_g = [14, 1, 3, 2] = 2^{14} \cdot 3^1 \cdot 5^3 \cdot 7^2$$

Note: This example uses four data values, but the encoding works for any number of values.

Prime	Exponent	Contribution
$p_1 = 2$	$14$	$2^{14} = 16384$
$p_2 = 3$	$1$	$3^1 = 3$
$p_3 = 5$	$3$	$5^3 = 125$
$p_4 = 7$	$2$	$7^2 = 49$
Product		$301{,}056{,}000$

 

$P_d = P_g - 1$

Since computer theory wants a bijective mapping from $\mathbb{N} \to \mathbb{N}$ and $\mathbb{N}$ starts with $0$, the above formula has to be adjusted by $-1$. Multiplying primes to nonnegative integers can only generate $1$ and above, not $0$:

$$[0, 0, 0, 0] = 2^0 \cdot 3^0 \cdot 5^0 \cdot 7^0 = 1$$

The obvious problem with this is that it is ambiguous because any sequence of zeroes will yield the same value:

$$P_g = [0, 0, 0, 0, \ldots, 0] = 1 \qquad \Rightarrow \qquad P_d = 0$$

So how do you know how many zeroes are encoded? They then had to LIMIT the number of ending zeroes as follows: only $[0]$ will be allowed to encode zeroes alone, and if the encoding has nonzero elements, the last element of the sequence cannot be zero.

$$[14, 1, 3, 2] = [14, 1, 3, 2, 0, 0, 0, \ldots, 0] = 301{,}056{,}000$$

Otherwise $[14, 1, 3, 2] = [14, 1, 3, 2, 0] = [14, 1, 3, 2, 0, 0]$ etc. But, $[14, 0, 0, 17, 2] > [14, 0, 17, 2] > [14, 17, 2]$, so zeroes before the last positive number do not cause an ambiguity; the resulting value is different each time. But zeroes after the last positive number in the encoding sequence do cause ambiguity since the value of the coding does not change: $[14, 17, 2] = [14, 17, 2, 0] = [14, 17, 2, 0, 0]$ etc.

c) Godel Sequence Number - GLE (Godel Length Encoding)

This encoding inspired RLE (Run Length Encoding) on images, discussed below.

To demonstrate why an encoding does not have to be a compression: the Godel numbering sequence was a suggestion to encode any list or sequence of numbers. Suppose we have $2, 3, 5$ and we would like to encode them into one number. The convention was to use the number $1$ as a delimiter that indicates where the data field starts and ends, and $0$ occupies the data value itself (but here in a very specific manner). Note: the spaces are for legibility only and not part of the encoding.

Segment	1 00	1 000	1 00000	1
Value	$2$	$3$	$5$	(end)

Encoded string: 10010001000001

This works in theory because Turing machines have no limitation on storage length due to the infinite length of their tape for storage.

In the research, this encoding was generally avoided. This situation, while mathematically correct, would violate analysis of algorithm principles. GLE is essentially a unary (base-1) encoding: the value of a segment is encoded as its length in zeros, so value and length are one and the same. This is in contrast to base 2 or higher, where only $\log_2 n$ bits are needed to encode a value $n$ (or equivalently, $k$ bits can represent values up to $2^k$). NOTE: That itself would not have bothered the theoreticians. They were never concerned about complexity but about solvability. They were concerned with “Can it be done?” as opposed to how do you do it (constructively) or even how well can you do it. ALSO, the decoding function from binary string to natural numbers is not total — not every binary string corresponds to a valid GLE encoding (e.g., a string starting with 0, or one with an incomplete segment).

RLE - Run Length Encoding

Those inspired by GLE created the RLE compression algorithm. RLE works best if you are anticipating long sequences of the same data value, in which case, the long sequence can be replaced by: [How many times did a given character appear consecutively in the sequence?][The character referred to.]

Original	Compressed
aaaaaaaaaaaaa (13 a’s)	13a

NOTE: The compressed version 13a is stored actually in two bytes and the character is represented by its 8-bit ASCII code. So, if the string had 13 1’s, the compressed version would be 131, BUT this would not be ambiguous since each part of this compressed/encoded segment would be stored in its own byte: Byte#1: 13 and Byte#2: ASCII code for character "1".

RLE is not the most widely used standalone compression algorithm, but it is used in practice as a second-pass compression: some lossless compression algorithms produce output data where consecutive values tend to be the same or similar, so RLE can be applied as a second round to compress the result even further.

Although the above and future suggestions can encode any number of numbers, Godel still suggested that if you need to encode only two numbers, use the Pairing function, and if you need to encode 3 or more numbers, use the “Godel (prime number) encoding”. This distinction probably emanated from Cantor who describes the theory for encoding (“counting”) the number plane (two dimensions) as single numbers.

d) Polynomial Encoding (Cantor; Chowla)

Why did Godel settle on an exponentiation formula for Pairing and Prime encodings and not come up with a polynomial or multinomial encoding?

Cantor did consider this and came up with the following polynomial encoding (1873):

$$P(X, Y) = \frac{1}{2}\left((X+Y)^2 + 3X + Y\right) = \binom{X}{1} + \binom{X+Y+1}{2}$$

where $\binom{i}{k}$ is the choose function ($i$ choose $k$).

Note

This is algebraically equivalent to the standard form of Cantor’s pairing function $\pi(x,y) = \frac{(x+y)(x+y+1)}{2} + y$, but with the roles of $X$ and $Y$ swapped. Both are valid pairing functions; the version above is the one used in these notes.

This polynomial encoding does map the Natural number plane to single natural numbers. (Note: Since $P(0,0) = 0$, the minus constant is not necessary here.) I believe Cantor thought that there should be a whole family of polynomial encodings but he was not able to find any other polynomial encoding. Concerned with this, he avoided using this and suggested the above Pairing function, which is what theoreticians eventually all used.

Fueter and Polya (1923) proved that the above polynomial is the ONLY possible degree two polynomial that can accomplish this encoding. They conjectured that in fact the above polynomial is the only possible polynomial of any degree that can accomplish such an encoding (i.e., that every possible number(s) can be encoded and decoded).

e) Combinatoric Encoding

Chowla (1961) showed a generalization of the above polynomial using the equivalent combinatoric formulation that can extend to encoding any number of dimensions into a single number. Let $X_1 = X$ and $X_2 = Y$, and $n = 2$ (the number of variables). Then, the above combinatorics will be rewritten as $X_1 + \binom{X_1 + X_2 + (n-1)}{n}$. They generalized and proved an extended combinatorics that can encode any number of numbers as follows:

Consider encoding $n$ variables $X_1, X_2, \ldots, X_n$ by the following combinatoric polynomial:

$$P(X_1, X_2, \ldots, X_n) = \binom{X_1}{1} + \binom{X_1+X_2+1}{2} + \binom{X_1+X_2+X_3+2}{3} + \cdots + \binom{X_1+X_2+\cdots+X_n+(n-1)}{n}$$ $$= \sum_{k=1}^{n} \binom{\displaystyle\sum_{j=1}^{k} X_j + (k-1)}{k}$$

Just as Chowla (mentioned above) was able to generalize Cantor’s Combinatoric Polynomial to encode $n$ numbers, one can also generalize the Pairing Function (which uses exponentiation) to encode $n$ numbers, but it can be quite involved. I leave this as an open challenge for intrigued students. If you do obtain a solution, please write it up and email me. I would be interested to review it and compare it to the solution I have.

Efficiency note

For these last encodings, remember that Efficiency was not a concern, because nobody was ever going to do concrete calculations with these functions.

f) Beta Encoding

It has the advantage of being easier to describe than any efficient scheme. It requires only one arithmetic operation (mod), and it has a very short definition.

Godel’s $\beta$ function:

$$\beta(x, y, z) = x \bmod (1 + y + yz)$$

$\beta$ function lemma. For any sequence of natural numbers $(K_0, K_1, \ldots, K_n)$, there are natural numbers $b$ and $c$ such that for every natural number $0 \leq i \leq n$, $\beta(b, c, i) = K_i$. In summary, the beta function encodes any finite sequence of natural numbers with two natural numbers $b$ and $c$ where the $i$th number in the sequence is generated by the beta function with the specific $b$ and $c$ computed. In practice, a third value $n$ — the length of the encoded sequence — is also needed, since $\beta(b,c,i)$ can produce a value for any index $i$. Without knowing $n$, one cannot determine where the encoded sequence ends. So practically speaking, three values $b$, $c$, and $n$ are used together to fully encode and recover a sequence.

See Godel’s Beta Function Lemma proof on ProofWiki for a proof.

As an example, the sequence $(2, 0, 2, 1)$ can be encoded by $b = 3412752$ and $c = 24$ (where $x = b$, $y = c$, $z = \text{index}$). Note that the example below uses the equivalent form $1 + (z+1) \cdot y$, since $1 + y + yz = 1 + y(1+z) = 1 + (z+1) \cdot y$:

$$\begin{aligned} \text{rem}(3412752,\ 1 + (0+1) \cdot 24) &= \text{rem}(3412752,\ 25) = 2 \\ \text{rem}(3412752,\ 1 + (1+1) \cdot 24) &= \text{rem}(3412752,\ 49) = 0 \\ \text{rem}(3412752,\ 1 + (2+1) \cdot 24) &= \text{rem}(3412752,\ 73) = 2 \\ \text{rem}(3412752,\ 1 + (3+1) \cdot 24) &= \text{rem}(3412752,\ 97) = 1 \end{aligned}$$

See also Godel’s $\beta$ function on Wikipedia.

Godel was interested in this encoding to present his “incompleteness theorem.” Any system of logic proofs (“theorems” or truths) that includes all theorems regarding (Peano) arithmetic is either incomplete or inconsistent. As we discussed, anything that can be represented by a computer is represented by a finite string of 0/1s, which is a natural number. Thus, any listing of such theorems or truths can be encoded by the beta function. This made Godel’s counting arguments about the proposed system easier.

Formally, the “incompleteness theorem” states:

• No consistent system of axioms whose theorems can be listed by an effective (algorithmic) procedure is capable of proving all truths about the arithmetic of natural numbers.
• The above system cannot demonstrate its own consistency.

Finally, Ackermann’s function cannot be helped by these encodings - it simply grows faster than any primitive recursive function. As such this function is said to dominate or majorize any primitive recursive function.

Course of Values Recursion

Suppose you have a primitive recursive function $f(n)$ that has already generated the outputs $f(0), \ldots, f(n-1)$. The recursive step in function $f(n)$ computes:

$$f(n) = g(n, f(0), \ldots, f(n-1))$$

for some predetermined primitive recursive function $g(n, X_1, \ldots, X_n)$. This requires access to all previous levels’ outputs. If we incorporate Godel Prime Encoding, let:

$$[X_n] = [f(0), f(1), \ldots, f(n-1)]$$

then we can rewrite the above as follows:

$$f(n) = G(n, [X])$$

where $[\cdot]$ encodes the $n$ previous levels’ output values. Note: $G$ is used instead of the original $g$ since $g$ operates on the actual previous levels’ outputs but $G$ must decode $[X]$ first.

And then:

$$[X_{n+1}] = [X_n] \cdot \bigl(\text{Primes}(n)^{f(n)}\bigr) = [f(0), \ldots, f(n-1)] \cdot \bigl(\text{Primes}(n)^{f(n)}\bigr)$$

and:

$$f(n+1) = G(n, [X_{n+1}])$$

In essence, Godel Prime Encoding will encode all previous levels’ outputs by raising the prime generated at the current level to the power of the previous level’s output and “tack that on” to the Godel Prime Encoding passed along so far by simply multiplying this powered value by the previous Godel Prime Encoding obtained.

Pairing Functions Applied to Fibonacci

Now, let’s apply pairing functions to the Fibonacci sequence. The Fibonacci sequence is defined as:

$$\text{Fib}(0) = 0, \quad \text{Fib}(1) = 1, \quad \text{Fib}(n+1) = \text{Fib}(n) + \text{Fib}(n-1)$$

The actual values for the Fibonacci sequence are $0, 1, 1, 2, 3, 5, 8, 13, \ldots$

To avoid the issues raised by Fibonacci, we encode the two base cases and subsequently encode the two previous levels’ outputs by a pairing function which results in a simulated recursion on one base case and one previous level’s output. $G$ will be this auxiliary encoded function.

In computer theory, we always start with the base case. Here we want to encode the two Fibonacci base cases as a single number. In general (recursively) we want to encode the two latest Fibonacci numbers in the sequence.

Note

The actual single number that the pairing function or any other encoding produces is not relevant; what is relevant is that we can interpret (i.e., “decode”) it properly.

Consider the first seven encodings by the pairing function. In actuality a total of eight Fibonacci sequence numbers are located in these seven encodings:

Level	Encoding	Left	Right
0	$\langle 0, 1 \rangle$	0	1
1	$\langle 1, 1 \rangle$	1	1
2	$\langle 1, 2 \rangle$	1	2
3	$\langle 2, 3 \rangle$	2	3
4	$\langle 3, 5 \rangle$	3	5
5	$\langle 5, 8 \rangle$	5	8
6	$\langle 8, 13 \rangle$	8	13

What emerges is that the left side consistently encodes the actual Fibonacci sequence. The last number on the Right side is actually the 8th Fibonacci number in sequence. This occurs since the Right encoded sequence does not start with the first number on the Right as 0, but instead starts with the second Fibonacci sequence number as 1. But then, the remaining numbers are the next numbers in the Fibonacci sequence (“next” as in the latest number in the sequence after the value encoded on the Left).

In general, the encoding has $\langle \text{Fib}(n),\ \text{Fib}(n+1) \rangle$. Calling the encoding $G(n)$, we have:

$$G(n+1) = \langle \text{right}(G(n)),\ \text{right}(G(n)) + \text{left}(G(n)) \rangle$$

This is the encoded Fibonacci which uses the pairing function encoding/decoding so that this primitive recursive function only requires one base case and one previous level’s output.

Since $G(n) = \langle \text{Fib}(n),\ \text{Fib}(n+1) \rangle$, the $n$th Fibonacci number is simply $\text{left}(G(n))$ and the $(n+1)$th is $\text{right}(G(n))$. In general: $\text{Fib}(n) = \text{right}(G(n-1))$ for $n \geq 1$, or equivalently $\text{Fib}(n) = \text{left}(G(n))$ for all $n \geq 0$. The only thing else to specify is the one base case for this new Fibonacci function: $\text{Fib}(0) = 0$.

Putting this all together, the new FIBONACCI function is defined as:

$$\text{FIBONACCI}(0) = 0, \qquad \text{FIBONACCI}(n+1) = \text{left}(G(n+1))$$

The pairing function both allows for encoding and decoding. The decoding processes are simply given the names “left” and “right” functions and in the literature are further simplified, written as $l(Z)$ and $r(Z)$ for left and right respectively. So, left decodes $Z$ into the original $X$ and right decodes $Z$ into the original $Y$:

$$Z = \langle X, Y \rangle, \qquad X = l(Z), \qquad Y = r(Z), \qquad Z = \langle l(Z),\ r(Z) \rangle \text{ (as an identity)}$$

The Postal Stamp Problem

Ackermann’s function was not primitive recursive because it REQUIRED recursing on two variables. There exists a genre of problems in discrete mathematics that most discrete mathematics books present as if recursion/induction is required over two variables. The name of this group of problems is called the Postal Stamp problems.

Given two denominations (face values) of stamps, prove that any postage $\geq$ a specific fixed value can be comprised of some (independent) multiple of each denomination of stamp. In fact, there is a somewhat trivial way to rewrite the same problem such that the recursive/inductive step only requires multiples of the smaller of the two face values.

The requirement for two denominations is only to set up the multiple base cases (which will be in number equal to the face value of the smaller valued stamp denomination) and then based on modular arithmetic only multiples of this smaller value is required to obtain any other further amount of postage. And, as mentioned in previous classes, computer theory computes recursion in a bottom-up manner so that the base case actually occurs PRIOR to any recursive level is computed.

For example, any postage greater than or equal to 18 can be made by multiples of 4-cent and 7-cent stamps.

We now show our approach to this problem which will show that the recursive step only requires recursion (multiples) of 4-cent stamps and as mentioned above, the number of cases will be equal to the smaller of the two values, here 4.

BASE CASE:

Postage	Combination
$18$ ¢	$1 \cdot 4 + 2 \cdot 7$
$19$ ¢	$3 \cdot 4 + 1 \cdot 7$
$20$ ¢	$5 \cdot 4 + 0 \cdot 7$
$21$ ¢	$0 \cdot 4 + 3 \cdot 7$

Thus, the first four values (base cases) can be obtained using 0 or more multiples of 4 and 7 cent stamps.

RECURSIVE STEP:

ANY number greater than 21 can be made by multiples of 4-cent stamps added to one of these four cases based on modular arithmetic:

Base mod
$\text{Mod}(18, 4)$	$= 2$
$\text{Mod}(19, 4)$	$= 3$
$\text{Mod}(20, 4)$	$= 0$
$\text{Mod}(21, 4)$	$= 1$

Adding four or multiples of four to any of these mod functions will result in the SAME mod remainder:

Generalized
$\text{Mod}(18 + i \cdot 4,\ 4)$	$= 2$
$\text{Mod}(19 + j \cdot 4,\ 4)$	$= 3$
$\text{Mod}(20 + k \cdot 4,\ 4)$	$= 0$
$\text{Mod}(21 + m \cdot 4,\ 4)$	$= 1$

Thus, there actually is only ONE variable that is recursing: namely, the number of 4-cent stamps. Consider any large number and keep subtracting 4 from it (each time subtracting 4 will be adding one 4-cent stamp) till one of 18-21 will be reached (the base cases). The appearance of two variables is only to set up the base case(s), which occur PRIOR to the first recursive step.

Note

In reality, we could do the above with 7 in the same manner as with 4, but we choose $4 = \min(4, 7)$ because that has less base cases.

The postal stamp genre does not change the primitive recursion framework. The two denominations only serve to set up the multiple base cases, and having multiple base cases does not leave the rubric of primitive recursive. The whole point of these encodings is that, ultimately, you only need one base case and one previous level’s output - it is all based on simple induction and simple recursion.

Extended Recursion Schemes

Mutual Recursion

Assume prior known primitive recursive functions G and H. Now define two mutually (primitive) recursive functions, E and F: E is defined recursively in terms of F, and similarly, F is defined in terms of E.

Base Case(s):

$$E(0) = a, \qquad F(0) = b$$

Assigned with constants, but also can be based on auxiliary functions.

Also, could have $E(0, x)$ and $F(0, x)$.

Mutually Recursive Step:

$$E(n+1) = G(n, F(n))$$ $$F(n+1) = H(n, E(n))$$

$E$‘s recursive step is not based on $E$‘s previous level’s output but on $F$‘s; likewise, $F$‘s recursive step is not based on $F$‘s previous level’s output but on $E$‘s.

Also, could have $G(n, F(n), x)$ and $H(n, F(n), x)$.

Main part of proof that Mutual Recursion is Primitive Recursive by the Pairing Function encoding:

Consider $F(n+1)$: By plugging $E(n+1) = G(n, F(n))$ into $F(n+1) = H(n, E(n))$ where the previous level becomes $n-1$:

$$F(n+1) = H(n,\ G(n-1,\ F(n-1)))$$

G and H are known Primitive Recursive (as stated above) and now F is defined recursively in terms of F and no longer involves E. As such, we of course expect F to be proven to be Primitive Recursive. What is the difficulty? The recursive definition for F above is not stated in terms of previous level’s ($n$) output but rather the level before it ($n-1$). This dependence on $n-1$ violates the primitive recursion format, which requires defining $f(n+1)$ solely in terms of $f(n)$.

Resolve: Pairing Function comes to rescue here similar to the manner that it did for encoding Fibonacci.

Solution:

$$P(0) = \langle a,\ b \rangle$$ $$P(n+1) = \langle G(n,\ \text{right}(P(n))),\ H(n,\ \text{left}(P(n))) \rangle$$

Base cases are $E(0) = a$, $F(0) = b$. The pairing function is simulating/encoding $\langle E(n), F(n) \rangle$ in general.

And then:

$$E(n) = \text{left}(P(n)), \qquad F(n) = \text{right}(P(n))$$

This proves that Mutual Recursion of primitive recursive functions is still primitive recursive. NOTE: For simplicity of presentation the base cases were assumed to involve constants $a$ and $b$. In fact, they could involve functions, say, $Q$ and $R$ as long as they are only used in defining the base cases. Then, the entire proof proceeds as above. It wasn’t done because there are so many functions floating around already. Adding two more would add more confusion. But if in fact, you wanted to, then:

$$E(0) = Q(0), \quad F(0) = R(0), \quad P(0) = \langle Q(0),\ R(0) \rangle$$

but then $Q$ and $R$ never appear again so the proof continues as is.

Simultaneous Recursion

Assume prior known primitive recursive functions G and H. Now define two simultaneously defined (primitive) recursive functions, E and F: E is defined recursively in terms of E and F, and similarly F is recursively defined in terms of E and F.

Base Case(s):

$$E(0, x) = Q(x), \qquad F(0, x) = R(x)$$

Assigned to auxiliary functions, but could also be constants.

Recursive Step:

$$E(n+1, x) = G(n,\ E(n,x),\ F(n,x),\ x)$$ $$F(n+1, x) = H(n,\ E(n,x),\ F(n,x),\ x)$$

$E$‘s and $F$‘s recursive step each require the previous level output of both $E$ and $F$. $x$ is an example of an auxiliary variable. This is by definition; i.e. that is how “simultaneous recursion” is defined.

Outline of proof that Simultaneous Recursion is Primitive Recursive by the Pairing Function encoding:

Pairing Function:

$$P(0, x) = \langle Q(x),\ R(x) \rangle$$ $$P(n+1, x) = \langle G(n,\ \text{left}(P(n,x)),\ \text{right}(P(n,x)),\ x),\ H(n,\ \text{left}(P(n,x)),\ \text{right}(P(n,x)),\ x) \rangle$$

Left side defines $E$ and Right side defines $F$; encoding $\langle E(n,x),\ F(n,x) \rangle$.

Finally:

$$E(n, x) = \text{left}(P(n, x)), \qquad F(n, x) = \text{right}(P(n, x))$$

Divide and Conquer

cf. Discrete Mathematics, Master Theorem aka Master Method; e.g. mergesort falls under this category.

Divide and conquer recursion differs from other instances of (primitive) recursion in that the decision of which previous level’s output you need to define the next level is based on a ratio of distance from the current level. For example:

$$T(n) = aT(n/b) + c \cdot n^d \quad \text{with constants } a, b, c, d$$

Level $n$ is based on output at level $n/b$. The above is termed Nonhomogeneous since it involves both a previous level output $T(n/b)$ and a function of the level number $n$ (namely $n^d$).

This is clearly primitive recursive since course of values recursion keeps track of EVERY previous level’s output. See next tab for an elaboration on this.

Dynamic Programming

A misunderstood(?) recursion.

Dynamic programming (DP) is an algorithmic technique used to solve complex problems by breaking them down into simpler, overlapping subproblems and storing their solutions to avoid redundant computations (termed memoization).

Examples - three typical NP-Complete problems, proven after Karp’s paper:

• 0-1 Knapsack variant
• Subset Sum
• Partition

Read about these problems and their dynamic programming formulations. If there is time, we will discuss this more in another lecture.

Dynamic Programming typically will have an iterative nested double for-loops that will solve the problem. From a simplistic approach, the complexity would appear to be $O(n^2)$, since each for-loop is $O(n)$ and they are nested. But, clearly the above NP-Complete problems exhibit exponential complexity if $P \neq NP$, which is assumed by most. The issue at hand is what does $O(n)$ really mean. One of the for-loops in dynamic programming iterates through all possible output VALUES and not based on length of input. (We had a similar issue when we analyzed the nested triple for-loop that power (exponential) has when programming the nonrecursive coded version of the primitive function POWER (exponential) based on the successor function $S(X) = X+1$.)

On a separate note, a distinction should be made between the divide and conquer recursion and the dynamic programming recursion. Divide and conquer breaks up the problem on the original size (amount) of data in terms of a number of smaller pieces, but all of the same size. Dynamic programming also breaks up the problem of the original size amount of data in terms of a number of smaller pieces, but each of those pieces tend to be of different sizes. Finally, while solving discrete mathematics recurrence (or recursive) relations (or equations) and dynamic programming are all interested in the nonrecursive equivalent to obtain the exact solution, divide and conquer recursions “solved” by the Master Theorem (from discrete mathematics) only determine the order of complexity.