Introduction, as introduced.

Ideal machines are machines that exist as ideas. These are useful in mathematical models, and as blueprints for “real” machines.
Components of ideal machines are shapes whose relative motion is constrained by the joints that connect them.

A computer program can be treated as an ideal machine in that it exists only as an “idea” written down in the computer’s memory. “Virtual machines” are computer programs that emulate the function of a “real” computer (one made out of matter) and which can, in turn, run programs within their own memory space. It’s impossible im principle (though sometimes possible in actual implementations) for a program to tell whether it’s run by a “virtual” machine or a “real” one.

Regardless of “realness” of its runtime, a computer program is a virtual machine. Every program is a computer [cite:SICP], but not necessarily a universal one. Programs which are universal computers are called “virtual machines” or sometimes “emulators”. These two are not identical, but the distinction is out of scope for this document.

A system is a machine composed of two or more other machines. A machine like a lever, designed to do only one simple computation (multiplier), is a “simple” machine. A scissor jack, which is a screw plus some levers, is a system. Systems can contain other systems, and some of them contain jacks. Using cars as an example again, cars have different systems: a “drivetrain” or traction system; a chassis-electrical system; and a brake system are common examples. A car’s traction system might contain an engine, which is a system that contains its own electrical system and a cooling system; the engine-electrical system contains a charging system, containing an alternator containing a rectifier containing diodes. Diodes are so simple that they probably don’t count as a system- but it depends on who is counting. As far as I know there is no hard-and-fast rule about what is a system and what isn’t. I would say that a component that is designed to do only one thing, like a diode, is not a system- but anything more complex than that might be.

A system is defined by components, which may be systems; and by the connections between those components, or interfaces. As joints constrain the relative motion of beams in the kinematic model of a machine, so interfaces constrain the interactions of components of a system.[cite:systems-engineering]

It’s a well-known idea that complexity is the inverse of reliability: that is, the more complex something is, the more ways it can go wrong. It’s a useful rule-of-thumb, but the reality of machinery is both more complex and more reliable than this idea.

Complexity in physical machinery is usually thought of in terms of likely failure rates of components and the number of and connections between these components. For example, a suspension bridge has more cables than quite necessary to hold the bridge up. Fewer, stouter cables might seem to be less complex and therefore more reliable, but having a larger number of thinner cables offers resilience against collapse due to cable failure. A system like such a bridge, deliberately built with greater capacity than its rated load, is called “overbuilt”. Overbuilding adds a “fudge factor” in static components, and in the case of our bridge cables, means a larger number of wearing components can fail at the same time without endangering the system of which they’re a part. Either way uses the same amount of steel and provides the same amount of strength to hold the bridge up. More cables means more expense- thinner cables aren’t any cheaper to hang- but over time, as worn cables are replaced in maintenance, a large number of small cables means a greater proportion of new cables at any given time after the first maintenance interval. If thin cables fail faster than thicker cables do, then they will be a slightly higher cost in maintenance to reduce emergencies- specifically the emergency that occurs when the number of failed cables gets too close to the critical number. The bridge might not fall down at that point, but it’s definitely time for something to happen in order to prevent it falling down!

Complexity in structure is represented in terms of components, subsystems and the connections between each. It’s measured in degrees of freedom (how much a beam can move along its joint with another beam) or bits (or calories) of entropy. Entropy is a measure of the “disorderedness” of a system, which is a reasonable proxy for its complexity in some contexts.

Complexity in process is represented in terms of operations, the “space” needed for the operation to occur and the “time” to perform it. In industrial processes design, the space and time are usually architectural concerns, the same space and time will be experienced by humans performing or observing the process. Computer operating systems also have the concept of a “process”, which is a sort of unit of computation, the lifetime of a running program or sub-program. A process has an ID number, a wall time, a nice value, some other values. Its “space” is bits of computer memory and its “time” is processor cycles.

Computer science measures complexity in a few different ways. One of the most popular is “Big O” notation, where a problem is shown to “grow” in complexity in relation to the size of its inputs. For example, a program that lists all the permutations of a string might be O(n!), meaning that O grows as the factorial of n, the input string. If you enter a string of 5 characters, for example, the program will have to list out 5*4*3*2*1 lines of output. The science of measuring and computing complexity is called “complexity theory”.

In computer programs, complexity is an aspect of reliability, in that for certain problems we can know in advance (for example) that a correctly-working program must have an output greater than a certain number. When a program’s outputs grow beyond what we expect from the problem, this can directly result in the machine going wrong, via memory leaks, buffer overruns, storage running out of space, and so forth.

