## Archive for the ‘Computability’ category

### 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).

Summary: Aaronson, knowing that I’m writing my thesis at the moment, took the liberty of preparing an introduction for me. Thanks! I’m going to include it verbatim. (Just kidding of course, though I’m actually going to cite this paper extensively.)

The early work on computability had a lot of philosophical significance; actually, we can say that computability was born to answer a philosophical question, Hilbert’s Entscheidungsproblem. We all know that the answer turned out to be negative (or do we? See Section 3.1). Apparently computational complexity theory, the theory of computing under limited resources, didn’t turn out to be so popular among philosophers. That’s obviously a problem, and this paper tries to do something about it.

After a brief introduction to complexity theory (Section 2), Aaronson turns his attention to one of the main cornerstones of this field, which is also one the points that are usually criticised: the relevance of polynomial time, as opposed to exponential time. Here he argues that this distinction is at least as interesting as the distinction between computable and uncomputable. Section 3.3 contains an interesting question that can be answered using a complexity-theoretic argument: why would we call 243112609 − 1 (together with a proof of its primality) a “known” prime, while “the first prime large than 243112609 − 1” feels somehow “unknown”?

Section 4 is about the Turing test. This is the first time I see in print what Aaronson calls the “lookup-table argument” (though he cites Ned Block and others for it): namely, that there’s no doubt whatsoever that an abstract program P able to pass the Turing test does actually exist (you just need a huge but finite table of replies dependent on the previous history of the conversation). The only way to claim the impossibility of a machine passing the Turing test, apart from metaphysical arguments, requires addressing concerns such as the efficiency of P or the availability of enough space in the universe to store it. That is, complexity-theoretic questions.

Section 5, possibly the most interesting one, addresses the problem of logical omniscience. It is usually assumed that knowledge is closed under deduction rules; for instance, if I know A, and I know B, then I certainly know AB. But consider this: while I know enough basic axioms of maths, I surely don’t know that Fermat’s last theorem holds (except by trusting the mathematical community, which I usually do), even though it’s a mere deductive consequence of said axioms. We can argue that human beings do not possess the computational resources needed to actually achieve omniscience.

Section 6 is about a “waterfall argument” against computationalism. The idea is that the meaning of what a supposed computer actually computes is always imposed by someone looking at it, that is, it’s always relative to some external observer. I freely admit I am (was?) a fan of this argument, though I don’t necessarily see it as an attack to computationalism (I use to call this “computational relativism”, a term whose invention I claim, since Google returns zero hits for it ). According to some proponents, this leads to some “strange” consequences.

For instance, assume that we encode chess positions in the physical states of a waterfall, then take a look at some “final” state of the waterfall, and once again interpret that as a chess position. Can the waterfall be said to play chess? Aaronson argues that it is not so, unless the encoding (which is just a reduction from chess to computing the state of the waterfall) can be computed by a procedure requiring less resources than those needed to actually compute the state of the waterfall. But then a question emerges: does DNA compute Hamilton paths?

Section 7 describes how computational complexity can help to define what inductive inference is about, including Occam’s razor and the “new riddle of induction”.

Then, in Section 8, Aaronson argues that complexity theory might inspire some debate about the interpretation of quantum physics, particularly about the many-worlds interpretation.

In Section 9 new notions of proof, quite distinct from the usual notion of “formal” and “informal” proofs, are described. These are all based on complexity-theoretic and cryptographic results: interactive proof systems, zero-knowledge proofs, probabilistically checkable proofs.

Section 10 is about the difference between time and space. This is usually stated as “space can be reused, time cannot”. What if we allow time travel (i.e., closed timelike curves)? The assumption that PNP might suggest an argument for the impossibility of time travel, even assuming the validity of quantum physics.

Section 11 is about economics and game theory; here complexity theory can be useful to describe the behaviour of agents under bounded rationality assumptions.

