incomplete updated introduction

In mathematics, a function is a “black box” that receives parameters and emits a return value. Functions definitions are written like “f(x) = x*2+x” and function invocations like “f(3) = 9”. A pure function is one that has no “side effects”: it only returns its value and does nothing else. A first class function is one that can take other functions, including its own self, as parameters.

The full set of parameters to a function is called its “configuration”. The function’s definition and any parameters it holds at any given time are its state at that moment.

The state of a machine can be serialized to a computable number.

Just as any computation can be represented by a function, it can also be represented by a tape-machine as described in Turing’s paper, or as a “formal language”, or as movements of game-pieces on a board according to rules. There are multiple known “paradigms” of computing, each one representing its own fundamental foundation of mathematics. There are probably many more unknown and undiscovered ones, maybe even infinitely many. How many different types of universal computer do you need?

Possibly more than one: sometimes, problems which on which one kind of Universal Computer never halts might be computed in reasonable time by another kind.

A machine is defined by the thing it is meant to do. The function of any machine may be represented as a computation. This computation may take the form of a mathematical function, or other forms depending on the computational paradigm its authors prefer.
Mechanical machines compute using shapes made of matter. An electronic machine computes in electricity, using switches. Either can be simulated in a universal computer, whether electronic, mechanical, hydraulic or aetheric. It does not matter how the universal computer is implemented, it is still universal up to its practical limits.

Theoretical automata depend on a “tape” of infinite length. In practice only finite-length storage media are available, so in practice some problems are too large to fit in some computers. It can be hard to know ahead of time, and it is impossible to prove whether a given computation will ever end. This is the “Halting Problem”. If you don’t know if the computation has finished or not, you don’t know if the answer you got is an answer or just noise.

It is possible to prove, when the conditions are in place, that a particular computable function in a particular configuration results in a particular number, by running it.
It is also possible to prove that some functions related to an already-proven function will terminate.

proofs about programs

proofs about games

• https://patents.google.com/patent/US9070088B1/en
• tps://langsec.org – meredith patterson’s org, see also thesmartpolitenerd.com

tony hoare on program correctness
“the problem of program correctness”
SICP, r6rs et al.
(jeff atwood?)discourse guy’s blog esp. moderation bits
https://www.schneier.com/blog/archives/2023/12/ai-and-trust.html?

• file:///home/levity/Desktop/science-of-insecurity.ogg
• file:///home/levity/Desktop/trust/TrustReputationAgentsEvoGames&SocialNet.pdf
• file:///home/person/Desktop/trust/trust.pdf

Machines are made of parts, the interaction of the parts defines its function

Machines are computers in that every machine’s specification is computable: modern computers routinely print out other machines, and could in theory reproduce themselves.
Most computers are not universal computers.

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 potentially more reliable, than this idea suggests.

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.