一位物理学家发现了社会中的隐藏相变——Cristopher Moore

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

You say, “Oh, well, if we could solve the halting problem, we could ask it about itself and then halt if it doesn’t.” And they’re like, “That’s it. That’s what Turing is famous for besides fighting the Nazis.” You know, this business of feeding programs to themselves was kind of astonishing.

Put it past them—just past, because you don’t want them to bounce off. You know, the real world has all this rich hierarchy of objects and parts of objects.

Tim Scarfe

I think what’s fascinating is that that real-world structure seems very hard to mathematize. We need more compute. I’m like, “Oh, that does not sound right in my ears.”

Are you a bird or a frog?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

I’m more of a frog. A lot of 20th-century mathematics was about soaring above.

Right?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Real-world data is not designed by an adversary to be as tricky as possible. I’m proud to say 8 of my puzzles are in that data set, so I’m waiting to see if AI can solve my puzzles. But I hope that we understand that, wow, this is actually really deep and amazing.

What’s fascinating about the LLM world is that quick pause before we kick off with Chris.

Human data is shaping the direction of frontier AI yet there's little visibility about how teams are actually using it. Our sponsor Prolific are putting together their first report on human data in AI and they need volunteers. It just takes a few minutes to fill out and you'll also get early access to their findings so you can see how you compare. They're just asking about things like evaluation methods and data sourcing approaches. So nothing personally identifiable. Check the link in the description. Much appreciated. And the episode is also brought to you by Cyber Fund, which is a thesis driven investment firm led by founders who've built companies from zero to billions. They've sponsored MLST for the next year. So I'm absolutely thrilled to have their support. It's amazing. They're looking for the few out there who are going to define the next decade of AI. And if that's you, they want to talk. So if you ship even faster than Yanick Kilchshire used to read machine learning papers before ChatgPT came out, of course. Um, visit cyber.com to learn more. Back to Chris.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

I’m Christopher Moore. You can call me Chris. I’m a professor at the Santa Fe Institute. I was originally trained in physics, and then I read Gödel, Escher, Bach and got excited by computer science. Then I got into network theory, and then I got into machine learning.

Chris, welcome to MLST. It’s amazing to have you here.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Thank you very much for having me.

You’ve spent decades of your career looking at impossibility theorems and, in a sense, why you’re biased toward looking at things that are not possible?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

I guess this is because, after I got my PhD in physics and moved into theoretical computer science, there was a lot of focus there on proving that things are hard, right? What I like about computer science is that you put on 1 hat and look for efficient algorithms for things, and then, if you fail to find a good algorithm, you can switch hats and try to prove that the problem is hard.

I haven’t done very much work in cryptography, just a little bit in post-quantum cryptography. There, of course, if a problem is hard, maybe you can use it to build a secure cryptosystem. I like that 2-sided nature of computer science and computational complexity theory.

You were saying yesterday in your talk that in the 20th century there were many birds, where birds as scientists are, you know, “Let’s have a helicopter view. Let’s look at things zoomed out all the way.” And there were also frogs who are sort of down in the weeds a little bit. Are you a bird or a frog?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

I’m more of a frog. So, yeah, this comes from Freeman Dyson. A lot of 20th-century mathematics was about soaring above, like you say, and finding grand analogies between things.

I really like concrete examples. I like things I can visualize, that I can hold in my hand. I have a lot of desk toys. I’m a very tactile thinker. It’s actually very hard for me to do much abstract thinking.

Every time I’m trying to understand a proof or something, I’m constantly touching down and measuring the steps of that proof against my favorite examples to understand why they work, why it’s true here, and why it might be true elsewhere.

I also like moving back and forth on the rigor spectrum. I’m originally a physicist, and I often do numerical experiments and simulations of various things. But I do like proving things when I can.

It’s very nice: if I can prove it, I publish in a math or computer science journal; if I can’t prove it, I publish in a physics journal, and I get to publish either way. So it’s a good career strategy.

Very cool. Now, we’re in the regime of transformers, which are these huge, overparameterized models that predict the next token in a sequence of tokens. It’s just so good to have you in the room with me because it’s interesting to think about how they’re limited in terms of learning and optimization, but also complexity and computability, perhaps, in terms of the classes of automata. From your expert position, how do you think about the limits of these types of models?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Most of the work that I’m familiar with is where you can show that something is hard. But as some of your viewers know, traditionally in computer science, when we say a problem is hard, we mean there exist hard examples, if those are cleverly designed by an adversary to be as hard as possible.

In some interdisciplinary work at the boundary between statistical physics, machine learning, and high-dimensional statistics—different people have different names for it—you can prove that things are hard in the context of really random examples. So, synthetic data which is drawn from some simple probabilistic model.

Of course, real-world data is neither of these, right? Real-world data is not designed by an adversary to be as tricky as possible. It’s very far from random. It has all kinds of structure that human intelligence, animal intelligence, and artificial intelligence can exploit.

I think that’s why a lot of people in machine learning often feel like, well, proving that something is hard in theory isn’t really—I don’t care. I’m just going to go solve it anyway. That’s somehow because the real world presents us with examples of these problems where there is so much rich structure to sink your teeth into, whether that’s the structure in text, the structure in images, and so on.

I think what’s fascinating about the LLM-transformer world is that, a few years from now, we’re going to look back and say, “Yeah, that architecture works. A lot of architectures work.” Almost, in some sense, any sufficiently rich architecture will work.

What matters is that the world is structured, and any architecture which is capable of capturing some of that structure is going to do well at prediction. Whether it does well at other things, and the whole debate about whether they understand and so on, I have thoughts, but they’re probably thoughts that other people have said just as well as I would or better.

I do think, though, that some of this work on phase transitions is quite interesting. This is where I’ve spent the past decade or 2, and this is where some ideas from spin glass theory and the theory of disordered materials from physics have met with machine learning.

The idea here is that, just as a magnet loses its ability to hold a magnetic field if you heat it above a certain critical temperature, below that temperature the atoms will automatically align and you’ll get a nice, strong magnetic field. Above that, it just becomes very noisy, and there are similar phase transitions—in fact, using a lot of the same ideas from physics—in machine learning.

If you have some ground truth and then some noise process which produces some noisy data, then, depending on how much noise you have, that’s a little bit like the temperature. If there’s too much noise, then there’s literally nothing you can do to discover the ground truth, the underlying pattern. It’s just no longer present in the data; it’s been washed out.

If there’s very little noise, or, if you like, if the signal-to-noise ratio is very high, then it’s very easy, and a lot of our favorite algorithms work very quickly: spectral algorithms, PCA, what have you; message-passing algorithms like belief propagation, and so on.

There can also be these interesting middle ranges where you can find the ground truth if you do an exhaustive search, but we actually believe that there is no efficient algorithm that will succeed in that regime.

You’re wandering around in this high-dimensional landscape of possible fits to the data, and the accurate ones are kind of hidden behind what in physics we call an energy barrier. All of our favorite algorithms, whether they’re Monte Carlo, gradient descent, or message passing, get stuck for an exponential amount of time in a kind of amorphous mush of inaccurate fits to the data. Only if you had the luxury of exhaustive search would you find the accurate fit.

