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

A rational complex number is a complex number whose both real and imaginary parts are rational numbers. Note that a rational complex number is a finitary object that can be an input or an output of an algorithm.

A sequence of rational complex numbers is computable if there is an algorithm that given a positive integer index $k$ as an input, returns the corresponding element of the sequence.

A complex number $z$ is computable if there is a computable sequence of rational complex numbers that converges to $z$.

A function $f:\mathbb C\to\mathbb C$ is computable if there is an algorithm $P$ with the following property: for each (not necessarily computable) sequence of rational complex numbers $\{q_1,q_2,...\}$ that converges to a complex number $z$, when the algorithm $P$ is given the sequence $\{q_1,q_2,...\}$ as an input, it generates an infinite sequence of rational complex numbers $\{p_1,p_2,...\}$ that converges to $f(z)$. (More precisely, if $P$ is given an access to an oracle that can tell elements $q_m$ by their index $m$, and given a positive integer index $k$ as an input, it generates a rational complex number $p_k$; the sequence $\{p_1,p_2,...\}$ of those outputs converges to $f(z)$).

A function $f:\mathbb C\to\mathbb C$ is pointwise computable on a dense set if there exists a set of complex numbers $S$ dense in $\mathbb C$, such that every $z\in S$ is computable, and the corresponding function value $f(z)$ is computable.

1. Is there a continuous function $f:\mathbb C\to\mathbb C$ that is pointwise computable on a dense set but not computable?
2. Is there an analytic function $f:\mathbb C\to\mathbb C$ that is pointwise computable on a dense set but not computable?
• As written, 1 has a trivial answer since every computable function is continuous; maybe you want to add the requirement that $f$ be continuous at least? – Noah Schweber Jul 13 '15 at 4:42
• @NoahSchweber: Certainly an analytic function $f$ on $\mathbb{C}$ is continuous (as in part 2.), but if you could elaborate on why pointwise computable (as in part 1.) implies continuity, I would find that a helpful Answer. – hardmath Jul 13 '15 at 4:49
• @hardmath my point was that any computable function is continuous - so, any non-continuous pointwise computable function would provide a counterexample to (1) as originally written - say, the characteristic function of the computable complex numbers. – Noah Schweber Jul 13 '15 at 17:34
• @NoahSchweber Yes, I changed the wording of my first question when I realized this. – Vladimir Reshetnikov Jul 13 '15 at 21:17

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.)