AI and the Church-Turing Thesis

8th May, 2012

Over on G+, Alexander Kruel pointed me towards an article by Alex Knapp entitled “Why your brain isn’t a computer”.

The point of this post is not to argue whether it is or it isn’t, but to draw attention to a salient point, which I think Alex waves away rather too quickly (and which in any case is important and interesting).

One might reason that there are plenty of different types of ‘computation’ around these days: ordinary computer programs, embedded systems, neural nets, self-modifying code, and so on. So, with all this variety, why should we expect that a human brain, being a neurochemical network, should fall into the same computational category as a laptop? Might it not simply be that the two have different capabilities? As Alex argues “Electric circuits simply function differently then electrochemical ones”.

The problem with this argument is that it overlooks the great robustness of the notion of computability, specifically the Church-Turing thesis.

A bit of history: in the 1930s, Alan Turing was investigating the capabilities of Turing machines, funny little devices which creep along a ticker-tape, and respond to the symbols they find there. Meanwhile over in the US, Alonzo Church was exploring the semantics of a formal system he had developed, called lambda calculus.

On first sight, the two topics appear to have little in common. But when the two men encountered each others’ work, they quickly realised something unexpected and profoundly important: that anything which can be expressed in lambda calculus can also be computed by a Turing machine, and vice versa. Shortly afterwards, a third approach known as recursion was thrown into the mix. Again, it turned out that anything recursive is Turing-computable, and vice versa.

This leads to the assertion we know as the Church-Turing thesis: that a process which is computable by any means whatsoever, must also be computable by a Turing machine.

It is important to stress that the Church-Turing thesis has good experimental support. Every computational system we know of obeys it: cellular automata, neural networks, Post-tag systems, logic circuits, genetic algorithms, string rewriting systems, even quantum computers*. Anything that any of them can do can (in principle) be done by conventional computational means.

So when Alex comments that “the brain itself isn’t structured like a Turing machine”, the obvious response is, “well, no, and neither are lambda calculus, cellular automata, and the rest”. (Come to think of it my phone doesn’t much look like a Turing machine either.)

The ‘dualism’ which distinguishes software from hardware (which Alex argues fails for the human brain), is not something built in from the outset. Rather it emerges from the deep, non-obvious fact that computational systems beyond a certain complexity can all emulate each other.

Needless to say, there have been no shortage of people claiming to have developed systems of different kinds which go ‘Beyond the Turing Limit’. (See Martin Davis’ paper on The Myth of Hypercomputation.) And who knows, maybe our brain embodies such a process. (I have my doubts, but if we’re going to find such a system anywhere, the brain is certainly an obvious place to look.)

The bottom line here is that if you don’t want to accept that

  0)   The human mind is computable

then I’d say you have three positions open to you:

  1)   It requires an extra metaphysical ingredient;
  2)   It’s a hypercomputer which violates the Church-Turing thesis;
  3)  It relies in an essential way on a non-computable process, meaning some inherent element of randomness.

Personally I’d order these 0312, in order of likeliness. (At the same time, I’d say talk of reverse-engineering the human brain is like a toddler planning a manned expedition to Mars. How about we concentrate on crossing the room without falling over first?)


*Quantum computers may be able to compute certain things quicker than conventional ones, but they won’t be able to compute essentially different things.

Categories: Bloggery, Brain Science, Logic, Philosophy | Comments (4) | Permalink

Elwes Elsewhere

7th December, 2011

If it’s been quiet around here recently, it’s because I’ve been hanging around in various places other than my own blog recently…

1. I’m on Google+ a lot these days. It’s now definitely my social medium of choice. Come and join in!

2. Coming out of discussions on G+, I cowrote a piece with John Baez on Babylonian mathematics and the square root of 2, which is now up on John’s blog Azimuth. (I can’t resist adding that John was also kind enough to write a flattering review of Maths 1001.)

3. And by no means least… I have a new book out! It’s called The Maths Handbook. I’ve been chatting about it, and maths in general, with Daniel Fraser on the Quercus Couch.

Categories: Bloggery, Bookery, Richard Elsewhere | Comments (0) | Permalink

Webinar playback: some families of polyhedra

16th May, 2011

On Saturday, I gave my first ever webinar, on the topic of “Some families of polyhedra”. And if you don’t know your tetrahemihexahedron from your tridiminished rhombicosidodecahedron, the good news is that the whole thing is available to see and hear here. It’s just over an hour long, but of course one advantage the recorded version has over the live one is the ability to fast forward, pause, and rewind.