I love this work. I love its interdisciplinary nature. It connects with replica theory and the stuff that Giorgio Parisi recently got the Nobel Prize for. I work with a number of his students and grandstudents, so it’s a wonderful interdisciplinary community.

That said, though, all of this is theory about random problems. Again, real-world problems have structure that can help guide us. I think what’s fascinating is that that real-world structure seems very hard to mathematize. How do we talk about that structure? It’s much more than just correlations. The real world has all this rich hierarchy of objects and parts of objects.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Ultimately, I feel like what LLMs are going to do, and what transformers are going to do, is help us mathematize that structure. I think that ultimately we're going to learn a lot about the world from the fact that they succeed, in addition to learning things about them.

Yes, it feels, though, that we do something slightly more sophisticated. I completely agree with what you said about this: reification, simplification, abstraction. There's so much more information that we're leaving out in these processes. But we can design the Linux operating system, and it feels that even though these transformers can learn structure, the types of algorithms that they can perform are limited in very, very problematic ways.

I follow these debates about how good these things are at coding. I follow Jonathan Blow on Twitter. I enjoy his work on game design—I love his work on game design. He's very opinionated. I don't really have an informed opinion about this because the coding that I do tends to be relatively small-scale. I don't build large modular things with many interacting parts. I build some code to run a physical system on my laptop.

From the outside, I see that there's this debate about whether it's really just copying GitHub and how much it really understands code the way a human coder does. I guess I also know that people are talking about—or are doing—taking an LLM and giving it a module that it can use the way we use specialized modules.

When I have a certain kind of mathematics problem, I fire up Mathematica, right? If I want to know how some function behaves, I graph it and look at it. I think once LLMs are given these various playgrounds and given the ability to fire them up to literally doodle and look at it in a 2D way, the way we can with our eyes, as opposed to treating everything as 1D strings of text, I expect that we'll see much more multimodal abilities. I know that this is already happening.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

It's just so interesting that, in the self-attention layer, it's this first-order Janossy pooling, where you just kind of take all of the possible pairs of the tokens, stack it N times, and stick an MLP on the end. The sanity test there just seems to me: how could it possibly learn a deeply factorized, structured representation of problems?

Yeah, I agree with you. And yet it seems to work surprisingly well at a lot of things, and we keep moving the goalposts—and we should move the goalposts, right? The interesting area of research is the velocity of the goalposts. One thing that I do on the side is design puzzles.

There's this fantastic YouTube channel called Cracking the Cryptic, where these 2 puzzle champions from England, Mark and Simon, do pencil puzzles. Many of them are online nowadays, and many of these are modern variants of Sudoku.

People take traditional Sudoku and invent all these cool new rules. There are thermometers, which are paths along which the digits have to increase; there might be a box within which you're told what the total of the digits in that box is; or there are additional constraints, like cells a knight's move apart have to be different.

So there's an AI company, I think Sakana AI.

Oh yes, I know them. Yeah.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Yeah. So they worked with these guys to compile a lot of these. The goal is: can you get an AI to read these rules in English and then solve some of these Sudokus? Last time I looked, the behavior so far was pitiful. They had done a couple of 4×4 Sudokus, maybe a 6×6. I can't remember.

Of course, these are puzzles designed by humans to have interesting insights about them and cool global constraints that cause various kinds of logic, which is just not present in traditional Sudoku. So far, the ability of AI to absorb these rules and then use them to do some kind of intelligent search hasn't happened yet. Now, I'm sure that it will improve.

I think one of the reasons why LLMs do poorly on these things, again, is this bias toward 1D text. At least a year or 2 ago, when I tried ChatGPT on very simple tasks involving 2D arrays, like the classic N-queens problem and things like that, it really couldn't do it.

Whereas we have this sensorium, right? We're used to being able to look at a 2D image. Our eyes—our pupils—can scan around very easily. One of the reasons why we like Sudoku is that it's very easy to scan a row, scan a column, and scan a little 3×3 box. So it fits with how we can address that data structure, if you will. And that lets us do, I think, much more directed kinds of search.

The last thing you would want to do is translate it onto a big Boolean satisfiability problem and then use your favorite Boolean satisfiability solver. You could do that, but that's certainly not what Mark and Simon do on their YouTube channel. They sort of sit there and think about the rules and derive from them some heuristic or some high-level logical constraint, and then use that.

For me, that's a really interesting benchmark, and I'll be very excited and a little annoyed if AI starts solving those problems. I'm proud to say 8 of my puzzles are in that data set, and so I'm waiting to see if AI can solve my puzzles.

Yes. I suppose the paradox is that even though they're kind of compute-restricted, you made a wonderful observation yesterday: we have these hard problems, and the art is transforming them into simpler problems with heuristics. So, in a sense, the intelligence is about doing more with less. It's about making hard problems simple.

If only it were possible just to make that transformation, then the language models would be able to do it. But what kind of intelligent process do you need? What goes through your mind when you come up with these creative flashes of insight?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Yeah. One thing I like about the puzzle design community—there are about 10,000 people on this Discord built up around this channel—is that they talk a lot, not typically in a formal mathematical way, about the art and science of designing insights and then finding insights. You act not as an adversary, but as a challenging yet ultimately compassionate teacher who's trying to create fun insights for the solver to have.

There's also a lot of talk about the sensation you want to have as a puzzle solver, whether it's a wooden puzzle, fitting little tiles into some tray, or a Sudoku. You want to have, at first, this vertiginous sense when you look at it: “Oh my God, I'm in this exponentially large search space.” A priori, the last thing I want to have to do is exhaust this search. It's boring. Humans are bad at it. That's the last thing anyone wants.

You want to feel that you're looking over this vast, forbidding landscape, and then you see an insight and start realizing things. I think one thing that's really fascinating is that humans are quite good at designing on the fly different kinds of partial knowledge or partial solutions to a problem.

If you go back to the days of good old-fashioned AI, where people were doing different branching rules for backtracking search and Davis–Putnam search, there were certainly a lot of clever ideas about this: if you have some big Boolean problem, which variable should you try setting first?

People came up with sensible heuristics. If a variable occurs in many different constraints, we should set it first, because that way, whichever way we set it, we'll satisfy a bunch of constraints, make a bunch of other constraints more upset, and narrow the search space. That's great.

But humans do something richer than that. Imagine you're solving one of these wooden puzzles where you have tiles with different shapes. Pentominoes are my favorite. You're trying to fit them together. Humans will very fluidly switch between asking which piece can fit here and where this piece can go—2 different kinds of variables.

In these modern Sudoku variants, powered partly by these really awesome apps, there are traditionally different kinds of pencil marks that Sudoku fans have invented. One of them means the thing here is either a 2 or a 7, which is one kind of partial knowledge. Another is that the 3 in this box is either here, there, or there, which is a different kind of partial knowledge.

Now people are inventing new kinds of partial knowledge, like: these 2 cells—I don't know what they are, but they have to be the same, so I'll color them both blue and figure out what their numerical value is later. Or these 3 cells—I don't know what they are, but they all have to be different.

