What did Alan Turing have in mind when he conceived his universal computing machine? One could speculate that his train of thoughts was like this: I can simulate any of my machines (there’s experimental evidence, and of course I defined them to work like people doing maths on a piece of paper). I’ve already formulated [...]
Archive for July 2010
The universal Turing machine
23 July 2010Hilbert’s troubles
21 July 2010While 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. *** david (daboss@uni-göttingen.de) has joined #logic <david> plz, solve integer eqns and prove completness of teh arithmetics <kurt> just 1 sec, brb * kurt [...]
On the length of proofs (episode II)
12 July 2010Last 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 [...]
How I learned to stop worrying about Turing completeness and love primitive recursion
11 July 2010The 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. The PR functions are exactly the functions that can be computed by using [...]
Solving PP-complete problems using P systems
5 July 2010Today 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. The venue of CMC11 is Friedrich-Schiller-Universität in Jena, Germany. This university has some slightly notable alumni, such as Rudolf [...]
On the length of proofs
4 July 2010One of the most amazing facts about (un)computability is the existence of functions f : ℕ → ℕ that grow faster than any recursive function, that is, for all computable g : ℕ → ℕ we have . The most common function of this kind is the busy beaver function, described by Tibor Radó in [...]
A cartoon about the halting problem
3 July 2010Bob 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 [...]
