|
|
Plottable real number functions and the computable graph theorem
Vasco Brattka, Informatik-Bericht 300, FernUniversität in Hagen, 2003
Abstract
The Graph Theorem of classical recursion theory states that a total function
on the natural numbers is computable, if and only if its graph is recursive.
It is known that this result can be generalized to real number functions
where it has an important practical interpretation: the total computable real
number functions are precisely those which can be effectively plotted with any
given resolution. We generalize the Graph Theorem to appropriate partial real number
functions and even further to functions defined on certain computable metric spaces.
Besides the non-uniform version of the Graph Theorem which logically relates computability
properties of the function and computability properties of its graph, we also discuss the
uniform version: given a program of a function,
can we algorithmically derive a description of its graph? And, vice versa,
given a description of the graph, can we derive a program of the function?
While the passage from functions to graphs always is computable, the inverse
direction from graphs to functions is problematic and
it turns out that the answers to the uniform and the non-uniform questions do not
coincide. We prove that in both cases certain topological and computational properties
(such as compactness or effective local connectedness)
are sufficient for a positive answer and we provide counterexamples
which show that the corresponding properties are not superfluous.
Additionally, we briefly discuss the special situation of the linear case.
Electronical Versions