To me, this is a really interesting frontier for AI, where you take the problem and invent on the fly what kind of variable you should use to address the problem, right? That's very different from being told, “Here are the variables; here are the constraints.” There's already a lot of interesting questions there.

But here it's more like: fit these things in, formalize the problem, mathematize the problem, and then make some progress. Maybe you even fluidly jump from one mathematization to another during the solving process. To me, this is a lot like science.

When you're doing mathematical modeling, in many cases, the challenge—if you're working with a social scientist or a biologist or whatever—is that 90% of the work is the mathematization: figuring out what kind of mathematical structure could fit here.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

And often, once you do that, it's relatively easy to simulate the model, solve the model, or prove something about it, whatever kind of work you're trying to do. That formalization process is something that I think is a really interesting kind of task for an AI to do.

Yes. Yes. There's always this lingering problem of residuals: what happens when we leave things out? But this process of epistemic foraging fascinates me, right?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Very good phrase.

It's wonderful. I got it from my friend Cole Friston.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Oh, okay. The free-energy guy.

Yeah, he's a great guy. And so there's also this phylogenetic locking-in, which I think is good as a form of constraint, but it's also interesting from a flexibility point of view. We're trying to explore this space, right, to forge a path.

And the other thing is, I'm not sure whether you would call yourself a Platonist or not, but there's this interesting juxtaposition: are we converging on the real thing, or are we constructing our own reality? And where does culture and all of these different things come into it?

Because we are very much just laying down what you called partial knowledge. We're laying down the stepping stones, and we're trying to move forwards.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Right? I mean, I guess when it's a puzzle, there is a ground truth. You've been promised there's a ground truth. In the Sudoku world, you've been promised that it's a unique solution, and when you've found it, you know you've found it.

In real-world problems, as you say, it's very hard to know when we've found the real thing and whether we've failed to see something else.

And I guess if what these things know is what's on the internet, well, that is a world; it is not the same as the physical world. And so, on grounding and meaning, my friend Henry Ferrell, who is a historian, tried out one of these things.

He wrote an essay and, in his essay, he made a subtle point that was really a little bit sideways to the various points that various people had made. Then he asked—I forget which system—to summarize his essay, and it sort of blandified it. It kind of reduced it to the lowest common denominator.

It did kind of what people at a cocktail party might do if they're thinking pretty informally, maybe trying to impress each other a little bit. It basically saw what he was writing about, and then it produced a summary based on the most common things that people say about that.

It totally missed the unique thing he was trying to say that was different from the common arguments on either side. This is interesting, and I think for him this was an indication, again, that these systems are not grounded in meaning. They don't really catch the, “Oh, that's an interesting point.”

Now, you could say, given a more sophisticated use of the statistics of text, even if that's all they have—and then you can argue about whether compressing them forces them to build world models, et cetera, et cetera—maybe a better summarizer would catch the cool thing, right?

Just as maybe a better music or book recommendation system would challenge you the way a friend challenges you in that wonderful, directed way that friends do. “I know you don't think science fiction is good literature, but you have to check out Gene Wolfe because the prose is amazing and the characters are amazing, and I think it will meet your literary needs. I want to bring you over to science fiction.”

You know, that sort of thing that our friends do for us that I don't think any recommendation system really does for us. It's like, “You like this music? Here's some more music like that. Oh, you kind of like that? Here's some more like that.”

It's like, well, give me something different. Challenge me. And I think one source of those challenges is meaning—the real world. Look at this cool thing, or this essay is actually about real things; think about those real things. Don't just look at the text.

Of course, these are again things that other people have said better.

Right.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Yeah.

Tim Scarfe

But this seems like the debate. On the other hand, I do think, like I said, that once these things—as they're already doing—can not just write code but run it and see whether it works, and then debug the code if it doesn't work, or, if it's a question about a 3-dimensional object, fire up a 3-dimensional workspace or a 7-dimensional workspace where they can doodle and then kind of perceive the way we perceive, right?

I am a bit of a Platonist because if you and I close our eyes and we each think of a cube, admittedly, we live in a society with a lot of right angles, and we've seen wireframes rotating on screen, so we've had a lot of practice with this.

But both of us can see in our minds a cube, and we can just, by counting, by perception, see that it has 8 corners and see that it has 12 edges. If one of us thought it had 14 edges, the other would say, “No, it's 12,” and the other one would look again at the cube in their mind and say, “Oh, yeah, you're right, it's 12.”

So we're really perceiving something there. The fact that we can have that shared perception gives me, and a lot of other mathematicians, a sense that there is some reality to these things. These are not just subjective objects.

And so I do think that once these systems can switch on the fly what kind of workspaces they have and what kind of reasoning they do, then I think they'll be much closer to what we do.

Tim Scarfe

I mean, even if you ask them to do proofs, of course there are proof-finding systems that are very formalized. If you ask an LLM to construct a proof, it will often construct some BS. It will be stylistically similar to proofs it's read, but so far it doesn't seem to be able to do that reflection process and really check the steps in the proof and see if it works.

But of course, that is also a very specific thing that humans don't do very often, right? Specific humans in specific cultures do this and have tools for doing this. We might whip out a sheet of paper and start writing things with formal symbols and formal logic to see if our informal proof, written in English or whatever, actually holds.

When we do that, we're firing up some special mental models and using some external tools—paper, pencil, blackboards, computers—to help us with them, because actually formal logic is not something that we're built to do.

So I expect these systems, once they can really play with all of these modules, including ones that we don't have, like visualizing things in 7 dimensions, will be able to do a lot.

And when we give them access to 3D printers and Fab Labs so that they can start building things and seeing whether they work—I'm not sure if we should do this—well, maybe we should solve the alignment problem first.

Tim Scarfe

Yes. What you were saying about the prose, the kind of GPT-generated text, was very interesting to me. They model this statistical distribution, and they're greedily sampled, so they just give you tokens from the bulk.

One school of thought is, well, we'll make them more creative. We'll just turn up the temperature and sample tokens from the tail. And you really get garbage there because you're a little bit out of distribution.

One thing that would lead me to think they were learning these factored representations of the world is when, if you sampled the tail, it actually gave you something creative and useful.

But I did want to say that I'm not entirely sure whether it is about learning meaningful, structured representations of things that are grounded in the world. I'm a creative professional, so I've learned about video editing, and I hire scriptwriters and so on, and I've noticed that there might be something else at play.

You were saying you can add noise to problems and that actually makes them more tractable. In audio and video, if you add noise, then you're actually training on textures and high-frequency patterns; you're training human perception to look away. So you could blur, you could add a texture, and so on.

And it's the same in writing, that there are so many creative motifs using slightly different language that deliberately takes it away from the head of the distribution, but such that it respects the epistemic fogginess [?]. It needs to be meaningful but still creative, and it doesn't necessarily have to have any grand meaning or be grounded in the world.

So I guess the question is: is it just aesthetic creativity, or does it really need to respect the rules?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

This reminds me of Martin Amos. He has this book called The War Against Cliché, and he makes some of the same points in a memoir about his friendship with Christopher Hitchens.

