https://ub-deposit.fernuni-hagen.de/receive/mir_mods_00000761https://ub-deposit.fernuni-hagen.de/servlets/MCRFileNodeServlet/mir_derivate_00000848/Brattka_Plottable_2003.pdfhttps://ub-deposit.fernuni-hagen.de/rsc/thumbnail/mir_mods_00000761.png
book
book
text
300
text
series
Informatik-Berichte
Hagen
FernUniversität in Hagen
627310-5
en
de
his
Plottable real number functions and the computable graph theorem
urn:nbn:de:hbz:708-dh3122
aut
Author
Brattka, Vasco
121389847
Brattka
Vasco
Hagen
FernUniversität in Hagen
2003
en
004
Computable real number functions
recursive graphs
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.
28 Seiten
mir_mods_00000761https://ub-deposit.fernuni-hagen.de/receive/mir_mods_00000761