Tag: turing machine

Incompleteness in the natural world
A post inspired by Godel, Escher, Bach, Complexity: A Guided Tour, an article in this week’s New Scientist about the clash between general relativity and quantum mechanics and personal humiliation. The everyday incompleteness: This is the personal humiliation bit. For the first time ever I went on a “Parkrun” today – the 5km Finsbury Park…

Turing, Hofstadter, Bach – with some Cherla thrown in
A few weeks ago I attended the morning (I had to go back to work in the afternoon) of the BCS doctoral consortium in Covent Garden in London – watching various PhD students present their work to audience of peers. The presentation which most interested me was that of Srikanth Cherla who is researching connectionist…

Stephen Fry is wrong about Alan Turing
Stephen Fry argues that Alan Turing’s “Universal Machine” is the greatest ever British innovation. 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…

My (computer science) book of the year
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…

Very small Turing machines
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 A turing machine in 133 bytes of javascript (swizec.com) Is…

The Great Alan Turing
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…

Cardinality of the set of all strings
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…

P = NP once again
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…

Coming up… the lambda calculus
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…

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. Petzold says these three axioms come from Hilbert and Bernays and they mean: Every member has a successor There exists a number that does…