His feeling as a prose writer is that any string of 3 words that other people have used should be avoided, basically. I mean, I'm paraphrasing him, but if you say anything that is a visible reference to something else, you better be doing it on purpose.

You shouldn't just be doing it because you've heard it before and because it has a high probability in the distribution.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

So I think his goal as a prose writer was to constantly produce new juxtapositions in order to intrigue the reader and to access a space in the creative space—the writing space—which hadn't been accessed before.

And I'm sure you know this as a creative person as well: just as a mathematician might look at a proof, hold it to the fire, and say, “Okay, does this proof really work?” We have lots of processes, both individual and collective, to do that. Artists make something and then hold it to the fire: is this really good? Right? Of course, the pain of artists and mathematicians is that we crumple up a lot of pieces of paper and throw them in the trash. It can be emotionally exhausting, but we have this very high standard for our own work.

We don't just produce things. We then reflect on them and show them to our friends, perhaps show them to our critics, and then try to modify them, improve them, or abandon them. This loop, I guess, is a little bit like this: if you're a physicist, you do an experiment and see how the experiment works out. If you're a mathematician, you do the “experiment,” but in a formal space of whether it's logically sound. If you're an artist, you do the experiment of looking at it and judging it in the ways we do.

One thing I've learned from artists is that art is not this kind of floppy thing, right? It is a very exacting thing. My PhD adviser, Philip Holmes, wrote poetry, and he said, “This is much harder than doing math.” I completely agree.

On that note, when I look at a video someone else has edited—because I'm very experienced now—it's very similar to mathematics or even the ARC Challenge or something like that. Intelligence is the process of decomposing something into the constituent parts that made it. As a video editor, as any creative professional, you're trying to create this progressive disclosure of complexity.

You're delivering a sequence of artifacts to the reader or the consumer which just increase in complexity, and you have to put it just past their prediction or cognitive horizon.

Tim Scarfe

Just past.

Just past, so you know.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

You don't want them to bounce off, and you don't want them to be bored. There's a sweet spot.

Exactly. Even with audio production, you have these sound effects, and they can hear the transitions. So you add texturing, you add noise. But I can still hear it, so I'm going to add a little bit more noise. At some point, the whole thing just becomes more than the sum of its parts. The process of art is just building this up layer by layer and having this almost synchrony with the audience, knowing what their prediction horizon is.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Right. In order to do that, you're doing a great deal of mental modeling of the viewer. You're constantly putting yourself in their shoes.

If I can jump back to puzzles for a little bit, when you design a puzzle, you're also constantly putting yourself in the shoes of the solver: would they get this? Are they going to see this? Is it going to be visible but just hard enough to see that it will be a wonderful aha moment?

I think one interesting thing philosophically is that there are both subjective and objective aspects to this. Subjectively, of course, you're designing things for humans, and you, as an editor and a creator, are designing things for humans with a certain level of literacy and familiarity with, for instance, the things that are talked about on your channel. Similarly, if you're designing a puzzle, you're designing it for a human who has a certain tolerance for search, but not much more.

It's like if you're in a chess-playing society, you kind of know about the knight's move, right? There are certain things that you're familiar with. There's a variant rule in Sudoku which, for some reason, is called disjoint groups, that for me is very headache-inducing: if there's a 7 in the top middle of this 3×3 box, there cannot be a 7 in the top middle of any of the other 3×3 boxes.

This does not fit with my sensorium. On a subjective level, I know that mathematically and logically it's a very nice extension of rows, columns, and boxes. It's sort of like a 3- or 4-dimensional extension, treating the thing more like a hypercube. But I hate it because I have to look over here, then look over there, and then painstakingly look over there. I can't scan it in the nice way I can scan rows, columns, and boxes. So that's an area where, subjectively, I find puzzles involving that constraint both harder and less fun.

It's also the case that if I were a much more cognitively powerful creature, then maybe I would experience just as much pleasure out of 100×100 Sudoku as I do out of 9×9s. Right? It's true that—I'm just 2 pounds of meat with a 1-hertz processor—I can only handle the 9×9 things. Is it 2 pounds? I'm not—I haven't weighed my brain.

On the other hand, I also can't help but feel that there are almost mathematically objective aspects to aha moments. Maybe there are big aha moments and little aha moments, but we can all agree—we can all sort of recognize them as insights. When you're designing a video, you can agree that, okay, at this point, this concept is being introduced. You have a cognitive map of what concepts are being gained at each step and then used to build the next step. Maybe for some viewers, some steps would be very challenging; others would be kind of obvious, but they would all understand that that's a step.

So, in the puzzle world, there's a lot of recognition that a good puzzle and a hard puzzle—these are orthogonal axes. There are simple but beautiful puzzles. There are hard and beautiful puzzles. There's also simple, boring puzzles and hard, boring puzzles. These are really very different things.

Theoretical computer science supposedly helps us figure out what problems are easy and what problems are hard, and what qualitatively makes them easier or harder. What is it about their structure that makes them easy or hard? Why is this problem a smooth landscape that a greedy algorithm can just find the optimum, and this problem a very rugged landscape? In physics, we would say a very glassy landscape, where there are many local optima, hard to navigate, blah blah blah. I've tried a little bit to formalize what it is about these aha moments, and I haven't succeeded.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

It's a little bit like public-key cryptography, where you have a function: everyone can run the function forward, but the challenge is inverting the function. If you're given the private key, then inverting the function becomes very easy.

But this is different. You have to find the key yourself. You have to find the insight yourself. Or there's this notion in computational complexity called computation with advice, where again you're given a big string of advice. But again, this is about finding the advice.

I feel like it's more like the meta-problem of designing an algorithm. So imagine that I show you an example of a potentially hard problem, an NP-hard problem. But I promise you, actually, this example is easy. I promise you this example belongs to a large subclass of problems for which there is an efficient algorithm. Now you have to go find the algorithm.

Yeah.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

That seems a little closer to this puzzle design, and maybe also a little closer to being an intelligent entity dealing with a very structured world. You're not having to parse arbitrary images; you're parsing natural images shaped by the processes of natural selection and by the structure of the built environment, which is made by systems not entirely unlike you—systems that are building an environment they can understand and navigate. Now your task is to understand, navigate, predict, and segment this data.

What's really fascinating is that it's not just humans solving puzzles that were invented by humans. Of course, that's ultimately a kind of communication: you're being communicated to by something with cognitive capacities and cognitive tastes—enjoyments similar to yours—and then you can grab onto that. What's amazing is that even the nonliving world and even the natural, nonhuman world has all sorts of stuff that we can grab onto.

You can share it with other folks because I'm interested in creativity and whether it's socially constructed or whether it's grounded. As we were saying, the other artists or the other mathematicians can decompose the structure, see whether it fits, and identify what the creative steps are. So there's a kind of intrinsic value to it, which is fascinating.

On the other point about actually forging paths in this space, I wonder whether you would agree it's related to undecidability and even Wolfram's computational irreducibility. I mean, just imagine Wolfram: you have a cellular automaton. What's one of his famous ones? Rule 134.

Tim Scarfe

