2005/08/31 by Martin Ziegler · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Logic, programming, and type systems #cs.CC #cs.LO #semigroups and automata theory
paper · pdf · doi:10.1007/s00224-006-1343-6
published as pp.177-206 in Theory of Computing Systems vol.41 (2007) · previous version (extended abstract) has appeared in pp.562-571 of "Proc. 1st Conference on Computability in Europe" (CiE'05), Springer LNCS vol.3526
arxiv created 2006/02/22 · openalex publication_date 2007/05/04 · arxiv updated 2010/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
By the sometimes so-called 'Main Theorem' of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of HYPERcomputation allow for the effective evaluation of also discontinuous f:R->R. More precisely the present work considers the following three super-Turing notions of real function computability: * relativized computation; specifically given oracle access to the Halting Problem 0' or its jump 0''; * encoding real input x and/or output y=f(x) in weaker ways also related to the Arithmetic Hierarchy; * non-deterministic computation. It turns out that any f:R->R computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation does provide the required power to evaluate for instance the discontinuous sign function.