Tag Archives: Alan Turing
For the last two weeks I’ve written a number of posts contrasting physical systems with numeric systems.
(The latter are, of course, also physical, but see many previous posts for details on significant differences. Essentially, the latter involve largely arbitrary maps between real world magnitude values and internal numeric representations of those values.)
I’ve focused on the nature of causality in those two kinds of systems, but part of the program is about clearly distinguishing the two in response to views that conflate them.
Continue reading
20 Comments | tags: Alan Turing, Cantor's Diagonal, Georg Cantor, Halting Problem, Heisenberg Uncertainty, Incompleteness Theorems, Kurt Gödel, quantum mechanics, Turing Halting Problem, Werner Heisenberg | posted in Brain Bubble, Computers
I finally watched The Imitation Game last night. I have a great deal of regard for Alan Turing, and I’ve always enjoyed codes and cryptography (the story of breaking the Enigma machine is especially fascinating), so I was really looking forward to finally seeing it.
And… I didn’t like it. A lot. Turns out it reflects everything I see as wrong with movies — and with society — in these social media-driven, over-amped, uncritical modern era days.
Watching the movie to get away from politics, it dragged me right back for having the same lack of authenticity, made up conflict, and disregard for history.
Continue reading
18 Comments | tags: Alan Turing, Andrew Hodges, Benedict Cumberbatch, Bletchley Park, Bombe machine, codebreaking, Enigma machine, Joan Clarke, Keira Knightley, Sherlock, The Imitation Game, Turing Test | posted in Movies, Rant
No, sorry, I don’t mean the Bletchey Bombe machine that cracked the Enigma cipher. I mean his theoretical machine; the one I’ve been referring to repeatedly the past few weeks. (It wasn’t mentioned at the time, but it’s the secret star of the Halt! (or not) post.)
The Turing Machine (TM) is one of our fundamental definitions of calculation. The Church-Turing thesis says that all algorithms have a TM that implements them. On this view, any two actual programs implementing the same algorithm do the same thing.
Essentially, a Turing Machine is an algorithm!
Continue reading
8 Comments | tags: Alan Turing, algorithm, Church-Turing thesis, flowchart, state diagram, Turing Halting Problem, Turing Machine, Universal Turing Machine | posted in Computers
When I was a high school kid, my dad and I sometimes played a game where one of us would make up a secret code, write a message in that code, and the other would try to decipher the message. We generally used simple substitution ciphers, so it was an exercise in letter frequency analysis and word guessing.
There’s a cute secret code I found in a book back then that really stuck with me because of the neat way it looks. It also stuck with me because it’s so simple that once you learn it, you really can’t forget it.
So for some Saturday fun, I thought I’d share it with you.
Continue reading
1 Comment | tags: Alan Turing, Alienese, cipher, code, decipher, decoder ring, Freemasons Cipher, Futurama, math, mathematics, one-time pad, Pigpen Cipher, secret codes, substitution cipher, The Simpsons | posted in Basics, Math
Is that you, HAL?
Last time, in Calculated Math, I described how information — data — can have special characteristics that allow it to be interpreted as code, as instructions in some special language known to some “engine” that executes — runs — the code.
In some cases the code language has characteristics that make it Turing Complete (TC). One cornerstone of computer science is the Church-Turing thesis, which says that all TC languages are equivalent. What one can do, so can all the others.
That is where we pick up this time…
Continue reading
1 Comment | tags: Alan Turing, algorithm, Church-Turing thesis, code, data, flowchart, lambda calculus, state diagram, stored program computer, Turing Machine, Universal Turing Machine, Von Neumann architecture | posted in Math
The previous post, Halt! (or not), described the Turing Halting Problem, a fundamental limit on what computers can do, on what can be calculated by a program. Kurt Gödel showed that a very similar limit exists for any (sufficiently powerful) mathematical system.
This raises some obvious questions: What is calculation, exactly? What do we mean when we talk about a program or algorithm? (And how does all of this connect with the world of mathematics?)
Today we’re going to start exploring that.
Continue reading
7 Comments | tags: Alan Turing, algorithm, binary digits, calculation, Church-Turing thesis, code, computer program, data, information theory, lambda calculus, mathematical expression, Turing Machine, Universal Turing Machine | posted in Math, Opinion
evaluate(2B || !2B)
Hamlet’s famous question, “To be or not to be?” is just one example of a question with a yes/no answer. It’s different from a question such as, “What’s your favorite color?” or, “How was your day?” What it boils down to is that the young Prince’s question requires only one bit to answer, and that bit is either yea or nay.
Computers can be very good at answering yes/no questions. We can write a computer program to compare two numbers and tell us — yea or nay — if the first one is bigger than the second one. Computers are also very good at calculations (they’re just big calculators, after all). For example, we can write a computer program that divides one number by another.
But there are questions computers can’t answer, and calculations they can’t make.
Continue reading
2 Comments | tags: Alan Turing, algorithm, calculation, Cantor's Diagonal, computers, discrete mathematics, Halting Problem, Turing, Turing Halting Problem | posted in Computers, Sideband