110, 110. Sorry, my bad. But you know—or I know you've studied the three-body problem, right? So you do this computation step by step, and there are no analytical shortcuts, right? You just have to do this wide-ranging, divergent process, and then you find something, and that's amazing.

You've hit this stepping stone, but there was no shortcut to get there.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Right? Or like a chaotic dynamical system where there's no closed-form solution: if you want to know the state it will be in at some future time, you can't just plug t into some formula. You have to numerically integrate it, and you have to do the work. You can't skip over its intervening history.

Cellular automata are a great playground for this. For the geeks, Rule 150 is kind of linear—it's linear mod 2 or something—so if I give you the initial state and you want to know the state at some future time, you can almost just plug it into a formula. You can create that future state with much less computation than it would take you to actually simulate it.

And then there are others where we strongly believe that you have to go step by step.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

The irreducibility you mentioned, which Wolfram likes, is one of the fascinating things about this. Our only techniques for proving that prediction is hard—that you have to do the simulation—are to build a computer out of the thing.

What happened with Rule 110 was that Wolfram observed all these cool particles and thought, “Gee, these particles are doing all these cool collisions, almost like chemistry, or almost like reading and writing symbols on a Turing machine's tape.” Then Matthew Cook came along and, with Wolfram, completed this proof and proved Wolfram's conjecture. Then my friend Damian Woods came along and did it more efficiently, and so on.

This is a lot like NP-completeness, right? We prove that problems are hard because they have some kind of universality to encode or express other problems. Therefore, if they were easy, these other problems would be easy, too.

A funny thing, though, is that there are a lot of systems where we don't know how to build a computer in them, but they still look really irreducible. They're still doing all kinds of stuff that looks really nonlinear, and it really doesn't look like you could jump forward in time, but the stuff is so uncontrolled that we don't see how to build a computer out of it. So we can't prove that we can't skip over the simulation.

Imagine that you were walking around in a world—imagine that you were thinking about computational complexity several thousand years ago, which I guess you could have done. Maybe, in some philosophical sense, some people did. But suppose you don't yet have wires or pipes, or in general things that can transmit some information—a bit or whatever—very cleanly from here to there. And you didn't have little gates that take these clean wires, produce something else, and send it out along another wire.

Suppose you just had this kind of—what a friend of mine calls—lava, just this chaotic stuff going all over the place. Or imagine looking at the flow of plasma in the Sun, right? In these amazing videos from solar telescopes, you see things briefly forming and then breaking apart, and it's very chaotic. It's sort of like the planet Solaris or something, right?

What you don't see is stuff out of which you could say, “Oh, that is a nice controlled building block. I could use that to store a bit that I could then write to later or read from later, or combine it with something else.” Some cellular automata have this kind of very chaotic, very nonlinear-looking structure, but what they don't have, that we know of, are these nice particles that we can use to transmit and modify information and simulate a Turing machine or whatever.

I wonder if a lot of natural systems are in this weird middle ground, right? You can build hydrodynamic computers if you have pipes and valves. Before transistors came along, people were trying to build microfluidic computers, right? There's some wonderful alternate history in which we don't have transistors and what we have is microfluidics everywhere. That would be fun to think about.

It's a little bit like The Difference Engine. Bruce Sterling and William Gibson have a novel about that, where Babbage succeeds in building these mechanical computers and that's the technology we have. But can you build a computer just out of water, just the flows of water? Maybe, just out of the Navier–Stokes equations, using little fluxons to travel from here to there. Maybe. Some people say yes, but it seems harder because things are not channeled.

Yes. So there's a difference between the complexity of a system and whether we can get it to do the computations we want it to do, right? It might be doing very complicated computations internally that are indigenous to its own dynamics. That doesn't mean that we could say, “Oh, good, now I can use it to build a computer.”

Formally, we know that there are problems which are undecidable but which are not Turing-complete, in the sense that if I gave you a box that solves this problem—an oracle for this problem—you could then solve the halting problem. So they're undecidable, but not because the halting problem can be reduced to them.

Similarly, we know that if P and NP are different, which we believe—academically, almost everyone I know believes that, although not everyone—then there are problems in the middle ground which are outside P. They cannot be solved in polynomial time. They cannot be solved efficiently, and yet they're not NP-complete. They don't have the ability to capture other things. The annoying thing is that the only way we can prove that a problem is hard is by showing that it is complete—essentially, by building a computer out of it.

My co-host, Dr. Doug, is a big fan of Turing machines, basically, and he thinks that current AI is limited because transformers are not Turing-complete. He thinks the reason for that is that they're finite-state automata and they're trained in such a way that means you can't really have a recursive thing when you're doing stochastic gradient descent, because it would just go on forever.

But his fundamental hypothesis is that he kind of thinks of GIs as being Turing machines, and you can have different strengths of agency. So a strong agent is a Turing machine: a thing which does some computation, has an environment signal, and takes an action. But if the block in the middle is a Turing machine, then it's capable of strong agency. So I guess my question—

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

GI—general intelligences? Generative? What's the G?

Oh, general. Yeah. But I mean, you're the perfect person to ask about this, out of all the people we've ever interviewed. Do you think he's right to think about Turing-completeness as a way to demarcate different forms of intelligence? And do you agree with his theory that if it were possible for us to train a Turing machine, rather than a finite-state automaton—imagine we could empirically train it—would that lead to amazing things?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Well, yeah. Of course, in his 1951 paper, Turing says that artificial intelligences—although I don't remember him using that phrase; I'm not even sure if he used the phrase “artificial minds” or something—would be trained, or almost raised, like children rather than programmed.

Turing machines as an architecture, I think, are rather brittle. I think the partly analog nature of neural networks and LLMs—their ability to work in a continuous way with high-dimensional vector spaces and embeddings—is important to their trainability, even if it's not ultimately important to their cognitive abilities. I guess an easy riposte to your question is that I am also a finite-state machine.

I have a very large number of states. I will not, within my lifetime, have the ability to explore more than a few of them. But I'm composed of a finite number of neurons, a finite number of elementary particles, so I have a very large but finite number of states.

Now I think the difference is that, because I am also a tool-using and tool-making entity, if I realize that there's a problem which is difficult for me to do in my head—which is most problems of any size at all—I can then build things, whether that's a clay tablet, an abacus, or a computer, that extends my workspace, extends, if you will, the tape of my Turing machine. And that gives me, in principle, recursion.

Then we can get into, “Oh, well, is the universe actually finite?” That's not very interesting to me because we can reach fairly far into the kind of asymptopia of recursion.

Famously, people joke about German speakers having a stack depth of 3 or 4 and English speakers having a stack depth of 1 or 2. I'm not sure that I contain a stack. Unlike what Noam Chomsky supposedly said, if I had a stack in me, then it would be a lot easier for me to repeat a string of words backwards.

Yes.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

And that's very hard. If you give me a short string of words, it'll be a lot easier for me to repeat it in the original order than backwards. So I don't think I'm very good at pushing and popping. I don't seem to have that kind of data structure in my mind. But if I need it, I can build it with pencil and paper or a stack of plates on a table. So I think it's that extensibility—

Tim Scarfe

Yes. Yes.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

—which gives us access to recursion and universality.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

