Computability and Complexity

A symbol is one mark you are allowed to write in one square. Which marks are allowed is up to whoever designs the machine, and the list is fixed before it starts. In this course the marks are the digits 0 and 1, a few letters such as X and Y, a plus sign and one more: an empty square.

An empty square needs a name, because rules have to be able to mention it. It is called the blank, and it is written as an underscore, _. On screen an empty square is drawn with a dashed edge so you can tell it apart from a square holding a real mark.

Because the tape is doing the rest of the remembering. The state only has to hold what the machine cannot write down: which part of the job it has reached. Something like "I am searching for a plus sign", or "I have seen an odd number of 1s so far". A handful of words covers that.

The number of different words allowed is fixed and finite, and that matters later. A machine cannot have a state for every number it might meet, because there are infinitely many numbers and only so many words. Anything the machine wants to count has to be counted on the tape.

They are not allowed to. Each pair of state and symbol may appear at most once in the table. If two rules both started with seek 0 the machine would have a choice, and then nobody could say what it does. A machine with no choices is called deterministic and every machine in this course is one.

This is not a small technical detail. It is what makes the machine trustworthy: run it twice on the same tape and you get the same answer both times, every time, because at every step exactly one rule applies. The editor below will tell you if you write the same situation twice.

Because it keeps the first adding machine short enough to read in one go. A machine that adds ordinary written numbers, with carrying, is perfectly possible and takes about twenty rules; a machine that adds tallies takes five. Nothing about what a machine can do depends on the choice. It only changes how many squares a number takes up and how many steps the work costs.

That difference is real, though, and Step 7 comes back to it. Written as tallies, the number one million needs a million squares. Written in the ordinary way it needs seven. When people measure how slow a method is, the size of the written-down input is what they measure against, so the choice of writing changes the measurement.

An algorithm is a method written out in enough detail that something with no judgement at all can follow it and get the right answer every time. No steps left to common sense, no "and then sort it out somehow". Long division is an algorithm. A recipe that says "season to taste" is not.

A rule table is an unusually honest way of writing one down, because the machine that follows it really does have no judgement. If a rule table works, there is no argument about whether the method was described properly: you can watch every step of it happen.

Three tallies, a plus, two tallies. If you rubbed the plus out entirely you would have five tallies touching, which is the answer, but the machine cannot rub something out and close the gap: a square cannot be removed from the strip, only overwritten. So it writes a 1 in the plus sign's square instead. Now the strip reads six 1s in a row, one too many, and the fix is to delete any single one of them.

The machine deletes the last one, because getting to the end is easy: walk right until you meet a blank, then step back one. Walking left to the front would work just as well and cost the same.

Look for a rule whose first word and last word are the same. walk 1 -> 1 R walk reads the symbol, leaves it alone, moves right, and comes back to walk. If the next square also holds a 1, the same rule fires again. That is a loop, and it keeps going for exactly as long as the condition holds, which here means until the head meets something that is not a 1.

The way out of the loop is another rule starting with the same state and a different symbol. In a familiar language you would write "while the square holds a 1, move right". Here the while and the condition and the body are all folded into two lines.

It could be either. Writing Y or N in a square would work perfectly well, and some books do it that way. Using the stopping state is slightly tidier because the machine does not have to tidy the tape first, and because the thing we care about from Step 5 onwards is what a machine does rather than what it leaves lying around.

A machine that answers a yes-or-no question and always stops is said to decide that question. Hold on to that word. Almost everything in the second half of this course is about which questions can be decided and which cannot.

Because of how many separate attempts landed in the same place. Alonzo Church built a system out of nothing but functions being applied to other functions. Alan Turing built the tape machine. Kurt Gödel and Jacques Herbrand built one out of equations about whole numbers. Emil Post built one out of a queue. All of these were done at roughly the same time, by people working differently, and each system turned out to be able to imitate every other one exactly.

