In introduction to the notion of formal reasoning and theory.
Having concluded what I expect to say in my Unlocking Programming series, I find myself with two avenues which have been requested: one reader asked for instruction on actually learning programming; another asked for an introduction to computer science theory. I hope to fulfill both requests, but expect to do the learning as a series of video posts and have yet to add to my schedule time to record those in a low-noise environment. Thus, I am beginning to write the theory posts.
When I tell my friends that I am a theoretician and write proofs they typically react as if I had just admitted to being some sort of not-quite-human apparition with mystical powers. Hence, I want to introduce first the notion of theory in theory before delving into the practice of theory.
One of my favorite quotes, the origin of which I have been unable to trace, is “The difference between theory and practice is larger in practice than it is in theory.” This points to a difference in focus: theory asks “can anyone ever?” where practice asks “can I right now?”. Since there are many things we have not yet done but (as far as we know) could eventually be done, practice typically falls within the bounds of theory while theory typically extends far beyond practice.
Let’s consider a concrete example. Theory (special relativity) says that nothing can go faster than c, which is roughly one billion kilometers per hour. 670 million mph for you imperialists. Practice says nothing can go faster than a few thousand kilometers per hour. Clearly, practice aligns with theory, but it makes the theory look kind of silly. Particle physicists care about the speed of light quite a bit, but for the rest of us it is curious but not practically important.
Despite this sometimes extreme feeling of impracticality, theory can also be quite powerful. Knowing what can’t be done can save a lot of time working on impossible problems. Theory is also useful in indicating where there’s likely the largest room for improvement.
Theory. Know the possible.
Most theory is grounded in formal logic. That is, there is a translation to symbols using the formulae of the discipline, an manipulation of those symbols again per formulae, and then a conclusion from that manipulated form.
The power of formal reasoning lies in its ability to abstract away unnecessary details: once I have the notion “mass is conserved” I no longer need to wonder if the mass of this compound is conserved—the formalism ignored the particular material, so the question is answered once and for all, even for materials not yet invented. It is a beautiful thing to be able to close the book.
The weakness of formal reasoning also lies in its abstraction. Very often we end up throwing away things that matter. A well-known physics joke tells of a physicist hired to investigate the untimely death of cattle on a ranch. After some investigation the physicists announces success and then opens the explanation of the cause of death by drawing a circle on a chalk board and saying “we’ll assume a spherical cow”. Cows aren’t spheres; minds aren’t id, ego, and super-ego; Rubik’s cubes aren’t aren’t permutation groups I discovered this as a missionary when I disassembled my roommate’s Rubik’s cube and reassembled it in an impossible-to-reach state. ; teaching doesn’t create learning; being cold isn’t temperature and wind-chill; etc.
Theory. Ignore reality.
I plan to post several entries explaining the core ideas of computational theory. I probably won’t go too far, since this blog isn’t a textbook, but far enough to give a flavor for what computer science is. I’ll start with the Church-Turing thesis and throw in a bit about classical logic and the core generalizations and conclusions of computational theory.
Throughout computational theory there are two questions: first, “If I had a machine like X, what could that machine do?” “Can my phone do my math test for me?” ; and, second, “what’s the fastest possible way to do task Y?” “Why is my computer so slow?” . These are interesting classes of questions in their own right. However, we want theoretic answers that don’t care about particular details of the computers of the day; that often means getting rather odd-looking answers.
I hope to give a reasonable view of computational theory itself but also to use it as a window to theory and theorizing in general. We’ll see if I achieve either goal.
Looking for comments…