## Posted tagged ‘Turing’

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

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

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