Can the computability of a specific function be independent of ZFC?

Question

If I understand correctly there exist artificial examples. Let P be a statement known to be independent of ZFC, such as CH, $g:\mathbb{N}\rightarrow\mathbb{N}$ be a function known to be uncomputable, such as the one related to halting problem. Define a function $f:\mathbb{N}\rightarrow\mathbb{N}$ as follows: if P holds then $f=0$; otherwise $f=g$. Then whether $f$ is computable would be independent of ZFC. My questions are:

1. Is there any natural example?

2. Actually this is what I initially wanted to ask: is there any provably ineffective result in number theory (here "effective" is synonym for "computable")? The Siegel's theorem leads to many ineffective results, but Generalized Riemann Hypothesis (GRH) implies effective version of those results. Virtually everyone believes GRH is provable, and hence Siegel's result actually is effective.

Answer 1

One standard example of a function whose complexity is wildly independent is the continuum pattern, or rather, patterns. These are the various sequences associated to the function $EXP:\kappa\mapsto 2^\kappa$ on infinite cardinals $\kappa$.

For our purposes it's enough to just look at the first bit of this pattern. Let $ind$ be the indexing function for cardinals, sending $\aleph_\alpha$ to $\alpha$, and consider the map $$f:m\mapsto ind(2^{\aleph_m}).$$ This part of the continuum pattern is already totally bizarre: it could be anything subject to the obvious rule that $x<f(x)\le f(x+1)$. Note that "$\le$" - $\mathsf{ZFC}$ can't even prove that cardinal exponentiation is injective!

The fact that arbitrarily much complexity can be coded into the continuum pattern is a useful trick in set theory - it lets us whip up wild models of $\mathsf{ZFC}+V=HOD$.

Answer 2

Would you consider solving a Diophantine equation a natural problem? It is known that there is a polynomial $p$ (in $9$ variables) s.t. whether it has integer roots or not is independent of ZFC. Using this fact, one can cook a function that is computable iff $p$ has integer roots.

Let me elaborate a bit: it is known that there is a computable bijection $\langle \cdot \rangle\colon \mathbb{N}^9 \to \mathbb{N}$. Using this function we can well-order the set of $9$-tuples (so that we can talk about the "least" tuple). Consider the function $f$ that, upon input $x$ returns $1$ if $\{x\}(x)$ halts in less than $\langle m_1,...,m_9 \rangle$ steps and $(m_1,...,m_9)$ is the least tuple s.t. $p(m_1,...,m_9)=0$, otherwise it returns $0$. In symbols $$ f(x):=\begin{cases}1 & \text{if } (\exists s)( \{x\}(x) \text{ halts in } s \text{ steps and }\\ & \qquad ~~(\forall m_1,...,m_9)( \langle m_1,...,m_9\rangle < s \rightarrow p(m_1,...,m_9)\neq 0)) \\ 0 & \text{otherwise} \end{cases}$$

Intuitively, what $f$ does is searching for $m_1,...,m_9$ that satisfy $p(m_1,...,m_9)=0$ while, in parallel, waiting for $\{x\}(x)$ to halt. If $\{x \}(x)$ does not halt or it does halt after $f$ found a solution for $p$ then $f(x)=0$.

If such $m_1,...,m_9$ exist, then eventually $f$ will find them, hence $f$ basically tells you whether $\{ x \}(x)$ halts before a fixed number of steps, which is a computable function.

If, on the other hand, such $m_1,...,m_9$ do not exist, then $f$ is the characteristic function of $\emptyset'$, hence it is not computable.