Reseña: A formalisation of metric spaces in HOL Light

Se ha publicado un artículo de razonamiento formalizado en HOL Light sobre topología titulado A formalisation of metric spaces in HOL Light.

Su autor es Marco Maggesi (de la Univ. de Florencia en Italia).

Su resumen es

We present a computer formalisation of metric spaces in the HOL Light theorem prover. Basic results of the theory of complete metric spaces are proved. A simple decision procedure for the theory of metric space is implemented.

El trabajo se ha presentado en CICM 2015 (the 8th Conference on Intelligent Computer Mathematics).

Reseña: Formalizing divisibility rules as a student case study

Se ha publicado un artículo de razonamiento formalizado en Mizar sobre aritmética titulado Formalizing divisibility rules as a student case study.

Su autor es Adam Naumowicz (de la Univ. de Białystok en Polonia).

Su resumen es

We would like to present some results of a student case study administered as a part of an interactive theorem proving elective course for computer science students. The students’ task was to prove in Mizar the divisibility rules for selected primes based on the decimal representation of natural numbers. The formalized proofs were quite elementary, so a project like this could be carried out by a group of students without particularly strong mathematical background. In this paper we give a short overview of definitions that had to be introduced for the case study and present the way the divisibility rules were eventually formulated by the students. After that we discuss an example of a more interesting proof case, i.e. the divisibility by 11 rule.

El trabajo se ha presentado en CICM 2015 (the 8th Conference on Intelligent Computer Mathematics).

Reseña: How functional programming mattered

Se ha publicado un artículo sobre el estado de la programación funcional titulado How functional programming mattered

Sus autores son

Su resumen es

In 1989 when functional programming was still considered a niche topic, Hughes wrote a visionary paper arguing convincingly “why functional programming matters“. More than two decades have passed. Has functional programming really mattered? Our answer is a resounding “Yes!”. Functional programming is now at the forefront of a new generation of programming technologies, and enjoying increasing popularity and influence. In this paper, we review the impact of functional programming, focusing on how it has changed the way we may construct programs, the way we may verify programs, and fundamentally the way we may think about programs.

El trabajo se ha publicado en National Science Review.

Reseña: A formal verification of the theory of parity complexes

Se ha publicado un artículo de razonamiento formalizado en Coq sobre topología algebraica titulado A formal verification of the theory of parity complexes.

Su autor es Mitchell Buckley (de la Macquarie University en Australia).

Su resumen es

We formalise, in Coq, the opening sections of Parity Complexes up to and including the all important excision of extremals algorithm. Parity complexes describe the essential combinatorial structure exhibited by simplexes, cubes and globes, that enable the construction of free ω-categories on such objects. The excision of extremals is a recursive algorithm that presents every cell in such a category as a composite of atomic cells, this is the sense in which the ω-category is free. Due to the complicated multi-dimensional nature of this work, the detail of definitions and proofs can be hard to follow and verify. Indeed, some corrections [Street1994] were required some years following the original publication. Our formalisation verifies that all cases of each result operate as stated. In particular, we indicate which portions of the theory can be proved directly from definitions, and which require more subtle and complex arguments. By identifying results that require the most complicated proofs, we are able to investigate where this theory might benefit from further study and which results need to be considered most carefully in future work.

El código de las correspondientes teorías en Coq se encuentra aquí.

Reseña: Higman’s lemma and its computational content

Se ha publicado un artículo de razonamiento formalizado en Minlog sobre combinatoria titulado Higman’s lemma and its computational content.

Sus autores son

Su resumen es

Higman’s Lemma is a fascinating result in infinite combinatorics, with manyfold applications in logic and computer science. It has been proven several times using different formulations and methods. The aim of this paper is to look at Higman’s Lemma from a computational and comparative point of view. We give a proof of Higman’s Lemma that uses the same combinatorial idea as Nash-Williams’ indirect proof using the so-called minimal bad sequence argument, but which is constructive. For the case of a two letter alphabet such a proof was given by Coquand. Using more flexible structures, we present a proof that works for an arbitrary well-quasiordered alphabet. We report on a formalization of this proof in the proof assistant Minlog, and discuss machine extracted terms (in an extension of Gödel’s system T) expressing its computational content.