Notes on Computable Analysis

作者：Porter Michelle^*; Day Adam; Downey Rodney

来源：Theory of Computing Systems, 2017, 60(1): 53-111.

DOI：10.1007/s00224-016-9732-y

• Computable analysis
• Computable real
• Computable real-valued function
• Markov computable
• Borel computable
• Type II computable
• Located sets
• Darboux property
• Blaschke Selection Theorem
• Convex sets

Computable analysis has been part of computability theory since Turing's original paper on the subject (Turing, Proc. London Math. Sc. 42:230-265, 1936). Nevertheless, it is difficult to locate basic results in this area. A first goal of this paper is to give some new simple proofs of fundamental classical results (highlighting the role of classes). Naturally this paper cannot cover all aspects of computable analysis, but we hope that this gives the reader a completely self-contained ingress into this area. A second goal is to use tools from effective topology to analyse the Darboux property, particularly a result by SierpiA"ski, and the Blaschke Selection Theorem.

• 出版日期2017-1