Every computer built since fits the same pattern, which is the part that matters for the rest of this course. A limit proved about the strip of paper is a limit on every machine anybody has ever managed to build, including the ones that do not exist yet. That is why Step 5 is allowed to say "no computer" and mean it.

A string is a row of symbols one after another, in a definite order, with a definite length. hello is a string of five symbols. So is 111+11, and so is the whole contents of a tape between the first and last mark. The name is old and comes from the picture of beads strung on a thread.

The word gets used constantly in computing because so many different things turn out to be one: text, a program's source, a picture file, a message crossing a network. All of them are rows of symbols that some agreed convention says how to read.

The reason a laptop is not sold as a chess machine, or a word machine, or a spreadsheet machine, is that it is a universal machine. The programs on it are not part of it. They are strings sitting in storage, and the machine reads one and behaves like whatever that string describes. Change the string and the same hardware becomes a different machine.

Before this idea, a machine that did a job was built to do that job. Turing's paper of 1936 described the universal machine years before anyone had built an electronic computer at all, and every general-purpose computer since has been one.

A real universal tape machine does the reading and obeying with nothing but its own rule table, and it is a slog: a few hundred rules and a great deal of shuffling back and forth between the description and the working area to look up each step. Every serious textbook builds one and nobody enjoys it. In the lab above, that shuffling happens at full speed instead of one square at a time, so the idea is watchable.

The part that would be cheating is not happening. The rules being obeyed are read from the top strip, symbol by symbol, and if you write nonsense there the panel below reports that it could not make sense of the description, exactly as the real machine would grind to a halt on it.

Run it, and one of two things happens. It stops. You have your answer. Or it is still going. You have learned nothing, because "still going after a million steps" and "going for ever" look identical from the outside and always will. There is no moment at which waiting turns into knowing.

You might try setting a limit: run it for a million steps, and if it has not stopped call it a non-stopper. That method always gives an answer, and it is wrong about every machine that stops at step one million and one. The lab below has a machine that runs for over a thousand steps and then stops. It is not doing anything odd.

It is a way of proving something is impossible without having to check every possibility. You pretend the thing exists, follow the consequences honestly, and arrive somewhere that cannot be true. Since the reasoning was honest, the fault has to be the pretence, so the thing does not exist. This is called proof by contradiction.

Small example. Suppose there is a largest whole number, and call it L. Then L plus 1 is a whole number, and it is bigger than L. So L was not the largest after all and the supposition has eaten itself. Nobody had to look at every number. The argument on the cards has exactly this shape, with a machine in place of a number.

Suppose a perfect stopping-detector exists. Build a machine that asks the detector what it will do, and then does the opposite. Ask that machine about itself. Whatever it does, it does the opposite of what it does, so the detector was never perfect. That is the entire argument and every extra sentence in the cards is there to keep it honest rather than to add anything.

The same shape of trick shows up elsewhere."This sentence is false" has no truth value for the same reason. What Turing added was the observation that a machine can be handed its own description, which turns a word game into a fact about every computer that will ever be built.

Pick any single machine and any single input. Either it stops or it does not, and that fact is already settled, whether or not anyone knows it. For most machines you meet, working out which is easy: the adder from Step 2 obviously stops and a rule that sends the head right forever on blank tape obviously does not.

Undecidability is about the whole collection. There is no one machine that gets every case right. There are always cases left over, and no amount of adding special-case tests to your checker will finish the job, because the argument in Step 5 can be run against your improved checker just as well as against the original.

A compiler is a program that turns the code a person writes into the instructions a machine runs, and on the way it inspects the code and points out things that look wrong. Those warnings are honest because of how they are phrased. A compiler says "this loop cannot exit", not "this program halts". It only speaks when it is certain, and stays quiet otherwise.

That is allowed, and it is useful. It is not a solution to the halting problem. A checker with three possible answers, yes, no, and I cannot tell, is easy to build and never wrong. A checker with two possible answers that is never wrong is what cannot exist. The lab below is exactly such a three-answer checker. You are invited to defeat it.

