You Are Not a Turing Machine

ChatGPT is

Large Language Models (LLMs) like ChapGPT and GPT-4 continue to impress people with their calculating ability, to the extent that there are people saying these models are "intelligent".

So it seemed like a good time to talk about a proof that humans can do things that calculating machines can't, which shows we are more than just calculators.

This kind of discussion is generally put in terms of Turing machines, which are a kind of schematic model of any computing device. Alan Turing was a British mathematician who showed that anything that can be computed can be computed by a Turing machine, which means that any sufficiently powerful computer is "Turing complete": it can compute anything that any computing machine can. This was a very important result back in the 1930's, and one way of looking at it is that if it were not true then a Mac, say, might be able to compute some things but you'd have to buy a PC to compute others. Turing completeness tells us this isn't so.

But it also means that if we can find something that we can figure out but a Turing machine can't, then we are not simply computers.

Turing's imaginary machine consisted of an infinite paper tape that is divided into cells, a read/write head that can read and write symbols from and to the tape at the head's current position, a rules table that tells it what to do when it reads a particular symbol, and a state register that keeps track of what sub-set of the rules table applies to the current situation.

The machine goes through a cycle of steps: it first reads the symbol in the cell under the head at the moment, then looks up that symbol in the sub-section of the rules table that the current state tells it to use, and based on the result it may write a new symbol at the current head position, and then move one cell either left or right.

The cycle then repeats itself.

Despite being relatively simple anything that can be computed by any automatic device can be computed by a Turing machine.

To show we aren't Turing machines all we have to do is find a problem we can solve that a Turing machine can't. Fortunately, we know that there is a general problem that no Turing machine can solve, which is called the halting problem.

This is a question of interest to anyone who uses computers to calculate things: "Will my program eventually stop? Or will it get stuck in an infinite loop?" It would be nice if we had a program--which is conceptually just a Turing machine--that could take another program as its input and tell us if that program is going to come to an end eventually, or if it's going to keep running forever.

For example, in a lot of the kind of numerical computation I do for fun and profit there are questions of "convergence": will an iterative algorithm converge on a definite answer, or will it end up bouncing endlessly around the answer but never settling on it?

The "halting problem" in formal terms is: is there a Turing machine that can determine when another Turing machine eventually stop?

The answer to this question is: No. There is no Turing machine that can solve the halting problem for any possible machine that could be fed into it. This was a major result in the limits of computation, proven in various ways by Turing himself, his doctoral advisor Alonzo Church, and others.

So we know there are cases where no program can tell us if another program will halt. Can we tell if the other program will halt in any of these cases? If we can, then we're not Turing machines.

To answer this question we need to look at an instance of the halting problem that a machine can't solve.

Since Turing machines can implement any computation we can write this proof in terms of ordinary software, confident that we're still talking about the formal mathematics of Turing machines underneath. So what we want is a function that tells us if another function will eventually return.

In most programming languages it's possible to define functions that do something to the values passed into them, which are called "arguments" for some reason. A typical function definition might look like:

def add(int i, int j): 
    return i+j

In this case, i and j are integers (denoted by the "int" in front of them) and the function returns their sum. Somewhere else in the program we can call the function:

n = add(2, 2)

and expect the result would be 4, because that is what two plus two is always equal to.

Modern programming languages allow us to pass functions themselves as arguments to other functions:

def H(func f):
    return <<something to do with f>>

A common use of this method is "decorate" the function passed in with some additional functionality and pass back a new function that is defined inside the one doing the “decorating”. Assume we have a function like "add" that takes two integers as arguments. We could decorate it like this:

def D(func f):

    def g(int i, int j):
        print("I'm calling g!")
        return f(i, j)

    return g

The function returned by D then can be called wherever add() is called, and will print out the fact that it's being called before adding the two arguments:

padd = D(add)
n = padd(2, 2)

would result in "I"m calling g!" being printed, which while not useful is at least demonstrative.

