“Tarski has stressed in his lecture (and I think justly) the great importance of the concept of Turing’s computability. It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.” – Kurt Gödel
What do well-being, energy, knowledge, computability, truth, continuity, and beauty all have in common? They are each general notions that human beings understand intuitively, which become incredibly slippery when one attempts to extract or derive an exact definition. I can ask someone if they find something beautiful, and they can usually answer simply yes or no, but to demand a definition from them which covers all things they will or have ever found beautiful is absurd.1 With knowledge, the story is substantially less polarizing and epistemology exists to answer the question of what exactly constitutes that which is meant when we say one knows something. For energy, continuity, and computability it may seem these are not philosophical questions, however the goal of notion to definition is (or at some point was) the same. Arguably these are no longer seen as philosophy simply because the notions have found definitions which were resounding successes in another academic field. For energy Leibniz gave his model of vis viva (“living force”), which is still today the definition of a body’s energy of motion. Similarly there was at a time, a shared notion of continuity in the discussion of functions in mathematics. Bolzano and then Weierstrass, gave a model which captured this notion to nearly everyone’s satisfaction known now as (ε, δ)-continuity. In the 1930’s computability was undergoing the same transition with Alan Turing, Alonzo Church, Kurt Gödel, and others, attempting to give a hard definition to this shared seemingly imprecise notion. I’ll be using this example as a case study.
Mathematicians, Logicians, and Philosophers alike all had this notion of problems which were “effectively computable”. Problems for which there seemed to be a procedure one could follow to always obtain a correct solution. The goal wasn’t simply to discuss the problems at hand, but to discuss the methods of solving said problems themselves. A familiar example of an effectively computable problem is multiplication. In grade school you were almost certainly taught long multiplication, a procedure which you can follow to produce the result of any multiplication. Sudoku is another example of a computable problem, as one can simply try every combination of numbers on the empty grid squares until one works; though it may take awfully long, it is a process that hypothetically could be carried out and guarantees a correct answer. The longer one thinks about these kind of problems, a common underlying set of properties emerges. A generally agreed upon definition for an effective method came about:2
- The method always produces a correct answer.
- The method will finish after a finite number of steps.
- The method consists of a finite number of exact instructions.
- The instructions need only be followed rigorously to succeed. It requires no ingenuity during the process.
- In principle, the method can be performed by a human without any aids except writing materials (for this reason, effective methods are sometimes called “paper and pencil methods”).
The requirements are listed in order of how strongly they depend on other human-centric notions: for starters, just how exact need an exact instruction be? Nevertheless we press on, happy to have made any progress on the imprecise notion. Important to note is the relationship between the problem and the method: a problem is effectively computable if the problem can be solved by an effective method.3 With the acknowledgement that we may “brute force” many problems like Sudoku above, it becomes difficult to imagine there are any problems which don’t fit into this camp. In fact there are plenty: in Conway’s Game of Life one can ask, given an initial pattern and a second pattern, whether the latter pattern can ever appear from the initial one. This seems fine, the question is quite well defined, and the rules of the game are rigid, however as it turns out this problem is not effectively computable.
There were (and are) many problems like those above, where algorithms had been discovered which seemed to be effective methods, and what people like Turing and Church were working on was finding a general frame work, or a model, where these effective methods could be codified and preformed more rigorously, so as to move past the questions of what exact meant, or discussion of what can and cannot be done with paper and pencil. Many different models of computability were proposed: Turing came up with Turing Machines, Gödel had his general recursive functions, and Church came up with what is known as Lambda-Calculus. This spurred three competing classes of computable problems: those problems for which solutions could be computed by methods encoded by a Turing machine, methods encode-able by λ-calculus, and those problems which could be encoded as general recursive functions. The latter two are quite involved for a simple blog post, but a Turing Machine is quicker to explain and imagine.
(If you are familiar with Turing machines skip this paragraph) The model is as follows: there is a tape which extends at one end to infinity with discrete uniform blocks containing room for a single symbol (typically a 1 or 0). The tape is fed into the Turing Machine “tape head”. On each step, the machine can read the current symbol on the tape, overwrite what is currently at the spot on the tape, and/or move left or right one square. Based on the input from the tape, the machine can enter one of its “states”, and what state the machine is in decides what the machine does on the following inputs, etc. That is it. Here is an example of a very simple Turing machine, which decides whether a binary string has an even number of 0’s in it (here the machine is assumed to start in the even state (no 0’s, is an even amount of 0’s), move the head right on each step, and only reads from the tape, never writing):
The are two states (labelled with what they happen to correspond to with regard to the input string (this isn’t always so obvious)) and the arrows tell us how to transition from one state to the next, based on the input from the tape. If the following tape was input
the machine would end up in the odd state, and so the Turing machine would output false, and you would know the string has an uneven number of 0’s.
Notice here that it is the algorithm (method) of detecting even numbers of 0’s which is encoded in the structure of the Turing machine. The inputs (instances of the problem) are always what is encoded on the tape. That is why the Turing machine is a model, because instances of problems need to somehow be faithfully encoded into some sort of tape-friendly form. The same is true for the λ-calculus and recursive functions. Hopefully you can now see how the model, in demanding everything have a tape-friendly encoding, could maybe miss some set of computable problems. Perhaps this 1 dimensional set-up is too restrictive. It seems entirely reasonable that perhaps 2 tapes could encode more problems, or more complicated problems. Or perhaps having two tape-heads which both move, could deal with a greater class of problems. Similar suggestions can be brought up for the other models of computing.
The miraculous fact however is that this is not the case! Not only do these modifications to the Turing machine fail to broaden the class of encodable problems, the above three classes of computability perfectly overlap each other, and there has never been a problem which has a known effective method that could not be encoded as a Turing machine. This is known as the Church-Turing Thesis. “Every reasonable and general model of computation is no more powerful than that of the Turing Machine” or equivalently “A problem is effectively computable if and only if it can be implemented as a Turing Machine”.4 The most important piece of this is that it is a Thesis (conjecture), not a theorem or a proof. It is a very specific and well-defined model, of a notion many thinkers shared over the years, which has never once failed to be satisfactory. Evidence for the thesis aside from the proof of the equivalence of the three models of computation, is that there have since been novel models of computation such as Markov’s Markov algorithms, and Post’s canonical systems, both of which have been shown wholly equivalent to the model of Turing machines.
Turing’s computability is a most wonderful example of an epistemological leap; much like vis viva and (ε, δ)-continuty, it is not derivable, but something which many people felt they shared an understanding of, and worked together to put a face to the name, as it were. If nothing else I hope this post serves as a reminder of the intimate relationship between philosophy and model building in the sciences. Much of philosophy is simply this same problem, of notion to definition and only once the problem is adequately solved, do we admit the problem to another field.
Footnotes
1. Objective aestheticians please don’t come after me.
2. en.wikipedia.org/wiki/Effective_method
3. The problem may be solvable other ways, like guessing, but simply being solvable doesn’t mean computable. Computable means your method of solving the problem is repeatable.
4. Those more familiar with the language of theoretical computer science should replace the words “implemented as” with “decided by”.
The Third Triumvirate 