Finally, in Section 12, Aaronson concludes that lots of philosophical problems seem to have interesting complexity-theoretic aspects. Several questions remain open, and the most important of those is still “If PNP, then how have humans managed to make such enormous mathematical progress, even in the face of the general intractability of theorem-proving?”.

I really hope that Aaronson’s paper spurs a lot of philosophical discussion involving and concerning complexity theory; I too believe there’s much to write about that.

### 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.

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)?

Predictably, the answer turns out to be negative.

Let’s start by formalising the problem. Assume M is the Turing machine whose runtime we’re interested in, and F is another TM computing the time bound f; then

L = {(M, F) : M halts within O(F) steps}.

Also let H be the halting problem:

H = {(M’, x) : M halts on input x}.

We can now define the function R(M’, x) = (M, F), where F computes n2 and M, on input y, behaves as follows:

• Simulate M’ on x for n = |y| steps.
• If M’ has already halted, then loop for n2 steps.
• Otherwise, loop for n3 steps.

We’re finally ready to prove our undecidability result.

Theorem. R is a many-one reduction from H to L.

Proof. Clearly R is a computable function, so we just need to show that

(M’, x) ∈ H ⇔ (M, F) ∈ L.

If (M’, x) ∈ H, that is, if M’ halts on input x, then it does so in k steps (for some k ∈ ℕ). Hence M runs in O(n2) time (notice that it runs in n3 time for |y| < k, but it’s only the asymptotic behaviour that matters for us). Thus (M, F) ∈ L.

On the other hand, if M’ does not halt on x, then M never completes its simulation, and the runtime for M is O(n3). Thus (M, F) ∉ L. □

Remark. We’ve actually proved a stronger statement, i.e., that the set of Turing machines running in O(n2) time is undecidable, even if we restrict the domain to machines halting in polynomial time. Similar undecidability results hold for an infinite class of time bounds.

### 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.

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, published in the Bulletin of the American Mathematical Society. This paper is about the length of proofs (a subject I’ve already touched upon here and here) without cut elimination.

On page 113, the authors write

By contrast [with propositional logic] in predicate logic one typically faces issues of algorithmic decidability or undecidability. That is, whether there is an algorithm at all that always gives the right answer, never mind how long it takes. The problem of determining whether a formula in predicate logic is a tautology is algorithmically undecidable. One can think of this as a matter of complexity, as follows. The tautologies in predicate logic of length at most n form a finite set for which one can choose a finite set of proofs. Let f(n) denote the maximum of the lengths of the shortest proofs of tautologies of length ≤ n. The fact that there is no algorithm for determining whether or not a formula is a tautology means that f(n) grows very fast, faster than any recursive function.

Essentially, this means that we can’t design an algorithm to solve an undecidable problem because the search space is too large, and the only way to somehow bound it is via a function that grows faster than any computable function. Compare this with the search space of the “witnesses” for an NP-complete problem: its size is exponential, which is too large to be explored efficiently (at least, as far as we know at the moment), but still small enough to make the problem decidable.

### On a philosophical quest

2 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.

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.

One of the founders of the theory of computation, Alan Turing, tried to pin down the meaning of “computing a function” for a human being equipped with a piece of paper, by giving a mathematical description of the process. I’m not the only one to think he was extremely successful, and Turing machines proved to be an accurate model of many other computing processes.

Now that we possess a class of mathematical objects describing computations, we can actually prove theorems about them, thus trying to uncover what can be computed, and how it can be computed; it immediately turned out that lots of perfectly legitimate functions cannot be computed at all, and that they can be classified according to a degree of uncomputability (some functions are just “more uncomputable” than others).

Some other guys, the first ones usually identified with Juris Hartmanis and Richard E. Stearns, tried to describe mathematically what it means for a function (resp., a problem) to be hard or easy to compute (resp., to solve). There are several complexity measures according to which the hardness of problems can be described; the most common one is just how much time we need to solve them. Alan Cobham and Jack Edmonds were quite successful in identifying a reasonable notion of “efficient computation”.

