Some puzzles from Gödel, Escher, Bach

Over the recent holiday break, I finally took the time to read Gödel, Escher, Bach by Douglas Hofstadter. I figured that it would be interesting to get a perspective on artificial intelligence from the pre-neural network era, and learn about the incompleteness theorem while I was at it. It’s a dense book, full of wit and wordplay, and I highly recommend it.

Are LLMs strange loops?

#

Hofstadter has expressed some degree of concern over the current state of AI in recent years. I can hardly fault him for being worried about how LLMs are quickly becoming arbiters of truth in our society, particularly when they are so fallible. Or that today’s young people are able to offload so much of their thinking to machines, so that they may miss out on developing certain fundamental skills themselves. Those are real problem, with no easy answers.

But I was struck by something he said in an interview I watched on YouTube. Towards the end of the conversation, he described himself as surprised that the core idea behind GEB (and subsequent work) - the idea of a strange loop - seemingly plays no role in modern AI systems. Strange loop is Hofstadter’s term for a self-interacting system, which appear throughout GEB (in the self-referential statement at the heart of Gödel’s theorem and the impossible waterfalls of Escher’s artwork, among many others).

Here’s what he says:

One thing that has completely surprised me is that these LLMs (and other systems like them) are all feedforward… The firing of the neurons is going only in one direction. And I would never have thought that deep thinking could have come out of a network that only goes in one direction… That doesn’t make sense to me, but that just shows that I’m naive.

Hofstadter is being too harsh on himself, if you ask me. I don’t think he’s totally right that strange loops aren’t present in a feedforward neural network (or that they won’t be more visible in next-generation AI systems).

It’s certainly true that feedforward neural networks like LLMs (by definition!) don’t have any loops in their architecture. That doesn’t mean more abstract loops aren’t present, though.

To illustrate this point, let’s describe the neurons in a human brain as a graph, with nodes (neurons) and edges (connections between neurons), and a “thought” as a pattern, in time, of neurons firing in a particular order. With three neurons, the graph of neurons might look something like this:

stateDiagram-v2
    direction LR
    A --> B
    B --> A
    B --> C
    C --> B
    C --> A
    A --> C

(Disclosure: I’ve never made mermaid diagrams before, so I used an AI system to help write the syntax for them.)

There certainly are loops here.

But the fact that the neurons fire sequentially means that we can remap the development of a “thought” to be entirely feedforward. We do this by “unrolling” the graph in time to produce a directed acyclic graph. Some physical neurons will be mapped to multiple logical neurons in the DAG, but that’s not such a big deal: they will simply share some properties in the unrolled graph, akin to the way that weights are shared between layers in an LLM.

In the case of the graph above, we might end up with a DAG sequence of firings like this:

graph LR
    subgraph A [Node A]
        A1(Event 1)
        A2(Event 5)
    end

    subgraph B [Node B]
        B1(Event 2)
        B2(Event 4)
    end

    subgraph C [Node C]
        C1(Event 3)
        C2(Event 6)
    end

    %% The causal flow
    A1 --> B1
    B1 --> C1
    C1 --> B2
    B2 --> A2
    A2 --> C2

Now let’s turn the argument around. What we typically view as a feedforward neural network (like an LLM) could in principle be “rolled back up” into a much more tangled, compressed version. That new version would, I think, certainly qualify as a strange loop: you’d have the output of neurons feeding back into themselves, changing their own state.

I’m not sure anyone has tried doing this, but perhaps it would be an interesting research angle?

Moreover, the very nature of autoregressive text prediction is itself strange loopy. The output of the neural network is used to aid in formulating the next state of the network - just, instead of the loops being hidden, they are written down in plain English. Modern, “reasoning” AI systems make this even more explicit, by forcing the model to write and read its own writing over and over until it generates a final answer.

All of that is to say that, in my view, it’s too soon to write off Hofstadter’s strange loops. More research is clearly needed.

A Kimian Self-Rep in Python

#

I did not take the time to solve all the problems presented in GEB (there are many), but a couple of them in Chapter XVI, “Self-Ref and Self-Rep” called out to me. The chapter is concerned with the analogy between a “quine” (a computer program that outputs its own source code) and the Central Dogma of biology (the DNA->RNA->Protein pathway). In both cases, we see examples of self-replication: the computer code copying itself, and DNA creating enzymes that in turn copy the DNA. Hofstadter shortens the phrase self-replication into just “self-reps”.

The first is described as a “Kimian Self-Rep”. Hofstadter writes:

Perhaps the sneakiest example of a self-rep is the following: instead of writing a legal expression in the compiler language, you type one of the compiler’s own error messages. When the compiler looks at your “program”, the fist thing it does is get confused, because your “program” is ungrammatical: hence the compiler prints out an error message. All you need to do is arrange that the one it prints out will be the one you typed in.

I had a hunch that this would be pretty easy to do. First, I chose Python for my “compiler language”, naturally, as it’s what I’m most comfortable in.

My hunch was quickly proven correct. I began with a simple:

hello world

And got out:

File "/path/to/geb-puzzles/main.py", line 1
    hello world
    ^^^^^
SyntaxError: invalid syntax. Did you mean 'del'?

So I substituted that in:

File "/path/to/geb-puzzles/main.py", line 1
    hello world
    ^^^^^
SyntaxError: invalid syntax. Did you mean 'del'?

The del/hello confusion is just an accident here, we won’t expect that to show up in the final version.

Running this code gives something very promising:

File "/path/to/geb-puzzles/main.py", line 1
  File "/path/to/geb-puzzles/main.py", line 1
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
SyntaxError: invalid syntax

So I tried using that as the code itself:

File "/path/to/geb-puzzles/main.py", line 1
  File "/path/to/geb-puzzles/main.py", line 1
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
SyntaxError: invalid syntax

And found that this indeed yields itself as output when run (I’ve obscured the paths here, but no matter).

What did I learn from this exercise? Very little. Let’s turn to the other problem presented in Chapter XVI.

Typogenetic self-replication

#

This one is a bit more interesting. Hofstadter describes a simplified version of the “Central Dogma” of biology (i.e. the DNA->RNA->Protein pathway). The main differences are:

• In Typogenetics, we use 2-letter codons instead of 3-letter ones.
• The functionality of each protein is determined directly by its amino acid sequence, not by its 3-dimensional shape.
• The “shape” of each Typogenetic protein is easily found by counting up the number of different amino acids. In real biology, determining the shape of a protein given its amino acid sequence remains one of the toughest problems to solve.
• Proteins can only act on DNA strands, and have a limited number of operations permitted (cut the strand, insert bases, create a copy of the strand, etc).

I won’t write the full Typogenetics specification; suffice it to say, at first blush, it seems to lend itself well to being written in code.

Hofstadter then poses the puzzle:

It would be most interesting to devise a self-replicating strand. This would mean something along the following lines. A single strand is written down. A ribosome acts on it, to produce any or all of the enzymes which are coded for in the strand. Then those enzymes are brought into contact with the original strand, and allowed to work on it. This yields a set of “daughter strands”. The daughter strands themselves pass through the ribosomes, to yield a second generation of enzymes, which act on the daughter strands; and the cycle goes on and on. This can go on for any number of stages; the hope is that eventually, among the strands which are present at some point, there will be found two copies of the original strand (one of the copies may be, in fact, the original strand).

I certainly have no idea how to intuit a solution, or work backwards, or really come up with any systematic way to solve this puzzle. But we have far more compute power than Hofstadter did in 1979 when he posed this puzzle, so I set off to brute-force a solution via a Monte Carlo simulation.

The idea is pretty simple: start with a single strand of bases, produce daughter generations of strands and enzymes, and simply keep track of all the strands that appear. Because the number of strands and enzymes grows exponentially over generations, I set a cutoff at three generations - if the program hadn’t found a solution by then, I simply started over with the next strand.

Initially, I set the code up to go through random strands, which is a reasonable way of approaching things if the strands are long. But I found that the number of self-replicating strands was just too low - I never was able to find one with a long starting strand. So I switched to a brute-force method, searching every possible strand of a given length.

One of my goals for doing this was to use zero AI assistance - just to get back in the groove of writing code and debugging. I’m sure an LLM could quickly spit out a passable script to run typogenetics code, but I wanted to keep my own skills sharp (even if this isn’t a particularly complicated problem). What does it say that I’m avoiding using AI to help solve a problem originally designed to illuminate AI concepts? I’m not sure, but probably nothing good.

I also attempted to avoid any spoilers throughout the whole process - so I didn’t know going into this whether a solution had previously been found. Surely, I figured, many others have tackled this problem over the years; I decided to only look up the solution once I had some code that worked.

In any case, the code is fairly straightforward, and since it’s mostly just string manipulations, hardly needs any dependencies at all. You can find all the code for this project (and the self-rep described above) here.

There were a couple learnings:

• What initially seemed so well-defined actually had some ambiguities in it. For example, say your initial strand codes for two enzymes. Which enzyme acts on the initial strand first? Just the first one that was created? Or do we assume there are multiple copies of the initial strand, and the enzymes each get one to act on?
• For that matter, what if you are in a situation with multiple strands and multiple enzymes? Does each enzyme get to act on each strand?

In my code, the way to resolve this ambiguity was to have the first enzyme act on all the strands present, then the second enzyme act on all the strands after that, and so on. This has the benefit of being deterministic, even if it doesn’t exactly mirror how things work in real biology, where everything is much more fluid.

Results

#

I confess that after not finding any solutions after searching many millions of starting strings, I did some Googling and (unsurprisingly) found some other folks had attempted similar things. One of the more helpful sources was here - although the page doesn’t render properly in my browser, it is readable enough to give some examples of self-replicating strands. The only problem was, most of the reported strands didn’t work in my code, because the initial binding site reported was not what I computed. Perhaps it was an oversight.

One sequence did work, however - CGTATCTCTG. And when searching all strands of length 10, it turned out to be the only one I found.

I also found three more very similar examples of length 12: CGTACATCTCTG, CGTACCTCTCTG, and CGTATCTCCCTG. But that took a while to run on my laptop, so I stopped there.

The repo, however, has an automated test set up, so the interested reader can submit a PR to add to this list, and GitHub will automatically decide whether the strand is a self-rep or not. Neat!