It was hosted over at Mathfuture, by Maria Droujkova. My aim in the talk was to give a very brisk overview of how several different families of wonderful, complex shapes all arise from juggling a very small number of simple criteria. I’m separately uploading the slides for my presentation here [pdf]. They are quite rough and ready, without any detailed explanations, or even any pictures – I used Stella for those. But it does sketch the central story (which I also covered in this blogpost). I may spruce them up one day, if I give the same talk again.

I found the whole thing a thoroughly enjoyable experience, and the Elluminate technology worked extremely smoothly. The format allowed me to talk while sharing my whole desktop with the audience, with the optimal result of people being able to hear my voice and watch everything I was doing, without having to endure looking at my face. And we could all do it from the comfort of our living rooms! This is sort of thing the internet was intended for, isn’t it?

Categories: Bloggery, Geometry, Maths, Richard Elsewhere, Technology | Comments (2) | Permalink

Science Media: The Next Generation

15th May, 2011

Last week I travelled down to sunny Cambridge for the Science Media Next Generation conference at Jesus College. I’m not going to write up all that was said, since that has been done well elsewhere. But I’ll briefly list the main lessons that I took away.

(This is a rather selfish list in that it’s about how the issues relate to me. There was lots interesting discussion and speculation about the future of science & media & science media, as well as some fascinating stuff from Simon Singh on his experience of libel law, and from Adam Wishart on ethics. But on all these topics I don’t have much to add to what others have already said.)

Lesson 1: I am not a science journalist. I suppose that subconsciously I have always secretly suspected this, but it is useful to have it confirmed. My interest in science is in science, much less in the attendant politics. I want to help demystify it, report on exciting developments to people who would otherwise not hear about them, and generally spread the word about how wonderful it is. Meanwhile, a journalist’s job is to “hold scientists to account” and generally “cause mischief”. I don’t wish to sound cynical: plenty of good arguments were made for the importance of these activities, but they had the side-effect of convincing me that that’s not where my future lies.

So what am I? A “science communicator” perhaps. I’d even accept “science curator, guide, navigator or sense-maker”, as John Naughton put it. Actually I’ve often thought of myself as more of a “translator” of technical ideas into everyday language.

Lesson 2: The Science versus Religion debate has gone downhill since the days of Bertrand Russell. Like most of the crowd, I was slightly taken aback that the session on “Impact of Science Journalism on Culture and Society” was entirely devoted to booting around the old, deflated football of the compatibility of science and God.

I do think there are interesting things which can still be said about this, at the sociological and historical levels. But in terms of the metaphyical implications of any particular piece of science (whether that be the human genome or the latest multiverse speculation), I view the whole subject as a black hole best avoided. You can bat such questions back and forth for ever, after which everyone grumpily reverts to their starting positions. Namely, all reasonable people peg their preferred philosophical outlook to whatever the science currently says, while the maniacs deny it outright.

Lesson 3: People, things, and ideas. The most controversial moment of the day was when Andrew Brown declared that “People are more interested in stories about people than they are in stories about things”.

I work in mathematics, which isn’t even about things. It’s about ideas. This puts me at least two steps removed from anything anyone cares about. Like many people present, I think, my immediate reaction was one of defensiveness. On the face of it, the statement is false: as David Adam from Nature pointed out, things such as cosmic background radiation can generate a surprising amount of interest. Andrew replied that this is ultimately a story about people, as it concerns the origins of humanity. This struck me as a bit of a cop-out, since all of science is – by definition – the study of the situation in which we find ourselves, and hence ultimately about us, if you like.

Still, there is food for thought in Andrew’s remark. Some things (or ideas) are of interest for the way they relate to aspects of people’s direct experience. The never-ending stories of scientists finding a gene for obesity or campanology testify to this. Other ideas are interesting for their mind-expansion value: plenty of people derive pleasure from wild and wacky ideas. Dark matter & Higgs boson detection constantly attract headlines, even though they fall completely outside anyone’s daily life. This is – mostly, I think – where mathematics fits in, Grigori Perelman’s proof of the Poincare conjecture being a good recent example.

That example does qualify an interesting story about a person in a much more direct sense, though, since Perelman is such an unusual character.

The most interesting stories of all should, therefore, concern wild theories which also relate to our daily experience. Can mathematics hope to qualify? Yes! It could be argued that the P=?NP question, for example, lives exactly here. (For the hat-trick, all that remains is for it to be resolved by an extraordinarily strange individual.)

Lesson 4: The view from the other side. It was valuable to hear about the science book business from publisher turned writer Christopher Potter and literary agent Peter Tallack (disclaimer: he’s my agent). It’s clear that in all areas, the trend is away from paper towards electronic media. My impression though, is that this is happening faster in the world of journalism than in books. Relatedly, I sense that while journalists are – rightly or wrongly – feeling threatened by bloggers, book-writers have a slightly more secure position. While people might write blogposts for free as a hobby, they’re likely to continue to want money to write books. The upshot was that Peter’s “five reasons to be cheerful” pretty well had their desired effect, and it was certainly nice to end the day on an optimistic note.

