Revising Type-2 Computation and Degrees of Discontinuity

Details Revising Type-2 Computation and Degrees of Discontinuity Revising Type-2 Computation and Degrees of Discontinuity

2006-07-26

arxiv.org/abs/cs/0607114v2

Electronic Notes in Theoretical Computer Science vol.167 (Jan.2007)

Computer Science

Logic in Computer Science

to appear in Proc. CCA'06

Scientific paper

10.1016/j.entcs.2006.08.015

By the sometimes so-called MAIN THEOREM of Recursive Analysis, every computable real function is necessarily continuous. Weihrauch and Zheng (TCS'2000), Brattka (MLQ'2005), and Ziegler (ToCS'2006) have considered different relaxed notions of computability to cover also discontinuous functions. The present work compares and unifies these approaches. This is based on the concept of the JUMP of a representation: both a TTE-counterpart to the well known recursion-theoretic jump on Kleene's Arithmetical Hierarchy of hypercomputation: and a formalization of revising computation in the sense of Shoenfield. We also consider Markov and Banach/Mazur oracle-computation of discontinuous fu nctions and characterize the computational power of Type-2 nondeterminism to coincide with the first level of the Analytical Hierarchy.

Affiliated with

Also associated with

No associations

Rating

Revising Type-2 Computation and Degrees of Discontinuity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Revising Type-2 Computation and Degrees of Discontinuity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Revising Type-2 Computation and Degrees of Discontinuity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-477539