Quantitative continuity and computable analysis in Coq We give a number of formal proofs of theorems from the field of computable analysis. Many of our results specify executable algorithms that work on infinite inputs by means of operating on finite approximations and are proven correct in the sense of computable analysis. The development is done in the proof assistant Coq and heavily relies on the Incone library for information theoretic continuity. This library is developed by one of the authors and the paper can be used as an introduction to the library as it describes many of its most important features in detail. While the ability to have full executability in a formal development of mathematical statements about real numbers and the like is not a feature that is unique to the Incone library, its original contribution is to adhere to the conventions of computable analysis to provide a general purpose interface for algorithmic reasoning on continuous structures. The results that provide complete computational content include that the algebraic operations and the efficient limit operator on the reals are computable, that certain countably infinite products are isomorphic to spaces of functions, compatibility of the enumeration representation of subsets of natural numbers with the abstract definition of the space of open subsets of the natural numbers, and that continuous realizability implies sequential continuity. We also formalize proofs of noncomputational results that support the correctness of our definitions. These include that the information theoretic notion of continuity used in the library is equivalent to the metric notion of continuity on Baire space, a complete comparison of the different concepts of continuity that arise from metric and representedspace structures and the discontinuity of the unrestricted limit operator on the real numbers and the task of selecting an element of a closed subset of the natural numbers.

Expressibility in the Lambda Calculus with mu We address a problem connected to the unfolding semantics of functional programming languages: give a useful characterization of those infinite lambdaterms that are lambda_letrecexpressible in the sense that they arise as infinite unfoldings of terms in lambda_letrec, the lambdacalculus with letrec. We provide two characterizations, using concepts we introduce for infinite lambdaterms: regularity, strong regularity, and bindingcapturing chains. It turns out that lambda_letrecexpressible infinite lambdaterms form a proper subclass of the regular infinite lambdaterms. In this paper we establish these characterizations only for expressibility in lambda_mu, the lambdacalculus with explicit murecursion. We show that for all infinite lambdaterms T the following are equivalent: (i): T is lambda_muexpressible; (ii): T is strongly regular; (iii): T is regular, and it only has finite bindingcapturing chains.  :123,define regularity and strong regularity for infinite lambdaterms as two different generalizations of regularity for infinite firstorder terms: as the existence of only finitely many subterms that are defined as the reducts of two rewrite relations for decomposing lambdaterms. These rewrite relations act on infinite lambdaterms furnished with a marked prefix of abstractions for collecting decomposed lambdaabstractions and keeping the terms closed under decomposition. They differ in how vacuous abstractions in the prefix are removed.  :199,report accompanies the article with the same title for the proceedings of the conference RTA 2013, and mainly differs from that by providing the proof of the characterization of lambda_muexpressibility with bindingcapturing chains.