
Quantitative continuity and computable analysis in Coq
We give a number of formal proofs of theorems from the field of computab...
read it

A recursion theoretic foundation of computation over real numbers
We define a class of computable functions over real numbers using functi...
read it

Randomized Computation of Continuous Data: Is Brownian Motion Computable?
We consider randomized computation of continuous data in the sense of Co...
read it

Constructive Domains with Classical Witnesses
We develop a constructive theory of continuous domains from the perspect...
read it

Intensional and Extensional Semantics of Bounded and Unbounded Nondeterminism
We give extensional and intensional characterizations of nondeterministi...
read it

Abstract Geometrical Computation 11: Slanted Firing Squad Synchronisation on Signal Machines
Firing Squad Synchronisation on Cellular Automata is the dynamical synch...
read it

Data
In this article, the data notion is mathematically conceptualized as typ...
read it
Continuous and monotone machines
We investigate a variant of the fuelbased approach to modeling diverging computation in type theories and use it to abstractly capture the essence of oracle Turing machines. The resulting objects we call continuous machines. We prove that it is possible to translate back and forth between such machines and names in the standard function encoding used in computable analysis. Put differently, among the operators on Baire space, exactly the partial continuous ones are implementable by continuous machines and the data that such a machine provides is a description of the operator as a sequentially realizable functional. Continuous machines are naturally formulated in type theories and we have formalized our findings in Coq. Continuous machines, their equivalence to the standard encoding and correctness of basic operations are now part of Incone, a Coq library for computable analysis. While the correctness proofs use a classical metatheory with countable choice, the translations and algorithms that are proven correct are all fully executable. Along the way we formally prove some known results such as existence of a selfmodulating moduli of continuity for partial continuous operators on Baire space. To illustrate their versatility we use continuous machines to specify some algorithms that operate on objects that cannot be fully described by finite means, such as real numbers and functions. We present particularly simple algorithms for finding the multiplicative inverse of a real number and for composition of partial continuous operators on Baire space. Some of the simplicity is achieved by utilizing the fact that continuous machines are compatible with multivalued semantics. We also connect continuous machines to the construction of precompletions and completions of represented spaces, topics that have recently caught the attention of the computable analysis community.
READ FULL TEXT
Comments
There are no comments yet.