Nondeterministic sorting

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…]

The semiring of dynamical systems

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…]

Nash beats Gödel: On the history of complexity and cryptography

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…]

Do waterfalls play chess? and other stories

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…]

Time is unpredictable

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…]

Merry Christmath!

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…]

Undecidability in terms of complexity

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…]

Position paper: Computing with LEGO

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

On a philosophical quest

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…]

Developments in Language Theory 2010: Where tetration has lease

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…]

A relatively serious proof that P ≠ NP?

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…]

Karl Popper and Turing’s thesis

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…]

The universal Turing machine

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

Hilbert’s troubles

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…]

On the length of proofs (episode II)

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…]

How I learned to stop worrying about Turing completeness and love primitive recursion

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…]

Solving PP-complete problems using P systems

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…]

On the length of proofs

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…]

A cartoon about the halting problem

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…]