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.
We begin with a simple mathematical expression:
(3 + 4) × (9 - 7)
This expression has a value (14), and to find it we must evaluate the expression. We do this using processes (arithmetic) we learned as children for operating on expressions.
In contrast, consider the following (from a box of Uncle Ben’s® rice):
- Combine rice, water and butter (optional) in a saucepan.
- Bring to a boil, reduce heat (medium, medium-low) and simmer covered 20 minutes.
- Remove from heat. Let stand covered for 5 minutes or until water is absorbed. Fluff with fork and serve.
Assuming we know some basic kitchen skills (if we “have an app for that,” so to speak), we can perform — execute — the steps listed to produce some cooked rice.
The package also provides a reference table showing how much rice, water, and butter, to use for a desired yield. (The recipe comes with a data table! Remember that; we’ll come back to it later.)
Now what we’re going to focus on is the differences and similarities between the mathematical expression and the recipe. It turns out they have a great deal in common, but also some important differences. Those differences speak to what we really mean by calculation.
We start with how an expression has an immediate implicit value (in some cases, multiple values) as its “output” — an expression stands for some value; it’s a way of representing that value.
There are expressions that require multiple steps for us (or a computer) to calculate that value (or values). For example, think about the steps involved in doing long division.
But that doesn’t mean an expression like 4578 ÷ 109 doesn’t have an implied immediate value. It is, after all, the fraction 4578/109 — which is one way to represent its immediate value.
There is a key difference between evaluating an expression (taking its immediate implicit value) and calculating an answer to the question: What is this expression’s value?
The right kind of (usually physical, analog) device can immediately evaluate a given expression. A slide ruler expresses ratios mechanically with sliding pieces. Analog computers use networks of electrical potentials to calculate with numbers (an electrical version of a slide rule).
The equations of orbital dynamics involving more than two bodies are very difficult to solve. We usually can only converge on a usefully accurate approximation.
But nature solves the orbits of all the bodies in the Solar system in real-time and produces perfect answers.
What’s happening is similar to how water always seeks a level or how bubbles and drops are always round (if not distorted by outside forces).
There is a fundamental minimum energy principle in nature — a law of thermodynamics — that reflects how systems to seek the lowest energy state. For example, surface tension is lowest when bubbles and drops are spherical — that’s why they “try” to be round.
Analog devices can leverage this principle, and other physical principles such as distance, to compute with real numbers. Digital devices cannot! The reason is the difference between an expression’s actual value and the need to calculate that value.
In theory, any mathematical expression can be viewed in terms of its ultimate value, not the process of calculating it. In a sense, that value is the expression’s lowest energy state — it cannot be further reduced.
The key point is this: Evaluating an expression in some analog, physical fashion leverages real-world properties that are inherent in the object or in physical models of that object. There is a direct physical mapping between the object and our model of it.
Calculation, however, is as disconnected from the object as a digital music stream is from actual music!
Now let’s get back to the recipe. It also has an output “value” (some cooked rice), but the amount can vary per the data table for different yields. Note also there was an optional step (the butter) and some judgement calls regarding heat and water absorption.
The recipe requires real-time decisions involving information not available to whoever wrote the recipe. For one thing, they have no idea whether you want butter or not. And you might want butter one time but not another time — you don’t know until the recipe is executed.
This ability to do different things depending on conditions when the steps are performed is one of the key distinguishing marks between two hugely important concepts: code and data.
You already have a sense of what data is: information. That sense is correct; data is information, pure and simple. Information Theory says data can always be reduced to binary — ones and zeros — so when we analyze data we think in terms of bits (binary digits).
Code is a very special form of data. It’s data that consists of instructions for some “engine” to execute (or run). A set of instructions that accomplish some goal is called an algorithm. We started this with a simple algorithm for making rice.
The engine that runs code can be a hardware device, such as a CPU, or it can itself be code.
We see the distinction between code and data on the rice box. The recipe is code; that table of how much to use for a given yield is data.
Whether a given chunk of data is code depends a great deal on intent and on the engine that runs the code.
The rice yield table is data for code steps on the box, but if the engine is a cook who knows those steps perfectly, then the table is the code!
That is, the table is what the cook engine uses to create a result. (Assume the amounts are different for different kinds of rice.) At the same time, the table lacks important characteristics required to call it a real algorithm. (In this case those characteristics are in the cook.)
We’ve already encountered one: Code can decide what steps to perform depending on conditions at run-time. The technical (computer science) term is selection, but computer programmers know it as the many versions of the If-Then-Else statement.
To understand another crucial requirement, let’s consider a different algorithm.
Probably many of you have worked in some retail job that required you to count up your “bank” (the money in your cash register) and reconcile it with your sales. You likely followed a series of steps doing that. Maybe you started with the biggest bills and worked down to small change.
But during these steps, you kept track of the sum. It started at zero and grew as you added amounts of cash. Maybe at the end, you compared it to your sales for a match. (What you were really doing there is subtracting one from the other and seeing if the result was zero.)
The point is, not only did you have to keep track of where you were in a series of steps, you also had to keep track of a value object: the total.
Some algorithms have many value objects to keep track of. Consider tallying your credit card purchases into five categories of spending — that takes five sub-totals plus a total.
Programmers know this as the need for variables. Computer scientists refer to it as the need to preserve system state (literally, the state of (some part of) the system).
The final requirement is both involved and not particularly relevant to our purpose here. I’ll mention it only in passing: Code requires, at least, addressable code entry points and an ability to jump to those points (the dreaded GOTO). In many cases, iteration (“looping”) + callable functions covers the need.
So code is a special kind of data — a language. It contains instructions in that language for some engine to execute. We can be very inclusive in what we consider “code” but some code has certain characteristics — selection and state, for example — that make it extra special.
The name for a language with those certain code characteristics is Turing Complete.
We’ll pick it up there next time, but here’s the punchline: One kind of code can do the exact same things as a completely different kind of code, so long as both are Turing Complete!
 Which may be totally passé now, but it’s apt here because we’re talking about what an app really is.
 Polynomial expressions can have multiple answers. For instance: x2 = 4 amounts to solving √4 which both +2 and -2 satisfy. The higher the degree of the polynomial, the more roots (answers) it has.
 In both the mathematical sense of the domain of real numbers and in the ontological sense of concrete.
 Infinite series, in particular, which cannot ever be fully calculated, can (and should) be viewed in terms of the value they attempt to represent.
