Non-computable function having computable values on a dense set of computable arguments

Solution 1:

The answer to (1) is yes: it's easy to show that there are distinct continuous functions $f, g$ such that

• the domain of $f$ and $g$ is $D=\{a+bi: a, b\in[0, 1]\}$,

• on the boundary of $D$, $f$ and $g$ are zero, and

• $f(Q), g(Q)\subseteq Q$ (where $Q=\{a+bi: a, b\in\mathbb{Q}\}$).

Now say that a function $h$ is a quilt if it is gotten by pasting together copies of $f$ and $g$: that is, for every pair of integers $u, v$, we have $$h\upharpoonright \{a+bi: a\in [u, u+1], b\in [v, v+1]\}=T_{u, v}\circ f\circ T^{-1}_{u, v}$$ or $$h\upharpoonright \{a+bi: a\in [u, u+1], b\in [v, v+1]\}=T_{u, v}\circ g\circ T^{-1}_{u, v}$$ where $T_{u, v}$ is the translation taking $0$ to $u+vi$.

Since $f\not=g$, there are uncountably many quilts, and since $f(Q), g(Q)\subseteq Q$, every quilt is pointwise computable. But there are only countably many computable functions.

I believe the answer to (2) is also yes, but I don't have a proof yet; let me sketch why I think there is such a function.

Basically, we'll write $f$ as the limit of a sum of analytic functions: $$f(x)=\lim_{n\rightarrow\infty}\sum_{i=1}^nt_i(x).$$ We will of course have to guarantee that this limit converges, and that will take work - in particular, this is the part I'm least confident can be patched. For now, I'll ignore it.

Each $t_i$ will have a computable Taylor series (that is, a Taylor series whose coefficients form a computable sequence of rational numbers). Additionally, at stage $s$ in the construction, we will have fixed finitely many rational complex numbers $q_1, . . ., q_s$ and placed requirements on them of the form

• $R_1:\quad$ $\vert f(q_1)-\sum_{i=1}^s t_i(q_1)\vert<\epsilon_1$,

• $R_2:\quad$ $\vert f(q_2)-\sum_{i=1}^s t_i(q_2)\vert<\epsilon_2$,

• etc.

So basically, a stage in the construction is a pair $P_s=(t_1, t_2, . . . , t_s; R^{P_s}_1, R^{P_s}_2, . . . , R^{P_s}_s)$. There is a natural sense in which an analytic $t_{s+1}$ "makes sense" to tack onto $P_s$: each $\sum_{i=1}^{s+1}t_i(q_k)$ must satisfy $R_k$.

If we proceed in the natural way now, we obviously build a computable function. So the question is: how do we put a twist on this construction so that the resulting function is pointwise-computable-on-a-dense-set, but not computable?

The answer is finite injury. Basically, we want to construct a sequence of stages $(P_s)_{s\in\mathbb{N}}$ such that

• $\sum t_s$ is analytic, and

• for each $n$ there are only finitely many $s$ such that $P_{s+1}$ violates $R^{P_s}_n$.

Any such sequence of stages will correspond to an analytic function which is pointwise-computable-on-a-dense-set.

At this point we can diagonalize against the computable complex functions in the standard way: wait until the $0$th computable function makes a decision about where the $0$th rational should go, then injure the construction so far to make the $0$th computable function distinct from the $f$ we are building. (In fact, we can set this part up so that each requirement is injured at most once.)