2
$\begingroup$

Consider computable functions $f: \mathbb{N} \rightarrow \mathbb{N}$, given as formulas. I assume that it is clear for at least some of them whether they contain a distinction of cases:

$$f(n) = n$$

obviously does not contain a distinction of cases (i.e. is d.c.-free),

$$ g(n) = \begin{cases} 1 & \text{for } n = 0 \\ n & \text{otherwise} \end{cases} $$

obviously does, at least at the face of it.

What is not clear is whether there is a d.c.-free function $g'$ that is equivalent with $g$, is it?

What I believe to know:

  1. It is not decidable whether there is a d.c.-free function equivalent with a given one (unless one can prove that there is one for every computable function!)

  2. Especially, a d.c.-free function $g'$ is not "computable" (as a formula) from a given one $g$

  3. Even when you are given one (by an oracle): showing the equivalence of $g'$ and $g$ is not decidable.

Nevertheless there are at least some trivial cases where a d.c.-free formula exists, e.g. for

$$ g(n) = \begin{cases} 0 & \text{for } n = 0 \\ n & \text{otherwise} \end{cases} $$

Can anyone provide a non-trivial example?

$\endgroup$
4
  • $\begingroup$ Can the formulas involve quantifiers in the definitions of the cases? $\endgroup$ – Carl Mummert Jun 26 '14 at 11:00
  • $\begingroup$ As far as quantifiers can be mimicked by recursive functions. $\endgroup$ – Hans-Peter Stricker Jun 26 '14 at 12:35
  • $\begingroup$ So you do not allow primitive recursion? $\endgroup$ – André Nicolas Jun 27 '14 at 0:08
  • $\begingroup$ @AN: This objection is striking! (I did not realize that d.c. is an integral part of the definition of primitive recursion. But is it really and indispensably?) $\endgroup$ – Hans-Peter Stricker Jun 27 '14 at 7:23
4
$\begingroup$

The answer to this question heavily depends on what functions are allowed as building blocks for non d.c. functions. A little thought shows that if it's somehow possible to construct a step function using non d.c. functions, then any d.c. function can in principle be rewritten using these step functions - admittedly, not in a particularly nice way.

If we assume that $x\rightarrow x^2$ and $x\rightarrow \sqrt x$ are allowed as non-d.c. functions, then we can construct the absolute value function as $|x| = \sqrt{x^2}$, and using the absolute value function, we can then construct the max and min functions as

$$ \max(a,b) = \frac{|a - b| + a + b}{2}\\ \min(a,b) = \frac{|a - b| - a - b}{2}$$

Using these functions, we can first construct $f(x) = \max(x+1,0)$ and $g(x) = \max(x,0)$. When restricted to the natural numbers, we see that $h = f - g$ is equivalent to $$ h(n) = \begin{cases} 1&n \geq 0\\ 0 &n < 0\\ \end{cases}.$$

This step function can be translated to anywhere on the number line by defining $$h_a(n) = \max(n+1-a,0)-\max(n-a,0) = \begin{cases} 1 & n \geq a \\ 0 & n < a\end{cases}.$$

We can then get a generalized filter function by the product $h_a(1-h_b)$.

Any d.c. function can therefore be rewritten in terms of these products. For example, the function $$ f = \begin{cases} 1 & n = 0 \\ 0 & \mathrm{otherwise} \end{cases} $$ can be written as $h_0\cdot(1- h_1)$.

Writing $f$ out explicitly (only in terms of abs!), we have

$f(n) = \frac 14 \left[\left(1-|n|\right)\left(1-|n| +|n-1| + |n+1|\right) + |n^2-1| \right]$

Checking, we see that $$f(0) = \frac 14 \left[1\cdot(1 + 1 +1) + 1\right] = 1,$$ while $$\begin{align}f(n)|_{n \geq 1} &= \frac 14 \left[(1-n)(1-n+n-1+n+1)+n^2-1\right]\\ &= \frac 14 (1-n^2 + n^2 -1) = 0\end{align},$$ and $$\begin{align}f(n)|_{n \leq -1} &= \frac 14 \left[(1+n)(1+n-n+1-n-1)+n^2-1\right]\\ &= \frac 14 (1-n^2 + n^2 -1) = 0\end{align},$$

exactly as desired. This also shows that the construction in terms of cases is a great deal more succinct (and clear) than the one presented here.

$\endgroup$
1
  • $\begingroup$ Everything is fine! I appreciate the construction. The only thing I don't like is the - arbitrary - dependence of the function $f$ of the parameters $0$ and $1$ (in $h_0$ and $h_1$), which somehow play the role of the "definition by cases". But I cannot explain that any further. $\endgroup$ – Hans-Peter Stricker Jun 26 '14 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.