Undefined behaviour when composing primitive-recursive with $\mu$-recursive functions?

Question

It is quite easy to show that the following two functions are primitive recursive and thus also $\mu$-recursive: $$ifthen(n,a,b) = \begin{cases}a & n > 0 \\ b & else\end{cases} $$ $$ eq(x,y) = \begin{cases} 1 & x = y \\ 0 & else\end{cases} $$

Now, given a $\mu$-recusive function $f$ which is not total, i.e. whose domain $\mathcal{D}_f$ is a proper subset of $\mathbb{N}_0$, we can extend it to a function $f^\prime$ on $\mathcal{D}_{f^\prime} = \mathcal{D}_f\cup\{x^\prime\}$ for a fixed $x^\prime\not\in\mathcal{D}_f$ via $$ f^\prime(x) = \begin{cases}x^\prime & x = x^\prime \\ f(x) & else\end{cases}$$ and this function $f^\prime$ can be expressed in terms of $ifthen$, $eq$, the constant function $x\mapsto x^\prime$ and $f$ as a composition of $\mu$-recursive functions as $$ g(x) = ifthen(eq(x,x^\prime), x^\prime, f(x)).$$

Here is the interesting question: Is there a consistent way to define at what time the arguments to any $\mu$-recursive function, and the function $g$ above in particular, are evaluated?

Let me illustrate the problem:

Assuming all arguments of $ifthen$ are evaluated before being passed to $ifthen$, then $g(x^\prime)$ will not return $x^\prime$ since the computation of $f(x^\prime)$ never terminates.

We could also assume some kind of "lazy evaluation" where arguments are only evaluated when they really are needed. Then, when implementing $ifthen$ using primitive recursion as $$ ifthen(0, a, b) = b \\ ifthen(n+1, a, b) = a,$$ the function $g$ would really be equal to the function $f^\prime$ as $f$ will never be called with argument $x^\prime$. But there is a different way to implement $ifthen$ using just arithmetic operations $$ ifthen(n, a, b) = a \cdot (1 \dot{-} (1 \dot{-} n)) + b \cdot (1 \dot{-} n)$$ where $\dot{-}$ is the modified difference $\dot{-}:\mathbb{N}_0\times\mathbb{N}_0 \rightarrow \mathbb{N}_0$ defined by $$ x \dot{-} y = \begin{cases}x - y & x \geq y \\ 0 & else \end{cases}.$$ As primitive recursive functions, both implementation are equivalent and really compute $ifthen$, but if we assume $g$ uses this second implementation, then $f(x^\prime)$ again has to be evaluated and the computation of $g(x^\prime)$ never terminates, in particular $g(x^\prime) \neq f^\prime(x^\prime)$.

This seems odd to me, as computability of functions should not depend on the particular implementation of a function, but I have not been able to come up with a solution to fix that problem.

EDIT: More formally speaking, if we introduce the symbol $\bot$ for non-termination, the function $f$ above can be interpreted as a function $$ f:\mathbb{N}_0\rightarrow\mathbb{N}_0\cup\{\bot\} \\ f(x) = \begin{cases} f(x) & x\in\mathcal{D}_f \\ \bot & else\end{cases}. $$ Using this notation, every $\mu$-recursive function $$ h : \mathbb{N}_0^k \rightarrow \mathbb{N}_0\cup\{\bot\} $$ can be extended to a $\mu$-recursive function $$ h^\prime : (\mathbb{N}_0\cup\{\bot\})^k \rightarrow \mathbb{N}_0\cup\{\bot\} \\ h^\prime(\bar{x}) = \begin{cases} h(\bar{x}) & \bar{x}\in\mathbb{N}_0^k \\ \bot & else \end{cases}. $$ This corresponds to evaluation of arguments before the function $h$ is called.

