Antonio E. Porreca’s Website
Estimé·es Universités des Pays-Bas, Universités néerlandaises de Sciences Appliquées et leurs respectifs Conseils d’Administration, Par la présente, nous prenons une position de principe contre la prolifération des soi-disant technologies de l’« IA » dans les universités.
Can comparison-based sorting be sped up by using nondeterminism? The answer turns out to be yes, at least when you are sorting large integers and taking their bit-lengths into account when counting operations.
This is a post about something I’m working on at the moment, the semiring of finite, discrete time dynamical systems [4]. Here’s a picture to get you interested, a portion of the multiplication table of dynamical systems (everyone loves this️).
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. Unfortunately, there were no blogs back then, so we had to wait until the 1980s to read it, and Cook, Karp & co. had to reinvent the question from scratch.
Is there an automatic procedure to determine whether a given Turing machine, *known* to be halting, operates within time bound $O(f)$ (assuming $f$ is a computable function)?
A short post, just because I want this on my blog: a beautiful [video](http://vihart.com/blog/gauss/) and [song](http://vihart.com/music/gauss12days.mp3) by [Vi Hart](http://vihart.com) (take a look at the rest of her website, it’s amazing). Epsilon greater-than to you too.
In his classic book [*Computational Complexity*](http://books.google.com/books?id=JogZAQAAIAAJ), 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):
One of the main reasons why I find the theory of computation (“my” branch of theoretical computer science) fascinating and worth studying is the following one: it provides us with a way to investigate some deep (and sometimes puzzling) philosophical questions.
Tomorrow I’m leaving for Canada, to attend the 14th International Conference on Developments in Language Theory, held at University of Western Ontario, London. You can find the programme here.