Lately I’ve been thinking about computational effects *in general*, i.e., what is the structure of the “space of all computational effects”. We know very little about this topic. I am not even sure we know what “the space of all computational effects” is. Because Haskell is very popular and in Haskell computational effects are expressed as monads, many people might think that I am talking about the space of all monads. But I am not, and in this post I show two computational effects which are not of the usual Haskell monad kind. They should present a nice programming challenge to Haskell fans. Continue reading Not all computational effects are monads

# Category Archives: Computation

# Exact real arithmetic in Haskell

*HERA* is an implementation of exact real arithmetic in Haskell using the approach by Andrej Bauer and Iztok Kavkler, see these and these slides. It uses the fast multiple precision floating point library MPFR. Download source, and see documentation and examples of usage at my home page.

[*Note by Andrej:* this is a guest post by AleÅ¡ Bizjak, a first-year student of mathematics at my department. I am very proud of the excellent work he did on his summer project.]

# Efficient computation with Dedekind reals

Two versions of this talk were given at Computability and complexity in analysis 2008 and at Mathematics, Algorithms and Proofs 2008.

Joint work with Paul Taylor.

**Abstract:** Cauchy’s construction of reals as sequences of rational approximations is the theoretical basis for a number of implementations of exact real numbers, while Dedekind’s construction of reals as cuts has inspired fewer useful computational ideas. Nevertheless, we can see the computational content of Dedekind reals by constructing them within Abstract Stone Duality (ASD), a computationally meaningful calculus for topology. This provides the theoretical background for a novel way of computing with real numbers in the style of logic programming. Real numbers are defined in terms of (lower and upper) Dedekind cuts, while programs are expressed as statements about real numbers in the language of ASD. By adapting Newton’s method to interval arithmetic we can make the computations as efficient as those based on Cauchy reals.

**Slides:** slides-map2008.pdf (obsolete version: slides-cca2008.pdf)

**Extended abstract:** abstract-cca2098.pdf

# Representations of uncomputable and uncountable sets

Occasionally I hear claims that uncountable and uncomputable sets cannot be represented on computers. More generally, there are all sorts of misguided opinions about representations of data on computers, especially infinite data of mathematical nature. Here is a quick tutorial on the matter whose main point is:

It is

meaninglessto discuss representations of a set by a datatype without also considering operations that we want to perform on the set.

Continue reading Representations of uncomputable and uncountable sets

# Seemingly impossible functional programs

Andrej has invited me to write about certain surprising functional

programs.

The first program, due to Ulrich Berger (1990), performs exhaustive

search over the “Cantor space” of infinite sequences of binary

digits. I have included references at the end. A weak form of

exhaustive search amounts to checking whether or not a total predicate

holds for all elements of the Cantor space. Thus, this amounts to

universal quantification over the Cantor space. Can this possibly be

done algorithmically, in finite time?

Continue reading Seemingly impossible functional programs

# The Role of the Interval Domain in Modern Exact Real Arithmetic

With Iztok Kavkler.

**Abstract:** The interval domain was proposed by Dana Scott as a domain-theoretic model for real numbers. It is a successful theoretical idea which also inspired a number of computational models for real numbers. However, current state-of-the-art implementations of real numbers, e.g., Mueller’s iRRAM and Lambov’s RealLib, do not seem to be based on the interval domain. In fact, their authors have observed that domain-theoretic concepts such as monotonicity of functions hinder efficiency of computation.

I will review the data structures and algorithms that are used in modern implementations of exact real arithmetic. They provide important insights, but some questions remain about what theoretical models support them, and how we can show them to be correct. It turns out that the correctness is not always clear, and that the good old interval domain still has a few tricks to offer.

**Download slides:** domains8-slides.pdf

# Implementing real numbers with RZ

With Iztok Kavkler.

**Abstract:** RZ is a tool which translates axiomatizations of mathematical structures to program speciï¬cations using the realizability interpretation of logic. This helps programmers correctly implement data structures for computable mathematics. RZ does not prescribe a particular method of implementation, but allows programmers to write efficient code by hand, or to extract trusted code from formal proofs, if they so desire. We used this methodology to axiomatize real numbers and implemented the speciï¬cation computed by RZ. The axiomatization is the standard domain-theoretic construction of reals as the maximal elements of the interval domain, while the implementation closely follows current state-of-the-art implementations of exact real arithmetic. Our results shows not only that the theory and practice of computable mathematics can coexist, but also that they work together harmoniously.

Presented at Computability and Complexity in Analysis 2007.

**Download paper:** rzreals.pdf

**Download slides:** cca2007-slides.pdf

# Are small sentences of Peano arithmetic decidable?

Recently there has been a discussion (here, here, here, and here) on the Foundations of Mathematics mailing list about completeness of Peano arithmetic (PA) with respect to “small” sentences. Harvey Friedman made several conjectures of the following kind: “All true *small* sentences of PA are provable.” He proposed measures of smallness, such as counting the number of distinct variables or restricting the depth of terms. Here are some statistics concerning such statements.

Continue reading Are small sentences of Peano arithmetic decidable?

# König’s Lemma and the Kleene Tree

For the benefit of the topology seminar audience at the math department of University of Ljubljana, I have written a self-contained explanation of the Kleene tree, which is an interesting object in computability theory. For the benefit of the rest of the planet, I am publishing it here.

Continue reading König’s Lemma and the Kleene Tree

# Sometimes all functions are continuous

You may have heard at times that there are mathematicians who think that *all* functions are continuous. One way of explaining this is to show that all *computable* functions are continuous. The point not appreciated by many (even experts) is that the truth of this claim depends on what programming language we use.

Continue reading Sometimes all functions are continuous