Antonio E. Porreca

Celle-ci est une traduction non officielle de la lettre ouverte Stop the Uncritical Adoption of AI Technologies in Academia par Olivia Guest, Iris van Rooij et d’autres enseignant·es et chercheur·es aux Pays-Bas (2025), dont je suis évidemment signataire…

Can comparison-based sorting be sped up by using nondeterminism?

This is a post about something I’m working on at the moment, the semiring of finite, discrete time dynamical systems [1].

We know that Kurt Gödel, unhappy with having only completeness and incompleteness theorems named after him, also essentially invented the P vs NP question in a 1956 letter to John Von Neumann.

This post is inspired by the question Are runtime bounds in P decidable?

On the second day of Christmas my true love gave to me… The only even prime and the absolute value of e to the iπ.

In his classic book Computational Complexity, Papadimitriou writes (page 59) that Undecidability is in some sense the most lethal form of complexity.

There is a LEGO Turing machine, constructed at Aarhus University (see here for more information): There is also a LEGO Babbage difference engine built by Andrew Carol: Now we also have an Antikythera mechanism (an ancient Greek computer for predicting ecl…

This was originally posted as an answer to the question Why go to theoretical computer science/research?

Tomorrow I’m leaving for Canada, to attend the 14th International Conference on Developments in Language Theory, held at University of Western Ontario, London.