Browsing by Subject "Computable real number functions"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Open Access
    Plottable Real Number Functions and the Computable Graph Theorem
    (2008) Brattka, Vasco
    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...