A real Turing machine
I saw this video and tweeted about it, but it’s so cool that I think it needs a blog post.
It’s a real live, operational, Turing machine (sans infinite tape, of course).
So, what’s a Turing machine? It is a theoretical (until now) device that is capable of scanning, reading, and writing binary numbers onto a “tape” of cells (think of it as a binary array of infinite size). Alan Turing (naturally) first described such a machine in order to provide a foundational representation of machine computing. It’s not practical, but it’s a good place to start.
Okay, it seems kinda silly, what’s the point? The point is, well…there are a lot of points. However, one of the most interesting things about the Turing machine is that a clear definition for “computer” can be written in terms of a Turing machine. Formally, the Church-Turing thesis states that everything computable can be computed by some Turing machine. This can be taken one step farther: any machine that can simulate a Turing machine, is a computer. So, my laptop is a computer, my Xbox is a computer, and my calculator is a computer. But even an abacus is a computer, and even a bunch of rocks can be a computer!
Anyway, I tend to get excited about nerdy stuff like this, and I thought it was very cool that someone took down the nebulous mind’s eye view of a Turing machine and built it out with servos and a long film strip. It got me thinking about those long assignments writing out state machine diagrams and simulating Turing machine outputs on paper.
CodeStock 2010 – vote for me!
Going to CodeStock this year?
If you are, consider voting for me! Yes, voting. CodeStock is unique among dev conferences in that it allows the participants to vote on the sessions they would like to see most. Check out the list of all CodeStock sessions.
So, back to voting. If you are going, I suggest you vote for me! I’ve submitted two talks:
- MVC with CakePHP, your first bite. This is a session I’ve given a couple of times now as an introduction to the CakePHP framework.
- Don’t be afraid of NoSQL: An Introduction to db4o – I think this is probably the more interesting of the two sessions, as I think db4o is really an undiscovered treasure when it comes to persistence options. It’s easy, fast, and mature. With recent interest in OODBMS’s like Mongo and Couch, I think db4o also deserves a look.
So there you go. Vote for me.
Clean Code, chapter 4: comments
“Comments are not like Schindler’s List. They are not ‘pure good.’ Indeed, comments are, at best, a necessary evil.”
I have gotten into some heated discussion recently about comments, mainly because I agree with the above quote from Clean Code. It’s possible that my code isn’t expressive enough. And by possible, I mean very likely. However, that doesn’t mean I need more comments: it means I need to write better code. That’s an opinion, but an opinion that’s validated by chapter 4 of Clean Code.
Here are a couple of points that were brought up in defense of commenting, and commenting often:
- Incompetent programmers: i.e. developers who don’t know basic syntax or basic design patterns
- Non-native English speakers: keywords, classes, frameworks, documentation, variable names, etc. have an English bias.
Those aren’t bad arguments, and they come from experience, but here are my responses:
- Incompetence on the part of someone else is not a good enough reason for me to do extra busywork that doesn’t add value. If a dev is incompetent but willing to learn, comments aren’t the place to teach. If they are incompetent and unwilling to learn, then they need to go. If they can’t be removed, then the organization is likely destructive anyway, and no amount of comments is going to mean the difference between a successful project and a failed project.
- English is the language of programming, for better or worse. And again, if the programmer is trying to improve their English skills, comments are not the place to learn spelling, grammar, etc. If they’re unwilling to try to improve, see the first bullet point.
The main point of this chapter is: comments do not make up for bad code. Clear code is better than comments.
However, sometimes comments make total sense. A colleague of mine recently discovered that JavaScript’s month index is 0-based. January = 0, February = 1, etc. This is surprising behavior, and is a perfect place for a comment.
Project Euler: 14, 15, 16, 17
I’ve been cranking away at Euler problems lately. It’s kinda addicting.
Problem 14 is about the Collatz Conjecture, which just so happens to be the subject of a recent xkcd comic:
But there’s nothing special about the sequence when solving this problem, really. I did learn a neat trick after solving this problem: normally to check if a number was even, I would just look at its modulus of 2—if it’s 0 then it’s even. But there’s a faster way to do it: do a bitwise ‘and’ with the number and 1, if the result is 0 then it’s even (and bitwise operations are certainly faster than division operations). This trick isn’t exactly obvious to the code reader, so I put it into the MathHelper class as an “IsEven” method.
p>Problem 15 is about finding all possible paths through a grid. I struggled a bit with this one. I tried a recursive solution, but the answer never seemed to be right. I kept getting this nagging feeling that there’s some pattern that I was missing, so I Googled about it and discovered that you can actually take Pascal’s triangle, turn it sideways, and lay it directly over a grid. The corresponding corner value is the answer. So, once again, I put a PascalTriangle method into MathHelper.
Problem 16 is yet another problem that’s easy to solve with a BigInteger class. Performing an exponential operation on it is just like with regular numbers: using a “shift” operator is faster than performing actual multiplication. Then it’s just a matter of going through every digit and getting the sum.
And finally, problem 17, which was fun. I again tried a recursive solution, and then it was just a matter of defining the minimum amount of rules (one – nineteen, twenty, thirty, … ninety, and one thousand). Writing tests made this problem a breeze.
That’s all for now. Remember, you can check out the source code at CodePlex. Also, check out my nifty new WinForms UI for running the tests.
Clean Code, chapter 3: functions
“The ?rst rule of functions is that they should be small. The second rule of functions is that they should be smaller than that.” (page 34) When I was first learning programming, it was my understanding that functions should be used whenever you have a piece of code that you will reuse. If you aren’t going to reuse it, it doesn’t need to be a function. However, this overlooks an important feature of functions: their names. Even if a function is only used once, even if doesn’t return anything, even if it doesn’t take parameters, it’s still useful to take a block of code and name it according to its intent. Does this lead to a lot of functions? Maybe. So what? It’s easier to read and maintain.
Functions shouldn’t have a lot of parameters. A bunch of ‘out’ or ‘ref’ parameters is usually a clear sign that maybe another class should be created. A function with one parameter is called a monad. A function with two parameters is called a dyad. A function with three parameters is called a triad. A function with four or more parameters is called epic fail.
This chapter is a very good one, with lots of great guidelines for writing functions, and a lot of the stuff in this chapter can also be applied to objects & systems (as I’ve read in later chapters).
Buy my book!
