Plottable Real Number Functions and the Computable Graph Theorem
Journal Article
2008
Permanent link to this Item
Authors
Journal Title
SIAM Journal on Computing
Link to Journal
Journal ISSN
Volume Title
Publisher
Publisher
Faculty
License
Series
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 nonuniform 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 is always computable, the inverse direction fr...
Description
Reference:
Brattka, V. 2008. Plottable Real Number Functions and the Computable Graph Theorem. SIAM Journal on Computing. 38(1):303 - 328. http://hdl.handle.net/11427/34759