Far from it. A result called Rice's theorem says that essentially every interesting question about what a program computes is undecidable. Does this program ever print the number 7. Do these two programs always agree. Does this program ever touch that file. All undecidable, and each one is proved by showing that a machine answering it could be turned into a machine answering the halting problem, which Step 10 shows you how to do.

Questions about how a program is written stay perfectly answerable: how many lines it has, whether a particular word appears, whether every bracket is closed. The line runs between the text of a program and its behaviour. Anything about the text is fair game; almost anything about the behaviour is not.

Go along the list and make one decision per number: in the group, or out of it. Two choices for the first number. For each of those, two choices for the second, so four so far. Then eight, then sixteen. With n numbers you get 2 multiplied by itself n times, which is written 2ⁿ and said as "two to the n".

Small numbers hide how fast this moves. Ten numbers give 1024 groups, which is nothing. Twenty give just over a million. Forty give over a million million. Each single extra number doubles the entire pile, which is why the counter in the lab below goes from comfortable to hopeless in about ten presses.

Seconds are a property of the machine you happened to use, the other programs running that day, and how warm the room is. Steps are a property of the method. Run the same method twice on the same input and the seconds differ while the step count is identical, which makes steps the honest thing to compare.

To turn steps into a feel for time you pick a speed and multiply. A modern processor manages something in the region of a billion simple steps a second, and that figure is what the next lab uses. It is a rough figure, deliberately generous, and being generous does not save the exponential method.

n² means n times n. It is the number of ways of picking an ordered pair out of n things, which is why any method that compares everything with everything else lands on it. n³ is n times n times n, the number of ordered triples, and it shows up when a method has three nested walks through the data.

The difference from 2ⁿ is which part grows. In n³ the base grows and the exponent is stuck at 3. In 2ⁿ the base is stuck at 2 and the exponent grows. That swap is the entire distinction, and the second lab in this step shows how brutal it is.

A class is a bag with problems in it, and a rule for what gets in. The bag called P holds every yes-or-no question for which somebody has found a polynomial method. Is this number in this sorted list. Is there a route from this town to that one. Does this list contain a repeat. All in P.

Membership is about the problem, not about your particular attempt at it. A problem is in P the moment any polynomial method exists, even if the method you personally wrote is exponential, and even if nobody has yet noticed the fast method. That last part matters: problems move into P when someone finds a better method, and several famous ones have.

Because the line has two properties nothing better has managed. It does not change if you swap the kind of machine: a method that is polynomial on a tape machine is polynomial on a laptop, with a different exponent. And polynomials survive being combined, so a polynomial method that calls another polynomial method a polynomial number of times is still polynomial. A line drawn at, say,"under a million steps" has neither property.

The practical defence is that the line turns out to bite. Problems with polynomial methods almost always end up with small exponents, usually 3 or less, once people have worked on them for a while. Problems without one usually have nothing at all. The middle ground the objection worries about is oddly empty.

A graph in this sense has nothing to do with charts. It is a set of dots, called nodes, and a set of connections between pairs of them, called edges. That is all. The picture on screen is only one way of drawing it; sliding a dot around changes nothing, because a graph is the pattern of connections and not the positions.

Graphs are used for anything made of things and relations between them: towns and roads, people and friendships, tasks and which must come first. Colouring with the rule that joined dots differ is how timetabling works. Dots are exams, an edge means some student sits both, and a colour is a time slot.

It stands for nondeterministic polynomial time, which is a mouthful from an older way of describing the same bag. Imagine a machine allowed to make guesses, which magically always guesses correctly when a correct guess exists. Such a machine solves colouring in polynomial time by guessing the colours and then checking. Nobody can build one, but it defines the same collection of problems as the checking definition, and the checking definition is the one to keep in your head.