Unfortunately, while this extension is sometimes unique (e.g. for the function $eq$ above), most of the time it is not. Especially in the case of a k-ary constant function it even is more natural to extend it to $$ const_c^\prime : (\mathbb{N}_0\cup\{\bot\})^k \rightarrow \mathbb{N}_0 \\ const_c^\prime(x_1,\dots,x_k) = c $$ instead.

The question I'm asking is the following: Given the implementation of a $\mu$-recursive function, is there a way to infer which extensions are / are not $\mu$-recursive?

One approach I tried is always assuming lazy evaluation of arguments. This yields the "correct" extension in the case of constant functions, $eq$ and the first implementation of $ifthen$, where the extension I need to be $\mu$-recursive in order to implement the function $f$ fulfills $$ ifthen^\prime : (\mathbb{N}_0\cup\{\bot\})^3 \rightarrow \mathbb{N}_0\cup\{\bot\} \\ ifthen^\prime(n, a, b) = \begin{cases} b & (n,a,b)\in {0}\times(\mathbb{N}_0\cup\{\bot\})\times\mathbb{N}_0 \\ a & (n, a, b) \in \mathbb{N}_{>0}\times\mathbb{N}_0\times(\mathbb{N}_0\cup\{\bot\}) \\ \bot & else\end{cases}. $$

But if I were just given the second implementation of $ifthen$, lazy evaluation just yields the canonical extension and not the one I require. Then the proof that $f^\prime$ is $\mu$-recursive would be incomplete unless I find the first implementation of $ifthen$ (or any other implementation of it that leads to the "correct" extension when assuming lazy evaluation), moreover it would be incorrect if there would not be such an implementation of $ifthen$.

How can I identify the possible behaviours of compositions of $\mu$-recursive functions?

Answer 1

There's a couple of questions here, so a couple of answers.

Changing when function parameters evaluated fundamentally changes your extensions of the function.

There seems to be a misunderstanding:

As primitive recursive functions, both implementation are equivalent and really compute $ifthen$...

This depends on exactly what type of $ifthen$ function we're talking about. Let's look at your implementations. Your first:

$ifthen(0, a, b)=b\\ ifthen(n+1, a, b)=a$

Note that, if the parameters are always "pre-evaluated" to natural numbers before being passed to the function, i.e. they can be treated simply as natural numbers, not as functions. In this case, this indeed implements a primitive recursive function, as you say. Now your second:

$ifthen(n, a, b)=a⋅(1\overset{˙}{−}(1\overset{˙}{−}n))+b⋅(1\overset{˙}{−}n)$

Where $\overset{˙}{−}$ is truncated subtraction. Again, assuming pre-evaluation of parameters, this is primitive recursive and, as you point out, implements the same function as the first. Note that lazy evaluation does not affect this, since pre-evaluation means that no parameters except constant natural numbers will be passed to $ifthen$.

Since we're assuming pre-evaluation, both implementations behave identically in an extension such as the one you proposed:

