Plottable Real Number Functions and the Computable Graph Theorem

Simple item page
dc.contributor.authorBrattka, Vasco
dc.date.accessioned2021-10-08T07:16:03Z
dc.date.available2021-10-08T07:16:03Z
dc.date.issued2008
dc.description.abstractThe 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...
dc.identifier.apacitationBrattka, V. (2008). Plottable Real Number Functions and the Computable Graph Theorem. <i>SIAM Journal on Computing</i>, 38(1), 303 - 328. http://hdl.handle.net/11427/34759en_ZA
dc.identifier.chicagocitationBrattka, Vasco "Plottable Real Number Functions and the Computable Graph Theorem." <i>SIAM Journal on Computing</i> 38, 1. (2008): 303 - 328. http://hdl.handle.net/11427/34759en_ZA
dc.identifier.citationBrattka, V. 2008. Plottable Real Number Functions and the Computable Graph Theorem. <i>SIAM Journal on Computing.</i> 38(1):303 - 328. http://hdl.handle.net/11427/34759en_ZA
dc.identifier.issn0097-5397
dc.identifier.issn1095-7111
dc.identifier.ris TY - Journal Article AU - Brattka, Vasco AB - 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... DA - 2008 DB - OpenUCT DP - University of Cape Town IS - 1 J1 - SIAM Journal on Computing LK - https://open.uct.ac.za PY - 2008 SM - 0097-5397 SM - 1095-7111 T1 - Plottable Real Number Functions and the Computable Graph Theorem TI - Plottable Real Number Functions and the Computable Graph Theorem UR - http://hdl.handle.net/11427/34759 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/34759
dc.identifier.vancouvercitationBrattka V. Plottable Real Number Functions and the Computable Graph Theorem. SIAM Journal on Computing. 2008;38(1):303 - 328. http://hdl.handle.net/11427/34759.en_ZA
dc.language.isoeng
dc.publisher.departmentDepartment of Mathematics and Applied Mathematics
dc.publisher.facultyFaculty of Science
dc.sourceSIAM Journal on Computing
dc.source.journalissue1
dc.source.journalvolume38
dc.source.pagination303 - 328
dc.source.urihttps://dx.doi.org/10.1137/060658023
dc.subject.otherComputable real number functions
dc.subject.otherrecursive graphs
dc.titlePlottable Real Number Functions and the Computable Graph Theorem
dc.typeJournal Article
uct.type.publicationResearch
uct.type.resourceJournal Article
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
BrattkaVasco_Plottable_Real_2008.pdf
Size:
233.25 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Journal Articles