And that's partly why I guess I'm excited by the idea of AIs that can say, “Gee, this problem has a recursive nature. I cannot do this just in my own context window or my own embedding. I need a data structure which lets me push and pop easily.” And I know that before transformers came along, people were already working on these hybrid structures where you have a deep network.

Rather than asking it to create a stack in its own state space, or training a stack as part of it—which would be very challenging—give it a stack and let it take actions on that stack as a data structure, and let it learn how to use it and play with it.

Tim Scarfe

Could I just refine this? Because I don't want to misrepresent Keith. Everything you've said is absolutely true, and when we have this discussion, there are many folks who say exactly as you have: the brain is an FSA, and we can expand our memory by writing things down on a hard drive. I can get another whiteboard, I can get another whiteboard, and so on.

But his argument is slightly more nuanced. He's saying that, yes, our brain is a finite-state automaton, but if you look at all of the algorithms that are inside that class, there is a subset of algorithms which are those that can control a Turing machine and expand memory and so on. And those algorithms are not traversable with stochastic gradient descent. So he's roughly saying that maybe the Chomsky argument—maybe we've got the merge operation or something—somehow our brains have learned the special class of FSA algorithms that can expand our memory.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

I see. That's an interesting claim. I mean, I think we're at this workshop this week where there was a whole discussion yesterday about what do we actually need language for, and what do we actually need symbolic thinking for, because that's where recursion seems to start, right?

And there are plenty of intelligent entities out there, like our close relatives, the great apes, and possibly our ancestors, who were already making stone tools and teaching each other to make stone tools using gestures. They didn't need the full-on modular structure of language that we have. And you can do a lot to navigate the world without, if you will, Turing completeness—assuming that what we mean by Turing completeness is the ability to do symbolic recursion and so on.

And the funny thing is, then we're training LLMs as language-first things. They're not tactile-first things or visual-first things or find-food-first things the way we were. They're language-first things. And because language is the medium in which we do symbolic thinking and recursion, then we're like, “Oh, good. They should be able to leap to all this formal stuff in mathematics.”

But they're not formal systems, right? They're token-producing systems, the same way most human speech is a token-producing system, right? Formal reasoning is something that we do—a kind of thin veneer that we apply in specific settings on top of token-producing, right?

When we're chatting with each other, or even talking about topics that we've had conversations about before, we're acting very much like an LLM. We're cheerfully in a distribution we're pretty familiar with. We're cheerfully emitting tokens. We're doing it; we don't really need to do that much self-reflection about it.

It's when we hit some edge that we're forced to do the self-reflection we were talking about before: “Okay, is what I'm about to say—does it actually make sense?” And that's something most of us don't do most of the time, right?

And so, yeah, I mean, I feel like the Turing machine itself—for instance, when I teach theoretical computer science, I don't do it in a Turing-machine-centric way, right? And I think if you look at some more recent textbooks, they don't do what the older textbooks did, where the first thing you do is, “Here is a Turing machine.”

The Turing machine is partly of historical interest now. I mean, it's a cool, minimal thing that's universal, but there are many other very small things that are universal, whether those are families of Boolean circuits of increasing size, with, yes, admittedly, some kind of uniformity to them, or whether they're counter machines or finite-state automata with 2 stacks.

People like Minsky and others had a lot of fun in the ’60s and ’70s finding these smallest possible machines that can do that, or cellular automata, or whatever. So, for me, the Turing machine isn't central.

Actually, it was the first thing like it which had this ability to simulate—had this universal ability to simulate other machines of its own kind. It had this paradoxical ability to simulate itself, and therefore the halting problem and so on. But I don't view that architecture as central.

It's very von Neumann, right? You have a CPU, you have a memory. It's very magnetic-tape-like. You roll the tape over to this part. So, yeah, I feel, I guess for me mathematically, when I think about computational universality, I think about things like our favorite programming languages and their relationship with the theory of partial recursive functions, right?

As I'm sure a lot of your viewers know, these basic notions of recursion that were invented before Turing came along—primitive recursion is basically a for loop. There's this other operator called minimization—don't worry about it—which is basically a while loop. And function composition is basically, well, function composition.

These tools can generate all of what are called the partial recursive functions, which are more familiarly now called the computable things, right? These are the same things a Turing machine can do. And then Church has his wonderful lambda calculus, and that shows up in Haskell and Lisp and so on.

So, to me, the wonderful thing is that these rather different architectures—the Turing machine and the grand unification which occurred in, like, 1936—what is marvelous is that they can all do the same thing.

Tim Scarfe

Yes, maybe I should clarify that Keith wasn't talking about a physical Turing machine. He was talking about the strength of the computation. I think, in a practical sense, he was saying exactly as you were just saying: being able to do arbitrary loops and recursion in an algorithm, right?

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Yeah. So ultimately, if you can take building blocks and use them to make more complicated things, and then use those things as building blocks, and then wire them to each other and wire them to themselves, you can do everything we're talking about computationally. And that is what we do as technological beings. We build these incredible scaffolded technologies, which we haven't seen the end of yet.

And if you can do that in a virtual space, then you are an unbounded technological being in the world of mathematics. You can build these arbitrary computable functions. You can compute anything which any other reasonable architecture can compute.

And now, right, so yes, Turing machines can do this, although they're very close to the hardware, as it were. And, of course, Turing's great achievement was showing that we can do software on top of a Turing machine, in a sense, right? And just as Gödel's great achievement was showing that mathematical formulas can talk about themselves, he showed how to do that, right? Turing did—he, if you will, built compilers.

Um, and it's funny: when you teach students nowadays the undecidability of the halting problem, you say, “Oh, well, if we could solve the halting problem, we could ask it about itself and then halt if it doesn't, and not halt if it does, and there we're done.”

And they're like, “That's it? That's what Turing is famous for, besides fighting the Nazis?” It's like, well, you've got to understand: this business of feeding programs to themselves was kind of astonishing, right?

I mean, in the early—even in the early 20th century—mathematics had this very stratified structure. There were numbers; then there were functions which act on numbers and produce other numbers. Then there were sort of meta-functions, or functionals, like taking the derivative, which takes a function and produces another function.

You couldn't feed things to themselves. What does that even mean? That's nonsense. And then along come Turing and Church and Gödel and show that you can. That's amazing, right?

And, like, Douglas Hofstadter talks about in Gödel, Escher, Bach, it's sort of like enzymes and proteins are both programs that can act on each other and data, like strings of amino acids. And nowadays this is the air we breathe. A text editor is a program that works on other programs; a compiler—people in compiler class compile their own compilers, right?

But I hope that we understand that, wow, this is actually really deep and amazing. So, yeah, that self-reflexivity, that ability to build things on top of other things.

Tim Scarfe

Yeah.

And, you know, what I like about the Chomsky hierarchy is that if you look at a Turing machine, it is kind of a finite-state machine with an infinite number of states, right?

And, you know, if you're used to having these little graphs of states, well, it is one of those. It's just an infinite graph. Then you go to this higher level of description and say, “Actually, this thing has a finite description,” right?

