数理解析研究所講究録
1169 巻 2000 年 84-91

84

How to understand the computability aspects ofstep functions
Mariko Yasugi

1*

Objective

In the following, I assume basic knowledge in recursive functions and computability properties of real numbers, of sequences of real numbers, of continuous real functions and of basic facts in computability structures in Banach
spaces. References [3] and [12] will be useful in obtaining necessary knowledge.
Our objective in this report is to give a mathematical expression to the actionof drawing a graph which is not necessarily connected. (I insist on mathematicaltreatment, and will not go into algorithmic foundations. I would like also toemphasize that I wiil confine subsequent discussions to “our way” of such aneffort, that is, of myself as well as my colleagues. I warn the reader that ehre
are many other ways to treat such a subject, but I do not mention them here
in order to avoid deviation. )The reason of need for such considerations is the following. (Here I consider
only unary real functions.) In drawing a graph of a function, one first computes
and plots some real numbers on the -axis, usually some fractions. One thencomputes the values of the function at such points and plots the corresponding
points in the plane. Finally, one connects these points as smoothly as possible.
Computer graphics would do similarly.
In sucn an action, computing the function value at a point is essential. (Here,computation means approximating computation of arbitrary precision.) For acontinuous function, the notion of computability has been traditionally established, and, for a computable function, it is theoretically possible to computeits value at a computable input. On the other hand, it is a common practiceto draw a graph of a discontinuous function. It has also been systematicallystudied in [3] how to view a discontinuous function to be computable. Their tool
is the Banach space, and they endow some functions which are not necessarily
continuous the notion of computability as points in a space.
A function in a Banach space is computable if it is effectively approximatedby a computable sequence of continuous functions with respect to the norm of
the space. Pour-El and Richards have formulated this notion in terms of anaxiom set.
$x$

*Faculty of Science, Kyoto Sangyo University: yasugi@cc.kyoto-su.

$\mathrm{a}\mathrm{c}$

.jp.

85

Stimulated by [3], I and some of my colleagues have investigated various
frameworks in analysis for use in dealing with discontinuous functions which
nevertheless can be regareded as having some algorithmic attributes. Examples
of such frameworks are the Fr\’echet space, the metric space and the uniform
topological space. See [4], [2], [6], [12], [5], [9], [10], [1], [11], [13].
Note The bibliography at the end of this article is not meant at all comprehensive. In fact, I resetrict the references only to those in which I have myself been
involved or which I have closely followed. For other related works, the reader isinvited to the comprehensive list of references in the area at. html.
. informatik. fernuni-hagen.
http:$//\mathrm{w}\mathrm{w}\mathrm{w}$$\mathrm{d}\mathrm{e}/\mathrm{c}\mathrm{c}\mathrm{a}/\mathrm{p}\mathrm{u}\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}\dot{\mathrm{x}}\mathrm{o}\mathrm{n}\mathrm{s}/\mathrm{b}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}\mathrm{y}$Subsequently, I present a brief exposition of our specuiations on a simple andfunction. I will also mention the Rademacherfamiliar step function, thefunctions, a sequence of step functions, which are important in Walsh analysis.
These functions are simple and innocent looking, but are good examples indistilling the algorithmic features of discontinuous functions. If one can set up aframework to talk about the computability properties of such functions, one canapply it to many significant functions. There is another reason why I take up
these functions. Namely, step functions are essential tools for digital analysis,
and so it is important to discuss computability properties of such functions.
My belief is that examples to be used for analyzing certain properties be
simple and familiar looking, so that one needs not work hard to understand thefunctions themselves.
$\mathrm{G}\mathrm{a}\mathrm{u}\mathrm{f}3\mathrm{i}\mathrm{a}\mathrm{n}$2Preliminaries

