Is $f: \mathbb{N} \to \mathbb{N}$ a computable function if it is : $1)$ nondecreasing; $2)$ nonincreasing

Question

According to the definition, a function $f$ is computable is

$1)$ $\forall x \in \text{Dom}(f)\ \exists\ \text{Algorithm} : f\ \text{returns}\ f(x)$.

$2)$ otherwise, $f$ never stops.

For the moment I have two ideas, but not sure of any of those.

FIRST IDEA:

This is quite simple. From the definition, it wouldn't matter whether $f$ is not increasing/decreasing, since for some $x \in \mathbb{N}$ the program would return $f(x)$ or it keeps going otherwise. So it would be a computable function anyway.

SECOND IDEA:

Here I brought the concept of bijective function. I'm not sure if this is necessary/allowed of it is even an implicit assumption of the nature of the function $f$. Well,

If $f$ is bijective, then for $f$ to be:

$a)$ nondecreasing: It has to be is strictly increasing for it to be computable. Otherwise $\exists x_1, x_2 \in \mathbb{N}: x_1 < x_2: f(x_1) = f(x_2)$, but this would imply that $f$ is not bijective.

$b)$ nonincreasing: As above, $f$ has to be strictly decreasing in order to be bijective. But in this case, considering that $f: \mathbb{N} \to \mathbb{N}$, we have that $\exists x' \in \mathbb{N}: \forall x > x' \implies f(x) = f(x')$ (we keep in mind that $\lim_{x\to \infty} f(x) = 1)$.

So under this assumption $f: \mathbb{N} \to \mathbb{N}$ would be computable only if it is an strictly increasing functions.

I'd appreciate any help with this.

Answer 1

There are a lot of incorrect assumptions here.

First of all, your definition of computable function has the quantifiers backwards: it should be

$f$ is computable if there is some algorithm $A$ such that for every $n$, $A(n)$ halts and outputs $k$ iff $f(n)$ is defined and equals $k$.

Note that this is one algorithm which works for all inputs.

The rest of your post confuses me. To begin with, I can't follow your first idea at all.

Moving on to the second idea:

• Every nonincreasing function is eventually constant, hence computable. (You got this correctly.)

• There is only one nondecreasing bijection from $\mathbb{N}$ to $\mathbb{N}$: the identity function. And this is of course computable.

• However, there are lots of nondecreasing - in fact, increasing! - functions which aren't computable: the Busy Beaver function is a nondecreasing example, and it's not hard to tweak it to get an increasing example. Or, nonconstructively, just note that there are uncountably many increasing functions and only countably many computable functions.

Meanwhile, you seem to miss the existence of nonmonotonic functions. There are lots of these which are computable:

• The parity function ($par(x)=0$ if $x$ is even and $par(x)=1$ if $x$ is odd).

• The function $$g(x)=x+5par(x)$$ is computable but neither increasing nor decreasing; its first few values are $$6, 2, 7, 3, 8, 4, . . .$$

• And we can come up with bijective computable functions which are neither increasing nor decreasing: e.g. $f(x)=x+1$ if $x$ is odd and $f(x)=x-1$ if $x$ is even; its first few values are $$2, 1, 4, 3, 6, 5, . . .$$

---

So I think the only thing that is correct is your observation that every nonincreasing function is computable.

Answer 2

Your first idea doesn't make much sense to me - it looks like you've gotten turned around in your thinking. In the question you posed in your title, you are not assuming $f$ is computable and attempting to determine what effect the non-increasing/non-decreasing requirement has. You're taking a function $f$ which is non-increasing or non-decreasing and attempting to determine whether it is computable. So you can't assume you already have an algorithm for $f$.

In (a) and (b), all you've shown is that a bijective function (regardless of computability) that is nondecreasing or nonincreasing must be strictly increasing (as long as it's total, which is to say that $f$ is defined on all $n \in \mathbb{N}$). Your argument doesn't say anything about computability.

There are plenty of noncomputable strictly-increasing functions; for example, let $f(n)$ be the smallest number $N$ so that $N > f(m)$ for all $m < n$ and every program indexed by a number $<n$ halts in fewer than $N$ stages if it ever will halt. In fact, in a precise sense, "most" strictly-increasing functions are not computable.

However, your argument actually tells you something important about non-increasing functions. As you observe, a non-increasing function has to be eventually constant. That means that if $f$ is non-increasing, it only carries finitely much information: a bunch of values before it stabilizes, and then what number it stays constant at. You can turn this into an algorithm for computing $f$.