What are the limits of what we can do with computers? I mean, it’s not obvious that computers have limits, right? They sure seem like they can do anything, with the only limitation being how fast the processor is or how much memory you have. What are the real limits of computation: not pragmatic limits like “is it realistic to try and search through a petabyte of data for an exact string in under a second?” but rather what are the things a computer could never do even with CPUs that run quadrillions of times faster than what we have now?

Thus we set the scene for our little story, shifting ourselves in time and space to a far distant future: an age of hyper-tech and space travel with unimaginably fast computers and yottabytes of data that can fit in your palm.

In specific, though, we find ourselves watching over the shoulders of three engineers—Adam Turing, Kat Goedel, and Gabriel Cantor—as they discuss their next big project: a machine that will be able to create stars, planets, and if our characters have their way, entire galaxies.

I’ve chosen to bring us to the most interesting point of their long ranging discussion, the point at which our engineers realize that their goal of building a galaxy engine isn’t so sure a thing!

Let’s listen…

“I was doing some reading on 21st century technology and I had a bit of an odd thought,” said Turing, hoping to get the rest of the group’s attention.

Cantor folded their translucent tablet and sighed as they put it back in their pocket. “And would you care to share what this odd thought is?” they ask with some annoyance. Goedel is staring at her tea, thinking.

“Well, I was thinking: take away all the references to the fundamental particles that make up matte and a star builder would, basically, have to be a lot like an old-fashioned 3d printer! Hear me out. It’s still a device that has to be told how to put things in places, it’s just creating systems of quarks and electrons instead of laying down plastic or metal.”

“That makes sense but I’m not sure how it’s helpful.”

“Well, Cantor, the interesting thing is that since we want one machine to create a variety of objects we need to be able to tell it what to do; hence, it needs to be programmable!”

“So we need to be working on a programming language for describing the relationships and positions of these particles? That would be a programming language for physics at small scales, for quantum mechanics itself!” they ask.

“Exactly! Once we’ve got our programming language we’ll be able to code up atoms, then stars, planets, and eventually galaxies! The mechanics of the machine will almost certainly be trivial.”

At this point, Goedel clears her throat and interrupts the conversation.

“That might be a problem, actually.”

“Why? If we can code it we can build it. What’s the problem with that?”

“Turing, not every problem can be solved with a computer! I’m particularly skeptical about this one.”

“Why?”

“Well, let’s remember what three things need to be true for a problem to be computable? It needs to take finite time, use finite resources, and be written down in a finite length program.”

“Yes, obviously, but where’s the problem?”

At this point, Goedel holds up her thumb and forefinger with a little space between them.

“How many points in space exist between my fingers?” she asks.

“Well an infinite number of them! I learned in college that space is continuous, which means between any two points there’s always more points between them. That implies an infinite number!”

“And how many decimal places would you need to describe each and every one of them to perfect accuracy?”

Cantor’s eyes go wide as they say, “Ah, of course, an infinite number of decimal places are needed. Pi alone requires infinite decimal places to store.”

“Further,” Goedel continues, “There are at least as many configurations of an atom as their are points in space. There aren’t enough programs to describe them all!”

“But aren’t they both infinite?” Turing asks skeptically.

“There are different sizes of infinity, though!” Cantor points out. “The number of possible programs is the smallest infinity. The number of points between her fingers is the next smallest infinity in size, which is massively larger.”

Turing thinks for a moment. “So it sounds like there’s too much information and too many possibilities to build our galaxy builder. That’s rather disappoint—wait, there’s one possibility we’ve all overlooked. What if the universe is discrete instead of continuous? In other words, what if there’s only a finite number of points between Goedel’s thumb and forefinger instead of an infinite number of them!”

Goedel frowns at this. “Yes but we have over 800 years of physics built around the assumption that space is smooth, continuous, with no gaps between points!”

*“But that doesn’t make it true! We need to go talk to the physicists…”
*

What happened after this? Were Turing, Goedel, and Cantor ever able to build their engine? I don’t know! Even from my lofty vantage point, I don’t know whether the universe is discrete or continuous or whether, if the universe is discrete, we can write a programming language for building matter out of the most fundamental of building blocks. What I do know is that people are working on understanding these very problems today and not in some hyper-tech future!

That brings us to the conversants in our trialogue: they were named after three important people in the history of computation.

- Alan Turing, who provided the first proven example of an important problem that couldn’t be solved with a program
- Kurt Goedel, who connected the limits of computation and the limits of logic in mathematics
- Georg Cantor, who created the foundations for modern mathematics with his set theory and was the first person to realize that there were different sizes of infinity

And here’s another way to describe this question about printing galaxies, from a talk I gave:

### Learn More

#### Cantor’s different sizes of infinity

https://www.coopertoons.com/education/diagonal/diagonalargument.html