Tagged: turing machine

Stephen Fry is wrong about Alan Turing


Stephen Fry argues that Alan Turing’s “Universal Machine” is the greatest ever British innovation.

Turing at the time of his election to Fellowsh...

The case for Turing is, of course, a strong one. Not just because of the computer you are reading this blog on, but because, probably even more importantly, Turing’s concept was at the heart of the British “Station X” codebreaking effort in the Second World War, shortening the war by years and perhaps was even essential to national survival. Defeating Hitler – something that it is hard to believe could have been done without Britain even if others paid a higher price in money and lives to finally deliver the triumph – remains the great British gift to humanity.

But it is utterly wrong.

Because the Universal Machine is not an invention or innovation at all. It is a discovery – of a mathematical idea – and it has existed (at least) since the beginning of our universe and will still exist long after we (humanity) are all gone.

Admittedly my formulation of mathematics – essentially Platonic – is not uncontroversial and I have strong “political” motivations for making it (of I will be writing more shortly) – seeing mathematical ideas as discoveries rather than inventions is core to keeping patent lawyers’ hands off them (in this jurisdiction at least).

But why treat maths as any different from physics? We are surely not about to grant Peter Higgs (lovely man that he is) a patent over mass, even though we are on the verge of confirming his theoretical paper of 1962 was essentially correct in its formulation of the “Higgs field” that gives particles mass.

Update: Stephen Fry is of course describing the Universal Machine as an “innovation” and not an “invention” as I originally descried it at the top of this article (changed now). The argument doesn’t change though – I don’t think it is an innovation, because it has always existed. It is a great discovery, arguably the greatest, but that’s a different matter.

Related articles

My (computer science) book of the year


The Annotated Turing

Image via Wikipedia

It wasn’t published in 2011 but The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine is without doubt my computer science book of the year.

If books can change your life then The Annotated Turing changed mine – because it showed me just how strong the link between maths and computer science is and how fundamental maths is to an understanding of the nature of reality and truth. The world, in my eyes, has not been the same since I read this book last January.

If you are a computer science student the you must read this book!

And finally, Happy New Year to all.

Very small Turing machines


State diagram of a Turing Machine

Image by Center for Image in Science and Art _ UL via Flickr

I am pretty busy with work now, so one of the things I had planned to do – write a simple Turing Machine in Groovy – will have to wait.

In the meantime here are some very small Turing machines to wonder over.

Related articles

The Great Alan Turing


Allan Turing Statue, on display at Bletchley Park

Image via Wikipedia

Slashdot have a story to the effect that Leonardo DiCaprio is to play Alan Turing in a film that will mark the mathematician’s centenary next year.

Great news – the man’s memory deserves nothing more than the actor who has proved himself to be both great and edgy in recent work (he’s certainly not the milque toast figure the start of his career briefly suggested.)

As a geek, of course, I hope that the film will try to explain, just a little his achievements.

But how can you explain the ideas of computability and the Church-Turing thesis in a popular film? A tough one, but I suppose you could do something.

The Bletchley Park “bombe” and the idea that the weakness of the German Enigma machine – that it would never map a letter to itself (eg., in any message “e” would never be encrypted as “e”) – could be used to break the code (if a combination of a guessed plain text, usually a weather report, at the start of the message , and the initial key settings produced code that mapped letters to themselves then the initial settings were wrong) – is probably easier to explain.

And don’t forget about SIGSALY, the voice encryption system Turing worked on with Bell Labs. As a piece of engineering this is probably impossible to over-estimate in importance: as the first practical pulse code modulation system it could even be said to be the mother the mobile phone, or at least its grand aunt.

And, of course, let me again plug my book of the year: The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine

Related articles

Cardinality of the set of all strings


Oded Goldreich

Image via Wikipedia

I finished John Naughton‘s A Brief History of the Future: Origins of the Internet – an interesting diversion, to be sure and a book worth reading (not only because it reminds you of how rapidly internet adoption has accelerated in the last decade.)

By now I should be on to proper revision, but I indulged myself last week and bought a copy of P, NP, and NP-Completeness: The Basics of Computational Complexity which I am now attempting to read between dozes in the garden (weather in London is fantastic). The book is written in a somewhat sparse style but even so is somewhat more approachable that many texts (the author, Professor Oded Goldreich, rules out using “non-deterministic Turing machines“, for instance, saying they cloud the explanation).

But in his discussion of (deterministic) Turing machines he states:

the~set~of~all~strings~is~in~1-1~correspondence~to~the~natural~numbers

Is that right? (Serious question, please answer if you can).

Surely the set of all strings has the cardinality of the reals?