Within the computational complexity framework, we can now prove some results that are consistent with our intuitive notion of computation. My favourite example is the time hierarchy theorem: if we are given more time to compute, we can solve harder problems.

The central open problem of complexity theory, P vs NP, is just a formalisation of another philosophically significant question: is it really harder to solve a problem than to check if an alleged solution of it is indeed correct? I believe this question is worth asking, and answering, independently of its practical significance.

### 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.

Our DLT 2010 paper, authored by yours truly, Alberto Leporati and Claudio Zandron, is titled On a powerful class of non-universal P systems with active membranes. In it, we describe a restricted variant of P systems with active membranes (computing devices inspired by biological cells) that is not Turing-equivalent, but nonetheless decide a surprisingly large class of languages. This class also seems to be somewhat “new” (we haven’t been able to find any reference to it in the literature).

Consider the operation of tetration (iterated exponentiation), defined as

${}^n b = \underbrace{\,b^{b^{b^{\cdot^{\cdot^{\cdot^b}}}}}}_{\text{\emph{n} times}}$

and call PTETRA the class of languages decided by Turing machines working in time ${}^{p(n)}2$ for some polynomial p (the P in PTETRA signifies the fact that exponentiation is iterated only polynomially many times instead of, say, exponentially many). This class is trivially closed under union, intersection, complement, and polytime reductions. Furthermore, it’s easy to see that it can also be defined in terms of space ${}^{p(n)}2$ (you can also throw in nondeterminism, if you really want to).

Well, the main result of our paper is the following funny theorem.

Theorem. The class of languages decided by our variant of P system with active membranes is exactly PTETRA.

The proof works like this:

• The upper bound is proved by a few calculations that show how our P systems can never use more that tetrational space, because the process of membrane division (which generates lots of new membranes) must stop after a finite number of steps.
• To prove the lower bound, we show that we can simulate with our P systems all tetrational-space counter machines, hence tetrational-space Turing machines.

The result is somewhat unexpected, as I was under the impression that all we could do with these P systems was EXPSPACE, and indeed I wasted a few days trying to prove that. Fortunately, reality turned out to be much more interesting.

### 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.

Indeed I am, because I’ve chosen this as the subject of an exam paper, a decision that I’m beginning to regret: the matter is so deep and fascinating, and I’m so little qualified to discuss it, that I’m spending an awful amount of time perusing unfamiliar literature without actually writing anything. There’s a lifetime to spend just to familiarise with the amazing history of computability, even if we limit ourselves to the first half of the 20th century, and we haven’t even begun with the philosophy of science yet!

I decided to directly attack the big ugly question: consider (one particular version of) Turing’s thesis, the claim that every arithmetical function computable by a human being, provided with enough ink and paper, can be also computed by one of Turing’s machines. Is this a scientific statement?

Deciding how to establish whether something is science or not is called the demarcation problem. Having, unfortunately, no time to get a philosophy degree at the moment, I chose a particular point of view, that of Karl Popper (the philosopher of critical rationalism), who was one of the main names in the course I attended. Popper says that what makes science science is not the verifiability of our claims, which is inevitably a hopeless task, but their falsifiability.

Popper rejects induction as a valid inference principle in science, essentially for purely logical reasons. Having seen enough white swans doesn’t allow us to infer that all swans must be white, as somewhere else a black one might be hiding and mocking us. However, this must not stop us from making the claim that all swans are white: this is a perfectly reasonable hypothesis, only we should not deceive ourselves and pretend that our claim is somewhat justified by our previous observations.

What makes the white swan hypothesis a good hypothesis is that it can be falsified. Tomorrow, a friend of ours could come to us and produce a black swan: this falsifies our claim, and we should (in principle) leave that one behind, and make science advance by formulating another.