Functions can also answer questions about functions, like, "Does the function passed in as an argument halt?" which we know from Turing's proof can't be answered in all cases.

There is a simple conceptual proof of this due to Christopher Strachey: assume there is a function H that returns True when the function passed to it halts, and False when the function passed to it goes into an infinite loop. Then construct a function g of the form:

def g():
    if H(g):
        LOOP

where "LOOP" is code for an infinite loop, and is only run when H(g) returns True.

To find out if g() halts, we should be able to call H(g) and wait for an answer. But...

...because g calls H on itself, if H(g) returns True (implying that g halts), then g() actually goes into an infinite loop, and if H(g) returns False, then g does not go into an infinite loop.

That means H cannot return either True or False. It cannot determine if g halts.

But we can: since H(g) can't return, neither can g.

Ergo: we are not Turing machines, because we can do something a Turing machine can't.

ChatGPT is a Turing machine. It is in fact an almost perfect Turing machine: it has nothing but input and output and can't do any real-time searches or the like. A Turing machine is not a robot: it has no sensors and no effectors. It just reads symbols off its tape, which is assumed to have a definite string of symbols on it from the start, with no later additions or deletions or changes.

It follows from this that there will be things that we can do that ChatGPT and other LLMs can't, and when one of them does something that starts to look a lot like what a conscious being can do we should ask how it's doing it.

This has been coming up a lot lately, as people have been feeding various LLMs different kinds of test for basic reasoning ability, and finding that they do remarkably well. But before anyone shouts "It's alive!" we should go back to this paper from a few years ago, which found the same result: models that were relatively simple by today's standards appeared to be able to reason, which is pretty strange when you consider that reasoning was simply not in their purview. All they did was compute what symbol to produce next based on the statistical properties of the data they have been trained on. That mass of statistical properties is nothing but the rules table of a Turing machine.

And it turns out that is what they were doing: the questions had statistical regularities that led the model to generate appropriate output without any reasoning involved. The authors were able to restate the problems in "adversarial language" that lacked those hidden statistical cues, and the models performed no better than chance, although humans--who are not Turing machines--would have no problem with them.

The trick of the proof above, you'll notice, is self-reference. By embedding a call to H() in the function g(), we can ask a question that is undecidable by H().

Unlike formal systems, reasoning--which is embodied--handles self-reference just fine. Is there a town where there's a barber who shaves every man who doesn't shave himself? Nope. It doesn't matter that we can formally define such a thing. It still doesn't exist.

The knowable part of reality has constraints that logic does not. The unknowable part of reality is free of some constraints that logic has. Logic--and mathematics in general--are formal systems that are sometimes useful in describing the world, and nothing more: the world is not governed by math or any other formal system. It is described by them, sometimes, more-or-less.

Turing machines like ChapGPT are not able to deal with the world in a complete and consistent manner, and fail badly when they reach their limits. Human beings, however radically incapable we may be, tend to fail somewhat more gracefully.

===

Editorial Note: World of Wonders is powered by Substack, which has recently added a Twitter-like "Notes" feature, allowing creators to communicate with each other much more freely than previously. This has produced an uptick in subscribers in the past week or so that I'm deeply grateful for, but it has also brought to my attention the reality that Substack the company may well be intent on monetizing hate in manner familiar from too many other social media companies. Hate drives engagement, and social media companies that turn a blind eye to hate are doing so because they profit from it. And it turns out they've been doing other sketchy stuff for a long time.

What I'm going to do about this I'm still thinking on. The outcome may be to stop writing entirely, or to move to a different platform with similar functionality, or to bring my own blog at tjradcliffe.com back to life, along with an e-mail feature so that all you lovely people can continue to get my deathless prose in your inboxes every Friday morning. The latter is the most likely, but it will be some months before I've settled the question. I do this for free and for fun, and Substack makes that easy. But it also makes spreading hate easy, and I can't be having with that.