As a simple example, 0.999… (infinite 9’s) is an expression for a numerical quantity that, hard as it is for some to accept, is identical to 1.000. Another example is any formula for an infinite series converging on pi.
 You can think of them as process and information.
 Typically different code, but nothing stops a code engine from running an instance of itself… which, in turn, could run an instance of itself,…
November 1st, 2015 at 9:08 am
“The recipe requires real-time decisions involving information not available to whoever wrote the recipe. For one thing, they have no idea whether you want butter or not. And you might want butter one time but not another time — you don’t know until the recipe is executed.”
And there there are cooks like me who let the rice boil over because I get distracted easily. So then I run from the other room upon hearing the hissing of lost water, trip over Geordie who runs with me (he knows if I’m running, something’s amiss), grab the pot and spill more water. Then I debate whether or not to add more water, look down to see how much was spilled, add water, then wonder how much time to add to the timer after adding cold water. (This is all bad cooking, but it happens.) Then I realize I want butter, so I add it on top. 🙂
“At the same time, the table lacks important characteristics required to call it a real algorithm. (In this case those characteristics are in the cook.)”
Not quite getting this one. So the table boils down to proportions, right? 😉 Aren’t those proportions enough to be called an algorithm? Or does it have to account for absolutely everything?
The rice example, by the way, is great. I don’t think I would have been able to follow otherwise.
November 1st, 2015 at 2:15 pm
So the rice was nice! (Thanks!) 😀
“This is all bad cooking, but it happens.”
I can imagine, though, that it can lead to great discoveries. I can’t believe anyone invented Crème brûlée on purpose! That had to be an accident; someone not paying attention. 🙂
“Not quite getting this one. So the table boils down to proportions, right? 😉 “
Correct. Just data.
“Aren’t those proportions enough to be called an algorithm?”
Nope (although the line is a little fuzzy in places). Code is distinguished by variables, selection, recursion (or iteration), and the general idea of steps in a process.
The table does have some selection — the butter amount is tagged “optional” — which is part of the fuzz in the line. The rice-making process doesn’t really require saving state, so we don’t see any variables regardless. Recursion also isn’t really relevant here, and the lack of both those elements in the process removes some of the differences between an algorithm and a table.
It’s not that they’re so similar so much as that this algorithm is so simple it lacks properties found in more complicated ones. As such, it can be more or less condensed to table form — certainly if you know what you’re doing rice-wise.
But the kicker is the lack of steps. The table assumes you know the steps (or refer to the directions). Whether to get the water boiling before adding the rice. How long to cook the rice. Whether to stir it frequently, occasionally, or not at all.
And most particularly, the order of the steps. First the water, then the heat, then the rice. The idea of an ordered sequence of steps is a fundamental sign of an algorithm. There is no sequence to a data table.
One example of this is how your internal arithmetic algorithm realizes that math expression has to be processed in a certain order to get an answer. You treat the expression as a code string (rather than the value it implies) and perform the calculation it specifies as a series of ordered steps.
November 1st, 2015 at 5:08 pm
Ah, I hadn’t realized the steps in the process were all part of it.
Not sure how creme brûlée came about, but I’ve heard crepes suzette came about by accident. Fire + orange liqueur turned out to be a good thing. (Ever had them? I made them once and they’re fantastic.)
November 2nd, 2015 at 12:48 am
“…the steps in the process were all part of it.”
In a sense, a process is a series of steps. (That’s a level of reductionism that makes algorithms like other things that also have steps. The property of having steps is necessary, but not sufficient.)
“Fire + orange liqueur turned out to be a good thing. (Ever had them?…”
I’ve had fire (and I’ve had rain) and I’ve had orange liqueur. Both are good things! XD
I had something once I was told was like crepes suzette — a German version. Thin pancakes rolled up with jam in them and powdered sugar sprinkled on them.
November 2nd, 2015 at 7:22 am
Hm, a German version? Homemade?
The crepes suzette are really easy, actually. It’s just crepes + flambé. (And that’s the fun part). They really are heaven.
November 2nd, 2015 at 11:36 am
Nah, it was a dessert in a restaurant in Germany.
As far as flambé goes, my only personal experience was the time we (accidentally) made popcorn flambé. That was when I learned about not (repeat: NOT) throwing water on an oil fire. (I have to say, the scorch marks up the cabinets and on the ceiling were pretty spectacular.)
November 2nd, 2015 at 12:36 pm
Popcorn flambé! Bonne idée!
March 25th, 2021 at 1:22 pm
[…] That said, Age of the Computer is the more appropriate, since the true dividing line is the electronic machines that perform complex algorithms at high speed and with complete accuracy. In reality, the idea of an algorithm predates computers considerably. An algorithm is simply a set of instructions for doing something (long division, for example). […]