The misreading matters because "not polynomial" would mean NP and P have nothing in common, and the truth is the opposite: every problem in P is also in NP. P sits inside NP. The open question is whether it fills it.

You cannot measure the height of a tall building, but a friend has an accurate way of measuring shadows and angles. You turn your problem into theirs: measure the shadow, measure the angle of the sun, hand those over, get a height back. You have reduced building-measuring to shadow-measuring, and shadow-measuring is now at least as useful as building-measuring.

Notice the shape. The translation has to be something you can actually do, the answer has to come back meaning what you wanted, and none of it says a word about how your friend does the measuring. That indifference is the strength of the method: you can use a solver you know nothing about.

Each switch gets a name. A requirement is written as a short list of switch names inside brackets, joined by "or". A plain name means that switch must be on to satisfy the requirement; a name with not in front means it must be off. So (a or not b or c) is satisfied if a is on, or b is off, or c is on. Each such requirement is called a clause.

You must satisfy every clause at the same time, using one setting of the switches. A single clause is trivial. Hundreds of overlapping clauses, where turning a switch on to rescue one clause breaks three others, is not. Every setting of 20 switches means a million possibilities, and the counting from Step 7 applies exactly.

If translating took exponential time, the reduction would prove nothing. You could always "reduce" anything to anything by solving the first problem during the translation and then producing a trivial question with the right answer, which is cheating dressed as a proof.

So the rule is that the translation must be polynomial. In the lab above it is better than that: one clause per dot, three per dot to stop two colours being on at once, and three per edge. That is a fixed amount of work per piece of the picture, and you can watch the clause counter to confirm it grows in step with the number of dots and edges rather than exploding.

By reducing the definition rather than the problem. Being in NP already tells you everything the proof needs: there is a checking machine, and it stops within some polynomial number of steps. You never have to know what the problem is about. You only need its checker and the construction turns any checker whatsoever into clauses.

This is the same style of argument as Step 4, where the universal machine ran a program it had never seen by reading its description. Once a machine is a description, general statements about all machines become possible, and Cook's proof is the most powerful thing anybody has done with that.

In NP means answers can be checked quickly. That is a ceiling on difficulty, and easy problems qualify: adding two numbers is in NP. NP-hard means everything in NP reduces to it, so it is at least as hard as all of them. That is a floor, and it does not require the problem to be in NP at all; the halting problem is NP-hard and is not in NP.

NP-complete means both at once: in NP, and NP-hard. Those are the problems sitting exactly at the top of NP. They are the interesting ones, because a fast method for any single one of them would be a fast method for every problem in NP.

Most of the locks. Public-key cryptography, which is what makes online payment possible, rests on certain problems being easy to check and hard to solve, which is exactly the NP shape. A fast method for SAT would very likely undo a large part of it. On the other hand, protein folding, chip layout, timetabling and thousands of scheduling problems would fall out at once, which would be a considerable compensation.

Two cautions. A proof might be non-constructive, showing a fast method exists without saying what it is. And a method taking n¹⁰⁰ steps would settle the question while changing nothing whatever in practice. Even the dramatic answer might arrive quietly.

Given an enumerator, wait until the target string appears. Given a recogniser, dovetail it over every possible string and print a string when its run accepts. This is an exact equivalence.

A sound analyser says safe only with a proof. For many behaviours, no analyser can be both sound and complete over all programs. Tests add evidence from selected runs; they do not cover every input.

A unit-cost model treats addition or multiplication as one step. For very large integers, their bit lengths matter and arithmetic itself takes more work. State which model is being used before comparing algorithms.

PSPACE allows polynomial memory even when time is much larger. Games and quantified formulas alternate choices. The Complexity Classes course develops this map.

Interval graphs, planar graphs, bounded treewidth and metric distances can change what is solvable or approximable. Restricting inputs is legitimate when the real system guarantees that structure and validates it at the boundary.

Continue with Complexity Classes, Algorithm Design and Quantum Algorithms. Quantum computation does not decide halting.