Plottable real number functions and the computable graph theorem

Brattka, Vasco GND

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 e®ectively plotted with any given resolution. We generalize the Graph Theorem to appropriate partial real number functions and even further to functions de¯ned 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 e®ective local connectedness) are su±cient for a positive answer and we provide counterexamples which show that the corresponding properties are not super°uous. Additionally, we brie°y discuss the special situation of the linear case.




Brattka, Vasco: Plottable real number functions and the computable graph theorem. Hagen 2003. FernUniversität in Hagen.


12 Monate:

Grafik öffnen


Nutzung und Vervielfältigung:
Alle Rechte vorbehalten


powered by MyCoRe