If we had a set of strings (0,1)^* like this:

1000000....
1100000....
1110000....
1111000....

and so on…

Then surely the standard diagonalisation argument applies? (i.e. take the diagonal 1111111.... and switch states of each member – 000000... and this string cannot be in the original set as it is guaranteed that for the i^{th} member of the set, the with elements \alpha_{1 ... \infty} , \alpha_{i} will be different. (See blog on diagonalisation.)

In Naughton’s book he makes (the very valid) point that students of the sciences are generally taught that when their results disagree with the paradigm, then their results are wrong and not the paradigm: so what have I got wrong here?

Related Articles

P = NP once again


Abacus

Image via Wikipedia

Been an interesting week here on the blog … as I said before getting on Slashdot is great as you get access to the intellect of a lot of people, and that taught me quite a bit.

It’s not relevant to my course but I went to the (Maths shelves of) the Birkbeck library and withdrew The Language of Machines – one of the few books on computability in the library.

But before I get down to reading much of that I think I need to reply to some of the harsher remarks that were made about this blog on Slashdot – in particular the piece I wrote at the end of December called “What if P=NP?“

The opening line of that article is “I admit I now going slightly out of my depth” and it does contain a few errors, though nothing I think that justifies some of the really nasty things a couple of people wrote about it – but then again some people also insisted that proving P=NP would not break public key encryption so plainly there are people on /. whose ignorance is matched by the vehemence of their opinion, so maybe I shouldn’t let it get to me: especially as one of the critics insisted there were no algorithms to solve NP problems (so how are they solved? Fairy dust inside your computer?)

But I thought I’d try to rewrite my blog post in a better way….

I admit I now going slightly out of my depth, but I will try to explain what this is about and why it is interesting.

It is known that computers can solve some problems in what is called “polynomial time“: that is to say a finite time that is proportional to a polynomial of complexity of the input. The key thing is that these problems are computable using known mechanical steps (ie algorithms). Often that means they are solvable in a way that is (sometimes euphemistically) described as “quickly”.

These can be simple problems – like what is the sum of the first ten integers – or more complex ones, such as creating self-balancing trees, sorting database records alphabetically and so on.

These are the so-called “P” (for polynomial time class) problems. Here’s a definition:

A problem is assigned to the P (polynomial time) class if there exists at least one algorithm to solve that problem, such that the number of steps of the algorithm is bounded by a polynomial in n, where n is the length of the input.

Then there are another class of problems which seem fiendishly difficult to solve but which it is relatively simple to prove the correctness of any solution offered. These problems can also be solved (computed) in a finite time – and they can also be computed by a Turing machine (a simple model of a computer) and so an algorithmic solution exists. It is just that one cannot tell in advance what that algorithm is. In the worst case the only way – it is thought – that a solution can be found is through an exhaustive search of all algorithms – in other words a form of “brute force“. These are the NP (non deterministic polynomial time class) problems.

Now most mathematicians think that NP does not equal P – ie there are no “simple” solutions to the NP problems – and that may or may not be a good thing as much of our internet commerce relies on encryption which is thought to be an NP problem and effectively impervious (due to the time it would take to factor the very large prime numbers at the heart of the process) to brute force attacks if properly done.

(In Afghanistan in 2001 US cryptanalysts seemingly brute forced a Taliban Windows NT box but it used much weaker encryption than most electronic commerce.)

But what if it were the case that all seemingly NP problems were actually P problems? There are a lot of people studying this issue – but according to the New Scientist (their Christmas edition, the first in my subscription and delivered this morning, inspired me to write this) we should expect to wait at least until 2024 for an answer (by which point the problem – first formulated in 1971 – will have reached the age at which 50% of major mathematical problems will have been solved).

Some problems thought to be NP have already been shown to be P. But there was also a big fuss earlier in 2010 when a draft proof of P != NP was published (the proof was flawed).

This all matters: unlike, say, Fermat’s last theorem, proving P = NP is likely to have more or less immediate effects on the lives of many of us (how would you feel if you knew that it was possible, even if not likely, that someone had developed a way to quickly crack open all your internet credit card transactions?)

Of course, proving P = NP for all problems does not necessarily mean we will immediately have determined polynomial time based solutions for all the current NP problems out there. But we should not expect that to last for long, though it may be the case that the algorithms may be exceptionally complex rendering them very slow even on the fastest computing equipment, but if history teaches us anything it is that computers get faster (yes, I know there are bounds on that).

And, actually, I think the benefits to humanity would be enormous. The most likely immediate effects would be in improvements in computing/operating system efficiency. fast computers for less money and/or less energy consumption would be a huge benefit. From that alone many other benefits will flow in terms of information availability and universality.

But there could be many, many others in medicine and linguistics and even in getting the trains to run on time!

Related Articles

Coming up… the lambda calculus


An example of a DFA state diagram

Image via Wikipedia

Another thing that The Annotated Turing taught me is what all those lambdas that I have seen over the last 25 years were about, or at least it introduced me to what they were about.

So I have just ordered a copy of Structure and Interpretation of Computer Programs: and I can guess that some blog posts will eventually follow.

Oh no. Maybe I am turning into a LISP hacker – having finally reached the age that all these guys were when I first became aware of them (older, actually).

Related Articles

For all you first order/predicate logic fans out there


From The Annotated Turing: now reached page 226 and it is still good.

I think Charles Petzold has made a mistake – has he? Please read on and let me know.

Three axioms from Hilbert and Bernays

Petzold says these three axioms come from Hilbert and Bernays and they mean:

  1. Every member has a successor
  2. There exists a number that does not have a successor
  3. That is r is a successor  to x and y and x is the successor to s, then y is also the successor to s.

But surely the second axiom actually means there exists an x which is not a successor of y?

Comments please.

Bought on a whim but seems like a good one


This diagram shows the syntactic entities whic...

Image via Wikipedia

I bought this book this evening on the way home from work – The Annotated Turing – and have already got through fifty pages.

(Actually I wish I had bought it from Amazon because the price there is less than half I paid for it).

Those pages covered much of the same ground as the early chapters of  Godel, Escher, Bach: An Eternal Golden Braid - a much more famous book (and not a bad read) -  and in a more formal, mathematical way, but it also seems to do it in a much clearer fashion.

So, while I haven’t yet got to the chapters that dissect Turing’s On Computable Numbers, with an Application to the Entscheidungsproblem, so far I have no hesitation in recommending it as a good introduction to the issues of computability.

What if P = NP?


Update (5 March): read a better version here.

I admit I now going slightly out of my depth, but I will try to explain what this is about and why it is interesting.

It is known that computers can solve some problems in what is called “polynomial time“: that is to say a finite time that is proportional to a polynomial of complexity of the input. The key thing is that these problems are computable using mechanical steps (ie algorithms) in a way that is (sometimes euphemistically) described as “quickly”.

These can be simple problems – like what is the sum of the first ten integers – or more complex ones, such as creating self-balancing trees, sorting database records alphabetically and so on.

These are the so-called “P” (for polynomial time class) problems. Here’s a definition:

A problem is assigned to the P (polynomial time) class if there exists at least one algorithm to solve that problem, such that the number of steps of the algorithm is bounded by a polynomial in n, where n is the length of the input.

Then there are another class of problems which seem fiendishly difficult to solve but which it is relatively simple to prove the correctness of any solution offered. These problems can also be solved (computed) in polynomial time – ie a finite time – and they can also be computed by a Turing machine (a simple model of a computer) and so an algorithmic solution exists. It is just that one cannot tell what that algorithm is. These are said to be solvable in unbounded polynomial time – and in the worst case the only way – it is thought – that a solution can be found is through an exhaustive search of all algorithms – in other words a form of “brute force“. These are the NP (Not in class P) problems.

Now most mathematicians think that NP does not equal P and that may or may not be a good thing as much of our internet commerce relies on encryption which is thought to be an NP problem.

(In Afghanistan in 2001 US cryptanalysts seemingly brute forced a Taliban Windows NT box but it used much weaker encryption than most electronic commerce.)

But what if it were the case that all seemingly NP problems were actually P problems? There are a lot of people studying this issue – but according to the New Scientist (their Christmas edition, the first in my subscription and delivered this morning, inspired me to write this) we should expect to wait at least until 2024 for an answer (by which point the problem – first formulated in 1971 – will have reached the age at which 50% of major mathematical problems will have been solved).

Some problems thought to be NP have already been shown to be P and there was a big fuss earlier in 2010 when a draft proof of P = NP (edit: it was actually P != NP) was published (the proof was flawed). And unlike, say, Fermat’s last theorem, proving P = NP is likely to have more or less immediate effects on the lives of many of us (how would you feel if you knew that it was possible, even if not likely, that someone had developed a way to quickly crack open all your internet credit card transactions?)

Of course, proving P = NP for all problems does not necessarily mean we will have determined polynomial time based solutions for all the current NP problems out there. But I would expect it would quickly lead to the solution of a multitude of them.

And, actually, I think the benefits to humanity would be enormous. The most likely immediate effects would be in improvements in computing/operating system efficiency. fast computers for less money and/or less energy consumption would be a huge benefit. From that alone many other benefits will flow in terms of information availability and universality.