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,…