$g(x)=ifthen(eq(x, x'), x', f(x))$

Because any implementation of $f$ shouldn't halt when its input is undefined, but we're evaluting $f(x)$ before we even pass its value to $ifthen$, no program implementing $g$ will halt on $x$ when $f(x)$ is undefined, even if you assume lazy evaluation in $ifthen$.

Now, let's remove the restriction that the parameters to $ifthen$ are pre-evaluated; specifically, let us define a new function $ifthen^*$ that accepts arbitrary $μ$-recursive functions for its parameters, along with some particular parameters for each function to be evaluated on. If all of the passed functions can be evaluated (i.e. they halt), then it evalutes $ifthen$ on the provided values; otherwise, it doesn't halt. By passing $ifthen^*$ certain values, we can get a function equivalent to $g(x)$ implemented without lazy evaluation.

Note that $ifthen^*$ is now a composition of arbitrary $μ$-recursive functions (its parameters). Therefore, by definition it is not a primitive recursive function and is not equivalent to the above $ifthen$ function!

However, it is almost equivalent to $ifthen'$, as defined in your post. The difference in the implementations of $ifthen^*$ and your $ifthen'$ is simply lazy evaluation; i.e. it evaluates $n$ first, compares the result to $0$, then evaluates $a$ or $b$ as necessary, rather than always evaluating all the functions. Since $ifthen'$ is defined on some inputs that $ifthen^*$ is not, the two functions are not equivalent. This means that lazy evaluation is not just an implementation detail. It actually changes what function your program is implementing.

This brings us to an excellent question of yours:

How can I identify the possible behaviours of compositions of $μ$-recursive functions?

where a composition of a finite number of $μ$-recursive functions and no non-$μ$-recursive functions, is also $μ$-recursive. Likewise, you might ask, "given an implementation of an arbitrary $μ$-recursive function, can I determine which of its extensions require lazy evaluation". You seem to be looking for a consistent way to answer such questions regardless of the $μ$-recursive function in question, which leads to an unfortunate result:

Non-trivial properties are undecidable over the $μ$-recursive functions.

That is, if you want to determine whether a particular $μ$-recursive function, its implementation, or its extensions have some sort of behavior or other property, unless the property applies to all $μ$-recursive functions or to none at all, there is no $μ$-recursive function that can decide whether some arbitrary $μ$-recursive function has this property. This is the main result of Rice's Theorem.

Note that this strictly refers to the semantics of arbitrary $μ$-recursive functions, i.e. whether the function itself has a property. Syntactic properties, i.e. properties of the implementation itself, not the function in question, may be decidable, e.g. the Bounded Halting Problem. However, the problem of determining whether a particular syntactic property is decidable is in turn semantic, and is undecidable for arbitrary properties.

Answer 2

I will only address a few points.

---

First, note that, in mathematics, the composition of two relations $R\circ S$ relates $x$ with $y$ iff $xRzSy$ for some $z$. This means that if there is no $z$ for which $xRz$, then there is no $y$ for which $x(R\circ S)y$ holds.

Since functions are relations too, the domain of $f\circ g$ is a subset of the one for $g$. Consequently, when writing $f(g(x))$, this is undefined if $g(x)$ is undefined.

Roughly speaking, the mathematical notation $f(g(x))$ assumes a "strict" interpretation: even if $f(n)=5$ for all $n$, we have that $f(1/0)$ is undefined.

---

In computability, if $f,g$ are primitive recursive, the function

$$ h(x,y) = \begin{cases} f(y) & \mbox{if $x>0$} \\ g(y) & \mbox{if $x=0$} \\ \end{cases} $$

can be obtained as $h(x,y)=ifthen(x,f(y),g(y))$, so it is primitive recursive.

If $f,g$ are total recursive (not necessarily primitive), we also have $h(x,y)=ifthen(x,f(y),g(y))$, which becomes total recursive.

However, if $f,g$ are partial recursive, we no longer have $h(x,y)=ifthen(x,f(y),g(y))$ in general, since $h(x,y)$ is in general defined on more cases than $h(x,y)=ifthen(x,f(y),f(y))$. To prove that the conditional is partial recursive, usually the following steps are taken. We choose $i,j$ so that $f=\phi_i$ and $g=\phi_j$. Then, we exploit the universal function $eval(n,z)=\phi_n(z)$, which we already know to be partial recursive, to derive

$$ h(x,y) = eval(ifthen(x,i,j),y) $$

Now, $ifthen$ is applied to "defined" arguments $x,i,j$, hence it will always produce a value: either $i$ or $j$ depending on whether $x>0$. Hence, the final result will be either $eval(i,y)=\phi_i(y)=f(y)$ or $eval(j,y)=\phi_j(y)=g(y)$, as wanted.

This is the standard way to "lazify" the $ifthen$, so that it works on all prtial recursive functions.

As you see, this approach is different from using something like $lazyifthen(x,f(y),g(y))$, which can not work unless we allow $\bot$ in the domain. Doing so, however, requires some care, since e.g. $x=\bot$ can not be decided without solving the halting problem.