Just as if you have a stack, of course, you could draw an infinite series of states where you push, push, push, push and then pop, pop, pop, pop, and it would be a big binary tree if you're pushing and popping binary symbols and so on. It's an infinite thing, but then you move to a higher level and it has a finite description.

That move, I guess—that move is something that, yeah, I don't know. I'm not saying Turing machines can do it; I'm not sure you can use Turing machines to build it. Seeing the ability to do that, recognizing this next level, which makes a previous infinite thing finite, that's a very cool thing for an intelligent entity to do.

So, I know this is a little sideways to your friend's question. But that jump, to me, is really fascinating.

Tim Scarfe

Yeah.

And I think that's a little bit like recognizing a statistical regularity and then being able to predict. Yeah, well, but it seems like more. It seems like more. You've really recognized and captured an infinite set of objects all at once. You've achieved a step of abstraction, and I would love to have artificial partners that can do that.

Tim Scarfe

It also makes me think that there's a kind of sandwich here. People like Wolfram believe in digital physics, so ontologically, the universe is made out of computation. As a quick aside, you said yesterday that you lambasted people for using “computation” as a noun, which I thought was brilliant.

Compute.

Tim Scarfe

Sorry—compute. Compute. Sorry, I—

Yes.

Tim Scarfe

Anyway, “we need more compute.” I'm like, “Oh, that does not sound right in my ears,” but okay, I know—

Verbing weirds language, as Calvin and Hobbes said, and nouning does too.

Tim Scarfe

I know, but—

We need more weird, I guess.

Tim Scarfe

So, I guess the first part of the question is: are you a pancomputationalist? Or, maybe if you're not, the one step up from that is, do you think it's appropriate to use the computation metaphor to talk about the various computations that the universe is doing?

And then you were going in an interesting direction a little while ago, when you were talking about Joscha Bach, for example. He talks about this kind of memetic virtual computation. Our brains are simulators, and we do this metaprogramming, and we share programs around. It's almost like the programs are the agents, right? So where's the locus of agency?

Selfish meme.

Tim Scarfe

Exactly, yeah. So you've got the stack there. Coming from the Santa Fe Institute, of course, we were saying that my co-host Keith, of course, is a big fan of this Turing machine thing because he's an internalist, but you're surrounded by so many fascinating professors who have this very externalist, complex-systems view of things. There are so many ideas about thinking about intelligence. What does it mean to you?

All right. I like to talk about the computational lens. To me, as a kind of general scientist, to the extent I am one, I like to be agnostic about what I should focus on—or, if you will, what lens I should look through when I look at a system. Computation is one such lens. To me, that's the lens which focuses on the storage, transmission, and transformation of information in a system.

In the cell, I have friends who are studying cells and who study the origin of life. The ribosome is clearly, in part, a computational device, which is transforming information from one form into another. The error-correction mechanisms in DNA replication and so on are clearly, in essence, computational. You certainly learn a lot by looking at that system and looking for computation.

On the other hand, people who have tried to build artificial life, partly because they want to understand how life began in the physical world, have said that we've moved too far in a purely computational or formal direction. One idea about the origin of life is some kind of ultimately formal system where strings make more copies of themselves, right? This brings us to lambda expressions that make copies of themselves, or a Turing machine, or, in Core War, a little bit of assembly code that copies itself elsewhere and makes more copies of itself.

That is one approach—the sort of replicator-first approach to life. But some people think that the problem with that is that it doesn't recognize that organisms are really dealing with thermodynamic constraints. They have to get energy, manage chemical gradients, and extract free energy from those chemical gradients. So there's a lot of physics and chemistry that they have to do.

From this point of view, the fundamental thing is not the replicator. It's more like the metabolism: the thing which channels free energy the way a river channels water, or the way a lightning bolt channels electrical charge. This is a caricature, but you could say, “All this formal stuff—the genome, all these wonderful strings of symbols that look very much like Turing machines to us—is just stuff that the selfish metabolism built—

Tim Scarfe

To better channel free energy, right? As opposed to metabolisms being things that replicators built to get the energy we need to replicate.

And maybe, who knows which thing is the tail and which thing is the dog? Which came first? Maybe there's some truth to all of this.

Similarly, you could say that even the orbits of planets in the solar system are computing. They're computing their own future positions. Yes, you can say that. I'm not sure what we learn about planets by saying that. So, for me, as a pancomputationalist, do I think everything is computing? Yeah. But I think that in some cases, that's an informative thing to say, and in other cases, it's less informative.

I think that focusing on computation is just one lens. Another lens is adaptation. Are things evolving? Are they adapting? Are they learning, either within a lifetime or over evolutionary time? Yes, that's another thing that a lot of things are doing. Sometimes that's really important to understanding them. Other times it might be less so.

For instance, I have a strong allergy to evolutionary psychology. I know maybe some of the ways we treat each other and think and feel might be because they're adaptive, because we're social primates, blah, blah, blah. But I don't really find that helpful for thinking about ethics. The origins of things are not always the important thing about them.

The Constitution was written by slave owners. Yes, that's historically important. It's also a system that we can use and call upon now to try to do good things in society. Each of these lenses is interesting, and they reveal different things. It depends on what you're trying to do and what kind of phenomenon you're trying to understand. I think we should freely and fluidly switch back and forth between them when we're trying to understand different things.

Tim Scarfe

I didn't quite get whether you would agree or disagree that the universe, ontologically, in its primacy, could be thought of as computational. So I guess I translate that into: is it simulatable by a computer?

Oh, is there a distinction, though? I would think it would be possible for the stuff the universe is made out of not to be simulated by a computer, but for us to simulate it. Maybe I've just said something very stupid there. Maybe what you said was correct. Is there a distinction there?

I don't know. I mean, is a computer computational? A computer is this thing made out of elementary particles that are doing all sorts of crazy things. We exploit a small fraction of their dynamics to make pixels and do the computation we want it to do. Obviously, the laptop is doing all sorts of things other than the computation we want it to do. So is it, at the fundamental level, a computer? I don't know. I'm not trying to slip out of the question.

I like Feynman's question: if I have a spacetime box—a single cubic meter-second of spacetime—is the amount of information processing, or shall we say computation, in there finite? I'm inclined to think so, but I don't really know.

I don't think that, at the fundamental level, things are cellular automata, because I think that doesn't really work with quantum mechanics. I like this picture that, at the Planck scale, something funny happens to spacetime, so that you don't really have an infinitely divisible continuum of space and time at those smallest scales. I don't think it's a lattice, but maybe it's something more amorphous. People talk about causal networks and so on, and my first paper was about causal networks.

Anyway, I'm inclined to think that, at the end of the day, the physical Church–Turing thesis is true. One form of that says that any device that we could actually build would be simulatable by, say, a quantum computer with finite resources.

Then there's also the question of what it does by itself, right? Even in this box, there could be analog degrees of freedom that go all the way out to infinity. The states of this box could be real numbers that really have an infinite number of digits.

I spent some time in my career thinking about analog computation, which, by the way, has a wonderful, cool history, with Claude Shannon building mechanical computers and so on. So, if you have real-number computation, then in theory there are an infinite number of bits there that you could call upon. The question is: can you read from them? Can you write to them?