The design of most machines is meant to accomplish a fairly specific, well-defined task or set of tasks. It’s clear, in the case of these machines, that any behavior that does not serve to accomplish these tasks is “going wrong”. Other machines, less well-defined, can’t really be said to be “going wrong” unless someone is unhappy about the way they are going. Your car isn’t supposed to explode (except inside the cylinders), and you are likely to be unhappy if it does- so that’s a clear case of “going wrong”. If your car turns into begonias, the case is less clear: maybe you prefer flowers to Fords.

Some machines, especially computer programs, can become transformed into a different sort of machine than they were intended to be. There is no design intent behind these “weird machines”, and they can never be said to be “going right”- by their supplanting of an intended machine, they are necessarily “going wrong”, even if they are doing something good.

In software engineering, “compliance” refers to the faithfulness of an implementation (the “actual machine”, the computer program as it runs) to its specification (the “ideal machine” that serves as a blueprint for the type of machine to be implemented).

There are many ways to specify a machine, some of which are capable of being run as computer programs (and are therefore machines in their own right). Some of these programs produce an implementation as output. For example, the program YACC takes a specification for a parser in the form of a source grammar, and produces that parser as output. For some such programs, a proof exists that the generated program will always be compliant with the specification, though definitions of “perfectly compliant” may differ. It’s one thing to prove a machine will always do a thing, and quite another to prove it can only ever do the thing. Most machines that are capable of going right are capable also of going wrong, or of failing to go at all. A machine can sometimes appear to be doing one of the three, while actually doing one of the others. This is often due to vagueness or missing cases in the specification or other human errors, but sometimes the problem goes deeper.

For some classes of problems, a proof exists that we can never know in advance whether the machine will go right or wrong. We just have to wait until it stops to find out, and it might not ever stop. These problems are referred to as “undecidable”. A famous example is Godel’s Theorem, which proves that the statement “This statement S is not valid in logical system L” is undecidable for some L which allow statement S. This is equivalent to Harry Mudd on Star Trek telling the computer “This statement is a lie” (OK, that’s not how it went down on the show, but the example is isomorphic and simplified).

Isomorphism is a property of logical statements or systems that have the “same shape”. The statement “This statement is false”
is neither true nor false, because if it’s true it’s false, and if it’s false it’s true. This outcome is the same for Russell’s Paradox about the barber that shaves everyone who doesn’t shave himself; for the Harry Mudd episode aforementioned; for Godel’s Theorem; and crucially, for Alan Turing’s proof of undecidability of the “entsheidungsproblem” in his famous paper.

Isomorphisms are a powerful tool in mathematics, and certain proofs of isomorphism have opened up entire new fields in computer science (and probably other fields of which I’m less informed). For example, the Curry-Howard isomorphism between proofs and programs enabled a type of program called “automated theorem provers”, which use intuitionistic logic to assist people in constructing mathematical proofs. Some of these provers, like Agda and INRIA’s Coq program, can take these finished proofs and output a program that implements the specification that the proof represents. Since these outputs are provably isomorphic to the proof from which they are constructed, they are the closest thing to a perfect implementation we can hope for.

A Universal Turing Machine is an ideal machine. It is a special one, because it is the original general-purpose computer. A UTM can compute any computable problem. It is the basis for the things we call “computers” in our daily lives.

A Turing Machine, Universal or not, consists of a tape divided into cells, a head which can go forward or back a cell and detect, write or erase a mark in the cell it’s on, and a “state table” which determines the action the head should take each “turn” based on the “state” of the head and the tape: for example, an entry in the table might be something like: “if the head went left to get here and there’s a mark here, move left and write a mark.” These components are enough to compute some classes of problems. A UTM has some additional components which allow it to compute any computable problem.

You might notice that these components sound a bit like board-game equipment, albeit for a weird game that might not be much fun to play. In fact the UTM also can be modelled as a game using chess board and pieces, go stones and board, and other such components. You can even model a UTM by yourself with a notepad and some graph paper. It’s easy, but tedious. You might not think it’s worth doing, and I wouldn’t ask you to do it. However, some people have done it already- and the fact that it’s been done is a constructive proof that it’s possible to do. This means there is not one, but many proven isomorphisms between specific Turing Machines and particular games.

Not only that, but there is a proof of isomorphism between the space of possible Turing Machines and the space of games. #cite I THINK THIS IS TRUE BUT I NEED TO LOOK THIS SHIT UP