We first quote from Sections 1 and 2 of [8] to supply with some preliminary
information.
In studies of algorithm in analysis, one puts the basis of considerations on
computable reals. Here a real number is said to be computable if there is awhich approximates and satisfies the following two
sequence of fractions
conditions.
.
(1) There is an algorithm which constructs the fractional sequence(That is, one can write a program which, for each natural number , assigns a)fractional number(2) There is an algorithm which measures the precision of approximation,(That is, one can write a program which, for each natural number , assigns asuch that for every natural number $m\geq N_{p}|x-r_{m}|\leq 1/2^{p}$natural number$x$$\{r_{n}\}$$x$$\{r_{\tau\iota}\}$$n$$r_{n}.$$p$$N_{p}$

holds.)

When the condition (2) holds, we say that if effectively approximated by. In general, we use the expression effective when a condition similar to (2)is satisfied.
One might say that a computable real number can be approximated byfractional numbers with guarantee of infinite precision.
$x$$\{r_{n}\}$86

A computable sequence of reals can also be defined in a similar manner. One
needs computability of a sequence of real numbers when one has to refer to thelimit.
The computability of a continuous real function on a compact interval can be
defined in a natural manner. There are several alternatives, but they are all moreor less the same. A real function (on a compact interval) is computable if (1)preserves the sequential computability, that is, for any input of a computablesequence of reals, its output by is also a computable sequence; (2) has arecursive modulus of uniform cotinuity.
The definition can easily be extended to fractional functions.
Computability on an open interval can be defined in terms of an approximation of the interval by a sequence of compact intervals and a modulus of uniform
continuity which is recursive in the approximating intervals.
$f$

$f$

$f$

$f$

As for the computability of a discontinuous function, one has to start with
speculation of what an effective approximation at a discontinuity means, andthere are several alternatives for it.
Typical and simple discontinuous functions which may contain some computational information are step functions (with computable jump points andcomputable values).
Here we will take up a very simple step function, the Gauiian function or
the integer part function, as an example, and propose some ways of dealing with
its computability properties. Indeed, this is a most exemplary case with respect
to which our problem can be distilled.
function can be defined as
The$\mathrm{G}\mathrm{a}\mathrm{u}\mathrm{f}3\mathrm{i}\mathrm{a}\mathrm{n}$$[x]=n$

if $n\leq x<n+1$

unless be an integer.
and hence the value can be determined byjudging
When is an integer, $x=n$ ? is usually undecidable (even for a computable ),and hence there is no general computation algorithm for $[x]$ .
In what sort of viewpoint can one discuss the computability of a function
which has such an attribute?
In Sections 2 and 3 of [9], this problem is discussed in detail. For explanation,
we quote Section 3 of [8]. In Sections 2 and 3 of [13], a similar problem is
discussed for the system of Rademacher functions.
$<\mathrm{a}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{e}$

$x$

$x$

$x$

Computing $[x]$3

Let be a computable real number and let us consider how to compute its value$[x]$ , the Gaussian of. For the sake of simplicity, we assume $x>0$ .
$x$

$x$

For $n=0,1,2,3,$ , keep asking $x<n?$ . (In fact, we compute with respect
which approximates ) One will
to a computable sequence of fractions
infallibly hit an satisfying $n<x<n+2$ .
If one is fortunate so that one hits an satisfying $n<x<n+1$ , then put$[x]=n$ and the computation halts.
$\cdots$$\{r_{m}\}$

$n$

$n$

$x.$

87

Otherwise, one checks$r_{\alpha(p)}<(n+1)-2^{p}\overline{1}$for $p=1,2,$ . ( is a recursive modulus of convergence ofto ) According to its answer, we define a sequence of integers
as follows.
While the answer is $No$ , put $N_{p}=n+1$ . Once the answer becomes Yes at, then put $N_{q}=n$ for all satisfying $q\geq p$ .
$\cdots$$\{r_{n}\}$$\alpha$$x.$$\{N_{p}\}$

$p$

$q$

