Can I read Relatively Recursive Reals and Real Functions on EtoBox?

Relatively Recursive Reals and Real Functions by Chun-Kuen Ho is a Computer Science article available to read on EtoBox.

What is Relatively Recursive Reals and Real Functions about?

Intuitively, a real number is recursive if we can get as accurate an approximation as we like, using a mechanical procedure such as a Turing machine. A real mnction is recursive if its value at a point x in its domain can be approximated effectively given an approximation to x. However, since there are only countably many Turing machines, there must be uncountably many non-recursive reals and functions. In this paper, we study some of these non-recursive reals and functions using a more recursion theoretic approach, via the degree of unsolvability. In particular, we are interested in reals and real functions that are relatively recursive in 0', where 8' is the jump of the recursive degree 8. Inspired by the Shoenfield Limit Lemma, we show that a real is @'-recursive if and only if it is the limit of a recursive sequence of rationals. We then give three characterizations of a @'-recursive function which are stated in terms of Turing machine, uniform convergence, and sequential computability with uniform continuity. A proof of their equivalence using a finite injury priority argument is given. With the new definitions, we can now give an upper bound to the difficulty of some uncomput

Who reads Relatively Recursive Reals and Real Functions?

Author

Chun-Kuen Ho

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

1999

Language

EN

Field

Computer Science (Physical Sciences)