In his classic book Computational Complexity, Papadimitriou writes (page 59) that Undecidability is in some sense the most lethal form of complexity. I’ve just come across a paper with a very interesting remark along the same lines: Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination by A. Carbone and S. Semmes, [...]
Archive for December 2010
Undecidability in terms of complexity
13 December 2010Position paper: Computing with LEGO
10 December 2010There 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 eclipses) made of LEGO, again by Andrew Carol: (Thanks to CompSciFact on Twitter for the [...]
On a philosophical quest
2 December 2010This was originally posted as an answer to the question Why go to theoretical computer science/research? on the Theoretical Computer Science Stack Exchange website. 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 [...]
