10
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Noah Schweber Jul 13 '15 at 4:42
  • $\begingroup$ @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. $\endgroup$ – hardmath Jul 13 '15 at 4:49
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Jul 13 '15 at 17:34
  • $\begingroup$ @NoahSchweber Yes, I changed the wording of my first question when I realized this. $\endgroup$ – Vladimir Reshetnikov Jul 13 '15 at 21:17
2
+100
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.