Popper says: that’s what science is made of! Formulate bold statements, using whatever means you find convenient: observations, deduction from metaphysical principles, imagination; it doesn’t really matter. And the bolder you are, the better: a more falsifiable statement is more informative, as it excludes a lot of possible worlds. Then you must fiercely attack your theory, by making lots and lots of empirical observations, with the goal not of proving it, but of making it fail.

And the testing never ends. It’s only a matter of convention to stop trying to falsify our theory for a moment, and do something else. Because we can always resume our experiments later, when doubts start troubling us again. In his Logik der Forschung (translated as The Logic of Scientific Discovery) Popper makes his point in a striking way.

The game of science is, in principle, without end. He who decides one day that scientific statements do not call for any further test, and that they can be regarded as finally verified, retires from the game.

Subscribing to Popper’s view, I’ll make my own bold (philosophical) claim, i.e., that Turing’s thesis is a scientific statement. Details in the next episodes.

In the mean time, here is a nice short introduction to Popper’s philosophy of science: Popper’s account of scientific method by J. A. Passmore.

### The universal Turing machine

23 July 2010

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:

1. 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).
2. I’ve already formulated a computability thesis that says: if I can do it, then a computing machine also can.
3. But then, there must be a universal computing machine! Let’s fill in the details…

Or maybe he came to that realisation some completely different way. Possibly, directly from Gödel’s work?

Who knows, maybe there even exists something written by Turing himself on this subject.

### 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.
 *** 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 is away: proving some stuff * kurt is back <kurt> lol dave, taek a look at this: http://is.gd/dAo7d <david> FFFUUUUUUUUUUUU <david> at least solve teh entsk^Wentschi^W entscheidungsproblem... <alonzo> cant do that, lambada calculus proves it <kurt> oh stfu alonzo <alan> my machiens are liek people and cant do it <alonzo> alan: your right, and so am i (told ya) <kurt> lol dave, epic fail!!1! <alan> lmao <david> wtf is wrong with you ppl?? <gottlob> i kno the feeling bro *** david (daboss@uni-göttingen.de) has left #logic (pwnd) 

After a few pages (omitted here) there’s a final remark on the subject:
 <yuri> oh btw, cant solve integer eqns either 

### 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).

Let L(φ) be the length in symbols of the shortest proof of the sentence φ, using a standard set of inference rules together with any recursive set of axioms for T; set L(φ) = 0 if φ is not a theorem. Also, let L(n) be the maximum L(φ) among all sentences φ of length at most n.

Theorem. L grows faster than any computable function.

Proof. Otherwise, given a sentence φ, we can first compute an integer f (|φ|) ≥ L(|φ|), then enumerate all proofs of length at most f (|φ|) and check them. If at least one of these is a proof of φ, we answer “yes”, otherwise “no”. But this is a decision procedure for T, since we know that if φ is a theorem, then it has a proof of length at most f (|φ|); contradiction. □

In particular, the theorem holds for Peano arithmetic and friends.

### 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.

• The PR functions are exactly the functions that can be computed by using only for loops (i.e., without unbounded kinds of loop such as while and repeat-until).
• Each time you apply the primitive recursion schema, you get new functions. Meaning: with n + 1 nested for loops you can compute functions that you can’t compute using only n nested for loops.
• Any computable function can be obtained by using PR functions plus a single application of the μ operator. In other words, you just need to use one while loop (together with the for loops) to obtain a Turing machine. This is called Kleene’s normal form theorem.
• Every recursively enumerable set is also primitively recursively enumerable. See this question on MathOverflow, where I recently discovered this fact.
• The PR functions are exactly the functions that can be computed by Turing machines operating within a PR time bound. Isn’t this amazing? See, e.g., this paper by A.R. Meyer and D.M. Ritchie (yes, that D.M. Ritchie).
• Any function of practical use is primitive recursive. This is a consequence of the previous point: polynomials, but also exponentials (and much, much worse functions) are all PR. If a function is not PR, then you don’t have enough time to compute it.

I strongly urge you to like the primitive recursive functions too.