Blog

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

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

This post is inspired by the question Are runtime bounds in P decidable? asked by John Sidles on the CSTheory website, and the answer given by Emanuele Viola. [read more…]

Merry Christmath!

04 January 2011

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

Undecidability in terms of complexity

13 December 2010

In his classic book Computational Complexity, Papadimitriou writes (page 59) that [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

02 December 2010

This was originally posted as an answer to the question Why go to theoretical computer science/research? on the Theoretical Computer Science Stack Exchange website. [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?

09 August 2010

Note: I’ve stopped updating this post, now that I’ve collected quite a lot of comments. For the latest news, I suggest checking my tweets and, in particular, the Polymath wiki page (edited by more people than just yours truly). Maybe I’ll have another post in the next few days, if something shocking happens. [read more…]

Karl Popper and Turing’s thesis

04 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

05 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

04 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

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