Computability in harmonic analysis (Q2671298)

This paper deals with the problem of approximating harmonic measures of bounded domains with respect to points in the domain. The ideal starting point of this investigation is indeed that of considering computability of harmonic measures on single points, but a surprising result shown by the authors is that computability on a single point immediately implies computability on all points of the domain. This does not mean that computability is uniform: in fact, in general, different algorithms are required (Theorem A). The proof of this result is based on a particular definition of harmonic approximations of domains. This is given (according to Definition 2.11) by sequences of dyadic polygons (connected interiors of finite unions of dyadic cubes) approximating, so to say, triples made by the domain itself, a point $x$, and a dyadic polygons in the domain (this also involves approximations of Lipschitz functions of a certain type). It is proved that any domain in the unitary $d$-dimensional cube is such that the harmonic measure of the domain at a point $x$ is computable if and only if there is a computable harmonic approximation with respect to any dyadic polygon $Q$. This paper presents several surprising results that are very important for computable analysis. Usually, incomputable (multi-)functions are trivially incomputable because of their discontinuity. It is in fact not so easy to find ``natural'' examples of incomputable continuous functions. The authors not only provide a natural example for that, but, even more, the example that they analyze is even piecewise computable: they show indeed that there exists a regular domain and a computable real function on its border with a unique solution $u$ to the Dirichlet problem such that, for every $x$, the value $u(x)$ is computable in $x$ but $u$ is not computable (Theorem C). A nice strengthening of Theorem A is provided by Theorem E, stating that on regular domains with computable boundaries, the computability of the harmonic measure at some computable point in the domain is equivalent to the uniform computability of the harmonic measure, hence there exists an algorithm that works for all points in the domain (a domain is regular when the values with respect to a continuous function on the boundary and with respect to the solution to the corresponding Dirichlet problem coincide for all points in its boundary).