But even if we couldn't access them as engineers to do an infinite amount of computation, maybe it's still doing an infinite amount of computation itself, if you know what I mean. I'm inclined to think that's not the case.

Yes, I'm inclined to think that there is a finite amount of computation happening. If you want to say that means it's computational, although if there were an infinite amount, we could say it's computational too. It's just a really awesome kind of infinite hypercomputation.

Some of the work on hypercomputation is a little silly. What happens in black holes? You can set your grad students up in orbit around a black hole. Make sure that they have a hereditary monkhood which will keep working on a problem. Then you wave goodbye and fall into the event horizon. If their Turing machine ever halts—if they ever solve the problem—they send you a signal, which of course will vaporize you because it will be blueshifted into gamma rays. But then, in theory, maybe you could learn something. If you have a closed timelike curve, you can do really awesome things.

I don't know. Part of it is that physicists, which is my original culture, have an allergic reaction to infinity. For us, when something is blowing up—when an integral is diverging, say, or some infinite sum is diverging instead of converging—that's a sign that something is breaking down, right? That's unlike the idea that you seem to be able to do an infinite amount of computation in finite time.

The attitude is, “Oh, well, the problem with this black hole idea is that there's cosmic censorship, which will actually prevent us from making closed timelike curves. Or there's going to be some sort of noise or firewall, whatever, at the event horizon, which will blow up our ability to do this.” Or, as Sean Carroll says, the universe is expanding so fast that—it's rather grim, in my opinion—we can only do a finite amount of computation before the stars go out from the accelerating expansion.

This just pisses me off. I'm like, “We'll do something about it.” The point is not to study the world, but to change it. So let's do something about that, which gets us into science fiction.

For physicists, every time in particle physics there's something which seems to give an infinite answer, we think that means our theory is breaking down somewhere, and historically that's been true. That gives us this sense that there aren't any real infinities. In particular, that fits with the idea that we're never going to be able to build a box—or even find a box out there, made of black holes or whatever—that can solve undecidable problems.

But we don't really know, right? Ultimately, this is a claim about the world which may or may not be true. I'm inclined to think it is. I grew up on Fredkin and Toffoli's digital physics, reading Wolfram, and playing with cellular automata. So I kind of think something discrete-ish is happening at the finest scales of space and time.

Tim Scarfe

Fascinating. And just before we go, Chris, we haven't really spoken about algorithmic justice. This is something that you've been spending a lot of time looking at recently, and I suppose it's difficult because we're building these inscrutable neural-network models. I think, certainly in common parlance, there's this intuition that they need to be inscrutable because if we make them interpretable, and if we dumb them down to be understandable, then they don't work as well. But we now have these unbelievably illegible black boxes making consequential decisions in our society.

Right. I have thoughts about this, and maybe this is another conversation. I don't think these things should be inscrutable. I think there's a range of applications, right? If you recommend movies to me using a black box and I like the movie, everybody's happy. That doesn't bother me, right? Maybe if I were a filmmaker, I would want to know more, but it doesn't really bother me as a consumer.

At the other extreme, if you're putting me in jail even though I've not yet been found guilty of a crime, or if you're using AI to help find me guilty of a crime, we have these things in the Bill of Rights that say I should be able to confront my accuser. I should be able to cross-examine witnesses. I should be able to contest evidence.

The interesting thing about these systems—this is what people call procedural fairness—is that the criminal justice system explicitly cares about things other than accuracy, right? We've all watched TV shows where the guy actually did the deed, but the police planted the evidence. They violated the rules of evidence. They knew he was guilty. They wanted to put him away. Then they crossed the line, and because of that, he got to walk.

In our society, we think that's how it ought to work, right? We don't just want to be accurate in putting away guilty people and releasing innocent people. We want to have a certain relationship between government and its citizens. We want to have rules about how the government can surveil you and investigate you. That's really profound, right? How do you optimize for that? How do you even mathematize that?

In some of the work on fair machine learning, people look at statistical notions of fairness: We have this group of people, we have that group of people. I'm a little bit disturbed by the assumption that everybody belongs cleanly to one of these groups. I think that's part of the problem.

To the extent that we can divide the world into subpopulations, it's like, well, we want the false-positive rate to be equal, or whatever. That's a constraint. We can add that to the model; we can tack that onto the algorithm. People have done lots of good work in that direction.

But I'm really fascinated by these other, harder-to-mathematize notions—not just of fairness, but what do we really want these systems to do?

One interesting fact, which I recently learned from a guy named Mark Kaneus, who has a PhD in aerospace engineering, then went to law school, and became a public defender, is that a lot of the software products being used to do DNA testing—specifically, something called probabilistic genotyping—are used when, say, a couple of days have passed, there are multiple people who have passed through the scene, and the DNA has fallen apart into pieces.

There are some choices to be made here about how to determine whether the defendant was at the scene of the crime. This isn't a perfectly clean math problem. There are 2 or 3 popular software tools used for this. Some of them have never been—or at least until recently were not—independently tested by anyone. Many of them were not open-source; they were proprietary products, and they sometimes disagreed with each other, right?

What is the right metaphor here? Are these things expert witnesses that you can cross-examine? Not really. Are their designers the witnesses? Do you cross-examine their coders or the bioinformaticians behind them? If they disagree with each other, how are judges and juries supposed to evaluate which one is better?

For me, I like the idea of transparency, which is a stronger word than explainability or interpretability. I agree that transparency is a moving target. In some settings, it might just be: Has some independent agency—Consumer Reports or Underwriters Laboratories—tested this thing, and can they verify the vendor's claims that it works?

In some settings, that might be enough. In a lot of settings, even that is missing from things that are being used right now to make important decisions about people. In some other settings, I really want to be able to look under the hood. I know deep networks are hard to interpret, but at least it's a start. If I can look under the hood, I can do these sorts of fMRI experiments, like the Othello paper, where people try to do the tomography and figure out what kind of model it's building. I think that's a very interesting line of work.

I think that as humans, it would be very good for all of us—especially if we want a democratic society where we're making informed collective decisions about when to use these things, whether to use these things, and in what settings to use them—to try to understand these things as well as possible.

There are multiple sources of gaps in our understanding. Some gaps are there for honestly good reasons, like deep networks are hard to understand. Some gaps are there because of intellectual property, and because people don't want to reveal how these things work because they want them to be proprietary. I'm not very sympathetic to that second kind of gap, and I think that kind of gap should be closed.

I don't think we should be using opaque, proprietary tools to make decisions that affect people's fundamental human rights. I think it's a continuum. In health, it's interesting: If you're using a proprietary tool to diagnose my cancer, I'm a geeky guy. I'm really curious how it works. If it's been independently tested by people who are not paid by the vendor of the system and it's really led to good outcomes, even if it's a black box, I might go along with it because I want to live.

I think it's a continuum: What level of transparency would we demand? But when we get into constitutional rights, I think we should demand every possible form of transparency.

Tim Scarfe

Chris, it's been so lovely to have you on the show.

Thank you so much for joining us today.

The Day AI Solves My Puzzles Is The Day I Worry (Prof. Cristopher Moore)

Thank you very much. It's been a great time.