Functions with and without distinction of cases 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:


*

*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!)

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

*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?
 A: 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.