Lesson 5: It really is time I got a twitter account. Well on that, at any rate, I can report progress. The only thing now is to work out what to do with it.

Overall, a thought-provoking day, and lovely to meet people including Andy Extance and Stuart Clark. So, many thanks to the organisers & sponsors including Bluesci magazine and the Public Library of Science.

Categories: Bloggery, Politics, Richard Elsewhere | Comments (2) | Permalink

Meet me in the aether

9th May, 2011

This Saturday (14th May 2011) I shall be involved in my first ever webinar, generally chatting about my work and a few interesting bits of mathematics with Maria Droujkova, and anyone else who shows up.

So please come and join in! The door is here. It starts at 7PM British Summer Time, or this time where you are.

To get in, you’ll need to download Elluminate, which provides the virtual seminar room where we can share images, text, and voices. It’s free and easy to install, and well worth having a look at, even if you’ve no interest in me…


(NB. Comments on this blog remain disabled for technical reasons my web-master explains: “There is an admin account but I can’t immediately find what the password is. I will look harder. I definitely will have written it down on a scrap of paper somewhere under my bed etc.”)

Categories: Bloggery | Comments (0) | Permalink

Superb at Nothing

27th April, 2011

Having shamefully neglected this blog (and indeed having been enjoying a holiday in Hungary), I came back yesterday to find it overflowing with thousands of comments flogging fake Rolexes (or should that be Rolices?).

I’ve disabled comments as a temporary measure, while I fiddle around trying to install a spam-catcher. I hope I didn’t delete any real people’s comments during the clean-up operation, but if you notice anything missing, please let me know.

Meanwhile, here’s a video clip of British comedian Kenneth Williams talking about medicine. But I think his comment is equally applicable to many areas of science, and not least to mathematics:

Categories: Bloggery, General Science, Nonsense | Comments (0) | Permalink

Exotic spheres and Yog-Sothothery

12th January, 2011

I’ve got an article about the smooth 4-dimensional Poincaré conjecture, and Yog-Sothoth, over at Plus magazine.

Categories: Bloggery, Maths, Richard Elsewhere, Topology | Comments (1) | Permalink

Blog and book updates

26th October, 2010

I’ve been doing some updates around this place. If things look rickety it’s because I am now phping and htmling myself. I’m having fun with it, but if I’m honest I don’t really know what I am doing. In fact, I don’t even know the difference between php and html. Luckily I have a tame professional webdesigner who should be able to repair any havoc I wreak.

The most important change is that this blog is finally equipped with an RSS feed. I encourage you to subscribe, because posting is likely to remain erratic, so the old fashioned method of clicking over here every once in a while might prove frustrating. Having said that, I do have a few posts lined up for the days ahead.

In celebration of this great step forward, I have decided to officially baptise this blog. Hereafter it will no longer be known only as “Richard Elwes’ blog”, but as “Simple City”.

In other news, my book Mathematics 1001 is now out… sort of. If you live in the USA, then it is definitely and unambiguously out. I think the same is true in Canada. For residents of the UK, the book is currently in a quantum out/not out state. The wave function seems to depend what sort of outlet you try to buy it from. It is not yet in the shops, but it is, I believe, available online. The official final release date here is 6th November. For citizens of Australia, and other countries, well, I don’t know. But it should be out soon, at least.

Anway, I am collecting book reviews (hooray!) and errata (boo!) here. So far there are barely any of either, but that will certainly change within the next couple of weeks. I’ll confine the updates to those pages rather than blogging them, so if you’re interested then check back there occasionally. (If you have any information for me about such things, then I’d be very grateful if you could drop me a line, or leave a comment here.)

Categories: Bloggery, Bookery | Comments (33) | Permalink

A Carnival Atmosphere

1st March, 2009


The Carnival of Mathematics is a fortnightly round-up of maths blogging, which has just reached its 50th incarnation. It’s a travelling show, and is currently docked at The Endeavour. Have a look, there’s some great stuff there (and a bit by me).

I will try to link to updates even when I’m not featured. But you can always find details here.

There’s also a brand new maths teachers at play carnival, focused more on school level mathematics and teaching ideas.

Categories: Bloggery | Comments (0) | Permalink

Tied up in Knots

17th October, 2008

I’ve got an article about knot theory in this week’s New Scientist magazine.

Categories: Bloggery, Maths | Comments (5) | Permalink

Next: Noting knots >>