The sequenceis well-defined and recursive, and it can be classicallyshown that, if $N_{p}=n+1$ holds for all , then the limit of the sequence is $n+1$ ;otherwise, the limit is . In either case, the sequence approximates the value$[x]$ effectively.
Now, we have to be careful here to note that it is not decidable whether thelimit is or $n+1$ . It is true that one of the two cases definitely holds, the limit
the value $[x]$ , and there a recursive modulus of convergence. Only we do
not know which case holds.
This undecidability indicates that, although there is a computation algorithm for each , it does not guarantee a master program to compute $[x]$ . Indeed, there is a computable sequence of real numbers whose values do not form
a computable sequence of reals.
As an example of a sequence of step functions, I have taken up the Rademacher, which is defined as follows.
function system$\{N_{p}\}$

$p$

$n$

$n$

$is$

$is$

$x$

$\{\phi_{n}\}$$\phi_{n}(x)=\{$’$-11,$$x \in x\in[\frac{\frac{2i}{3_{i2}^{n}}\dotplus_{1}}{n},\frac{n2i+21)}{2^{n}})[\frac{2i+}{2}$$2^{n-1}-1$ .
where $i=0,1,2,$
As for the computation of this sytem, for any single, computable real number$x\in[0,1)$ , the sequence of function values atforms a computable sequence ofreals ([13]).
$\cdots,$$x$4Functional approach

In order to regard a (step) function as a computable element in a functional
space, one has to select a space appropriately. For the function $[x]$ , we havechosen two Fre’chet spaces. One is to view the function as a sequence of values(at integer points) and the other is to view it as a locally integrable function.
We quote from Sections 4 and 5 of [8].
Taking this into account, for a step function whose jump points are integers, we identify with the sequence. Let
denote the spaceof integer-indexed number sequences.
For an element in this space,
$f$

$f$

$\{f(n)\}_{0,\pm 1,\pm 2},\cdots$$R^{\mathrm{Z}}$$x=\{\cdots, \xi_{-k}, \cdots, \xi_{-1}, \xi_{0}, \xi_{1}, \cdots, \xi_{k}, \cdots, \}$,88define a sequence of semi-norms by(1)$p_{m}(x)= \max\{|\xi_{k}|:|k|\leq m\}$Then the space becomes a Fr\’echet space.
denote the family of the right-continuous stepOn the other hand, letfunctions whose jump points are integers. Then$\Sigma$(2)$q_{m}(f)=p_{m}(\{f(k)\})$

becomes a sequence of semi-norms. A function onmined by the values at integer points.

$\Sigma$can be completely deter-. In the latter
is isomorphic with
It is obvious thatspace, a computable element is a (an integer-indexed) computable sequence ofreals. So, it will be natural to define a computable element of to be the one
whose sequence of values is computable.
The Gaussian function is certainly a -function, and the sequence of its
is computable. So, it is computable in the sense above.
values
One can draw a graph of the Gaussian function according to the idea above.
That is, in the $x-y$ plane, mark the point $(n, n)$ (or a vertical arrow from $(n, 0)$
to $(n, n))$ for each integer , and then draw an arrow from that point (from thetip of the arrow) to the right in a manner that its tip does not reach the next
point $(n+1, n+1)$ .
We next proceed to the space of locally integrable functions.
a R\’echet space with the sequence of semi-norms$\langle \mathrm{R}^{\mathrm{Z}}, \{p_{m}\}\rangle$$\langle\Sigma, \{q_{m}\}\rangle$$\Sigma$$\Sigma$$\{n\}_{n}$$n$$p_{k}(f)= \int_{[-k,k]}|f|dx$, or Cfor short.
Let us denote this space with
example the family of step
for
,
space
take
As a generating set of thefunctions whose jump points and values are rationals and which have compact
supports of integer end-points. One can also take the sequence of monomials
as a generating set.
1, $x,$
putable if it is effectively
Similarly, a function in can be defined to beapproximated by a recursive enumeration of rational coefficient polynomials. The sequence of monomials can therefore
with respect to the semi-norms
be regarded as an effectively generating set in .
The family of step functions as above can also be an effective generating set.
The Gaussian function can be effectively approximated by such step functions, and so it must be computable in this space.
In order to draw a graph of the Gaussian function according to this idea,
one would draw an open segment between two integer points (and put a whitecircle at the integer point if desired). A white circle indicates that one needs
not take into account the value there.
For the Rademacher function system, we employ the Banach space of pintegrable functions on $[0,1]$ for any computable number $1\leq p<\infty$ .
$\langle L_{loc}^{1}(\mathrm{R}), \{p_{k}\}\rangle$$\mathcal{L}$$x^{2},$ $x^{3},$$\cdots,$$x^{n},$$\cdots$$\mathrm{c}\mathrm{o}\dot{\mathrm{m}}$$\mathcal{L}$$\{p_{k}\}$$\mathcal{L}$

$p,$

89

5Uniform topological space and computability
So far, the functions in question were defined on sets of real numbers, in which
the usual distance metric is available. In [1], another metric for the interval$[0,1)$ has been used in order to discuss the computability properties of theRademacher and Walsh function systems.
In working with computability problems of real-valued step functions, however, one finds that the metric of the domain is not indispensable. It is only
the uniformity of the topology as well as the computability structure of thecodomain that are essential. For this reason, it is worth the effort to find out
how we can work with computability properties of some real-valued functions
from a uniform topological space (with countable index set). Although a uniform
topological space with a countable index set can be converted to a metric space(and certainly vice versa), and also that two kinds of convergence are equivalent,
it is important how things look like in the uniform topology directly so that thecircumstances under which a function becomes computable will become clear.
A computability structure on a uniform topological space and its applications
will be explained below very, very briefly.
An effective uniform topological space is a uniform topological space in which
the axioms of open basis are effectivized. The computability structure on sucha space is defined by three axioms.
We will quote from [11] for thesdefinitions of an effective uniform topologicalspace and a computability structure on it.
A uniform topology
on $X$ is called an effective uniform topology if there
are recursive functions
which satisfy the following.
For every $n,$
and every $x\in X,$ $V_{\alpha_{1}(n,m)}(x)\subset V_{n}(x)\cap V_{m}(x)$ (effective$\{V_{n}\}$$\alpha_{1},$$\alpha_{2},$$\alpha_{3}$$m\in \mathrm{N}$$A_{3})$.

For every
and every $y\in X,$ $x\in V_{\alpha_{2}(n)}(y)$ implies $y\in V_{n}(x)$(effective).
For every
and every $x,$ $z\in X,$ $x\in V_{\alpha_{3}(n)}(y),$implies$x\in V_{n}(z)$ (effective).
A double sequence
from $X$ is said to effectively converge to a sequence
if there is a recursive function satisfying$n\in \mathrm{N}$$x,$$A_{4}$$n\in \mathrm{N}$$y\in V_{\alpha_{3}}(z)$$y,$$A_{5}$$\{x_{l,k}\}$$\{x_{l}\}$$\beta$$\forall n\forall l\forall k\geq\beta(l, n)(x_{l,k}\in V_{n}(x_{l}))$Letbe a family of sequences from X. (As usual, we include multiple
sequences, such as double sequences, triple sequences, when we talk about sequences.)is called a computability siructure if it satisfies the following.
Cl: (Non-emptiness) is nonempty.
C2: ( -enumeration) If $\{x_{k}\}\in S$ andis a recursive function, then
.
$S$

$S$

$S$

${\rm Re}$$\{x_{\alpha(i)}\}_{i}\in S$$\alpha$90

is a sequence from $X$ , and if
belongs to $S,$
C3: (Limit) If
converges toeffectively, then $\{x_{l}\}\in S$ . That is, is closed with respect
to effective convergence.
A sequence belonging to is called a computable sequence. An element of$X$ is called computable if the sequence $\{x, x, \cdots\}$ is computable.
The tree topology of a binary tree is a uniform topology of clopen sets, andthe space is compact. The family of all the recursive paths in the binary tree
forms a computability structure. Furthermore, an effective enumeration of all
the eventually zero paths is an effective separating set.
As an application, we can show that the system of Rademacher functions
defined on the binary tree forms a uniformly computable sequence of functions.
The next space of our concern, denoted by $A$ is an amalgamation of thediscrete space of integers and the union of all the open intervals with integer
end points with relativized open interval topology. As a set, is identical withthe set of real numbers, but it becomes a uniform topological space.
We can also show that the amalgamated space is not complete. In regards
to the computability structure, however, we know that it is effectively complete
and, in particular, $A$ is effectively equi-totally bounded.
The function $[x]$ is continuous in $A$ .
The set of computable sequences of $A$ is defined as follows. Let
be aseuqnece of the set, where( is either
or for some ) .
is called computable if there is a double sequence of rationals
such that, andis a computable sequence in the usual sense, for all
converges effectively toin the usual topology of R.
The computable sequences in the sense above form a computability structure
for $A$ , and the uniform computability of $[x]$ with respect to this computability
structure follows.
$\{x_{l,k}\}$$\{x_{l,k}\}$$\{x_{l}\}$$S$$\{x_{l}\}$

$S$

$A$

$\{x_{n}\}$$x_{n}\in J_{n}$$\mathrm{A}_{\mathrm{R}}$$J_{n}$$\mathrm{J}^{\mathrm{Z}}$$k$$\mathrm{J}^{k}$$\{x_{n}\}$$\{r_{nl}\}$$\{r_{nl}\}$$lr_{nl}\in \mathrm{J}_{\mathrm{n}}$$\{r_{nl}\}$$\{x_{n}\}$References[1] T.Mori, On the computability of Walsh functions, manuscript.
[2] T.Mori,Y.Tsujii and M.Yasugi, Computability structure on metric spaces,
Combinatorics, Complexity and Logic (Proceedings of DMTCS’96), ed. by
Bridges et. al, Springer (1996),351-362.

[3] M.B.Pour-El and J.I.Richards, Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer-Verlag, 1989.
[4] M.Washihara, Computability and Fr\’echet space, Mathematica Japonica,
42 (1995),1-13.

[5] M.Washihara, Computability and tempered distributions, ibid.,50,1 (1999),1-

7.
[6] M.Washihara and M.Yasugi, Computability and metrics in a Fr\’echet space,ibid., 43(1996), 1-13.

91[7] M.Yasugi, Computability of discontinuous functions: a report at Dagstuhl
seminar, http:.
$//\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{k}\mathrm{y}\mathrm{o}\mathrm{t}\mathrm{o}- \mathrm{s}\mathrm{u}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\sim_{\mathrm{y}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{g}\mathrm{i}}/\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}$[8] M.Yasugi, Computability of discontinuous functions, Manuscript (presented
at Josai University, January 2000).
[9] M. Yasugi, V. Brattka and M. Washihara, Computability properties of the Gauf3ian function, Manuscript (1999): http://www.kyoto.
$\mathrm{s}\mathrm{u}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\sim_{\mathrm{y}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{g}\mathrm{i}}/\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}$[10] M.Yasugi, T.Mori and Y.Tsujii, Effective Properties of Sets and Functionsin Metric Spaces with Computability Structure, Theoretical Computer Science, 219(1999), 467-486.

[11] M.Yasugi, Y.Tsujii and T.Mori, Uniform topological space and computability of some discontinuous functions, Manuscript(2000): http://www.kyoto$\mathrm{s}\mathrm{u}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\sim_{\mathrm{y}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{g}\mathrm{i}}/\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}$.

[12] M.Yasugi and M.Washihara, Computability structures in analysis, (inJapanese), Sugaku (MSJ),vol.50, no.2 (1998),130-148.
[13] M.Yasugi and M.Washihara, Rademacher functions and computability, Manuscript. (Abstract for Ito Conference 00: http://www.kyoto.)$\mathrm{s}\mathrm{u}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\sim_{\mathrm{y}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{g}\mathrm{i}}/\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}$