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

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 implementat

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.

StackExchange Computer Science Q#44935, answer score: 2