6 December 2023 • 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. [read more…]

28 June 2020 • 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️). [read more…]

17 February 2012
•
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.
[read more…]

13 August 2011 • I finally took the time to read Scott Aaronson’s new paper Why philosophers should care about computational complexity (there’s a post about it with lots of comments on his blog). [read more…]

19 February 2011
•
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)?
[read more…]

4 January 2011 • A short post, just because I want this on my blog: a beautiful video and song by Vi Hart (take a look at the rest of her website, it’s amazing). Epsilon greater-than to you too. [read more…]

13 December 2010
•
In his classic book *Computational Complexity*, Papadimitriou writes (page 59) that *Undecidability is in some sense the most lethal form of complexity*.
[read more…]

10 December 2010 • There is a LEGO Turing machine, constructed at Aarhus University (see here for more information): [read more…]

2 December 2010 • 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. [read more…]

15 August 2010 • 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. [read more…]

9 August 2010 • The news seems to have originated from a post on Greg Baker’s blog. The author of the claimed proof of P ≠ NP is Vinay Deolalikar, principal research scientist at HP Labs (though “[t]his work was pursued independently of [his] duties as a HP Labs researcher, and without the knowledge of others”). Judging from his past publication history, we can’t afford to immediately dismiss the author as a crank this time. [read more…]

4 August 2010 • Those of you who have been following me on Twitter may have noticed that, lately, I seem to be tormented by scientifico-philosophical questions related to Turing machines and Turing’s thesis. [read more…]

23 July 2010 • What did Alan Turing have in mind when he conceived his universal computing machine? [read more…]

21 July 2010 • While digging in the early computability literature, I found a precious and long forgotten account of the history of Hilbert’s problems. I’m proud to present my discovery to the scientific community. [read more…]

12 July 2010 • Last week I wrote a post about arithmetical theorems having very long proofs, and linked to an article on the SEP for the details. Today, me and my colleague Luca Manzoni realised that there is a much simpler proof; it is essentially the same proof described by Scott Aaronson for the uncomputability of the busy beaver function, and it holds for any undecidable, recursively axiomatisable theory $T$ (that is, if there exists a recursive set of axioms generating the sentences of the theory, but no decision procedure for checking whether a sentence is a theorem). [read more…]

11 July 2010 • The primitive recursive functions are a class of computable arithmetic functions with a reasonably natural definition. They do not exhaust all computable functions (e.g., Ackermann’s function grows faster than any PR function). Here is a list of reasons to like them anyway. [read more…]

5 July 2010 • Today we submitted the final version of our paper P systems with elementary active membranes: Beyond NP and coNP, which has been accepted for the Eleventh International Conference on Membrane Computing, taking place on 24–27 August. [read more…]

4 July 2010
•
One of the most amazing facts about (un)computability is the existence of functions $f \colon \mathbb{N} \to \mathbb{N}$ that *grow faster than any recursive function*, that is, for all computable $g \colon \mathbb{N} \to \mathbb{N}$ we have
[read more…]

3 July 2010 • Bob is a programmer and software engineer, developing automated software testing utilities for his company. However, his manager Eve wants to fire him and, in order to get an excuse, she assigns him a very hard task: developing a tool to check the termination of programs. Eve, for some reason, seems to know that he’s doomed to failure. [read more…]