Tag: Computability
-
Failing software – again
The line above is from a real (and current at time-of-posting) job advertisement for a software developer. I’m not positing it because I think it is bad, shocking or dangerous, but mainly because it is illustrative of the real world: developers are expected to be “pragmatic” when it comes to testing the software they make…
-
A (partial) answer to my Goedelian conundrum?
Last week I puzzled over what seemed to me to be the hand waiving dismissal, by both Alan Turing and Douglas Hofstadter of what I saw as the problem of humans being able to write true statements that the formal systems employed by computers could not determine – the problem thrown up by Goedel’s Incompleteness…
-
More than a game: the Game of Life
Conway’s Game of Life has long fascinated me. Thirty years ago I wrote some Z80 machine code to run it on a Sinclair ZX80 and when I wrote BINSIC, my reimplentation of Sinclair ZX81 BASIC, Life was the obvious choice for a demonstration piece of BASIC (and I had to rewrite it from scratch when…
-
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…
-
Reflections on the riots: part one
This is a blog about computing (along with some maths and science) – and not about politics, and having disciplined myself to stick to that for the last nine months, I intend to keep it that way, even as I write about the biggest political event of the year. But I will allow myself two…
-
“Basically, you would be able to compute anything you wanted”
The quote that forms the title here comes from Lance Fortnow, a computer scientist at Northwestern University, in an article (here – subscription required) in the current edition of the New Scientist on the question. It’s an odd statement for a computer scientist to make – most numbers are transcendental numbers and so are fundamentally incomputable:…
-
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…
-
The diagonal proof
I am just reading Computability and Logic and it (or at least the old, 1980, edition I am reading) has a rather laboured explanation of Cantor’s 1891 proof of the non-enumerability of real numbers (the diagonal proof) so to reassure myself and because it is interesting I thought I’d set out a version here (closely…
cartesian product ... stuff about computing mostly 