Computers Can’t? God is Probably a Computer Scientist
AI will now navigate through the space of All The Things — all computable things. Jump aboard and journey through a fascinating and beautiful landscape through the eyes of computer scientists.
⸻
“Computers can’t…” you say. Sit down for a minute and let’s talk about what computers can and can’t do.
1. All The Things
I don’t worship at the church of simulation, or have strong feelings about whether god exists. But if God does exist, He (or She) is probably a computer scientist. Life. The Universe. All The Things. Computer Science has more to say about it than you might think.
The universe you are in is a subset of all possible Universes. All Universes unfold, progress, and go from one state to the next, and therefore they are in the set of all processes that can be described as algorithms.
The Program That Runs All Programs defines the set of all universes that can ever be, assuming only that universes are a finite, discrete process: the Program That Runs All Programs is a program that simulates All finite discrete processes, and so simulates All The Things that can ever be.
You might think that you are not special for our universe seems not special in this set of All The Things. Except … that it is the only one that exists for you to observe it. It’s the only one you’ve got. Whether you are a simulation or not, you are absolutely special, as is your universe — do make it the best one that you can.
From the point of view of the people contained within this set of All Computable Things computer science neatly answers to “Why the universe?” and even “Why this universe?”, without even having a testable theory. I guess you could also ask why processes and not nothing. But I think the answer would be the same. If nothing, then no you asking about it.
Heavy stuff. The stuff of crackpots? What do computer scientists mean when we say “compute” and “process”? Alan Turing laid this out in 1936, building on his work with his PhD advisor, Alonzo Church. With a pen and paper, he imagined the simplest computer that he could. It reads from its memory (state; input), looks up what to do in a table (a process function; state transition function; the program) that tells the new state, which is written back to memory. He showed that this trivial toy, the Turing Machine, is Universal. In a sense, nothing more complicated seems to be able to do more — the simplest computer can do all the things that the most complex can… time and memory space permitting. All (discrete, finite) algorithms can run in a Turing machine. After 100 years of trying we have not found a model of computing that can do more. Nor do we expect to. The simplest computer can run any program, and any algorithm, and simulate any (discrete, finite) process that can exist in the universe, and indeed any universe that is such a process. Anything you can think, any mathematics you can write down, any simulation you can run, any person you can love, even you sitting on the toilet, reading online articles on your smartphone and thinking your thoughts and disagreeing with what you read appears to be represented in this silly little toy.
Quantum physics appears interesting because it suggests that maybe there is more… but not because quantum computers seem faster at solving some problems — speed doesn’t determine what is and what is not computable. From the point of view of what is simulated, the speed of the simulation simply does not matter. Neither is quantum mechanics special here because it appears to be non-deterministic — computers have no problem in dealing with (countably finite) multiple possibilities. Quantum effects are interesting because they appear to us to be fundamentally random, and so are perhaps appear outside what is computable. But when physicists suggested in Nature magazine that nature is ‘irreucibily random’, a computer scientist was quick to slap back by pointing out that randomness in the universe is still very much a hypothesis, and remains an open question — and it may be that randomness is really the result of a discrete, finite process whose function may be inferred (i.e. computed) from observations and so can be shown to be computable. Nature published the rebuttal from a computer scientist because it was correct. We really have no cause to expect that the universe is random when all that transpired before quantum physics appears to be representable without randomness, and quantum effects might be explained without it also. In the past, we saw randomness also. On closer inspection, it vanished.
Is our universe finite, and simulateable? Is this a matter of belief — faith? Or is there evidence to support this? Certainly there is evidence for the limits of existence — perhaps finiteness.
When the James Webb Space Telescope gazes out into the farthest corners of space, it does not see stars and galaxies in every place. It sees a lot of blackness — empty space. In a personal sense it is seeing the limits of causality. The sky is black not because the light of stars and galaxies fades with distance, but because the expanding universe makes what is farthest move away from us faster than the speed of light. What is far appears to us as indistinguishable from “beyond existence” — those farthest things travelling in our direction as fast at the universe allows — at the speed of light — are becoming more distant from us due the infinitesimal expansion of local space within the vast distances between here and there. Beyond a certain distance their light cannot light our skies and telescopes … or causally affect us in any way. And so there are hard practical limits on what’s needed to simulate the extent of our universe. And so computation about the vast extent of the universe performs its work over a finite set of things.
Practically, and pertinently, when we turn our telescopes inwardly we understand physical limits in both time and space at the tiniest scales — the Planck limit — theories of that, at least. And so, very possibly, things in our universe are discrete and continuous, and as finite at the bottom as it so clearly appears at the top.
You might argue that such a simulation of a physical universe depends upon real-valued computation — infinitely precise numbers. But I can point not just to the arbitrary precision of finite rational numbers within computing, but also to that The Program That Runs All Programs has available any and all computable representations. We often forget that computers can deal in complex symbolic representations also. 𝜋 is a computationally finite concept that we use in pen and paper computations daily — so too can (and do) computers perform the same computations. And so too can they deal in much more sophisticated representations. People are rather limiting to what is possible for computers to represent.
You might argue: chaos, complexity. Butterflies and tornadoes. Three body problems. But on closer inspection you may realize that this apparent randomness is just a matter of precision in our simulation and that we can just add more time and memory space to achieve perfection. Thanks to Andrey Kolmogorov and Ray Solomonoff, computer science even has algorithms for figuring out which program random number generator program can produce any sequence of random numbers that you give it. It’s a tiny leap to understand that from any observations, the programs producing them may be computed. Not only that, but tap dancing backwards and in high heels, the same algorithm finds the shortest program that computes any set of random numbers that you give it. This is true for “random” numbers deterministically generated by computers, but then also true for randomness in nature, assuming only that nature is a comptuable process — so we have a universal way to produce models of anything at all from observation. This is how we may one day discover models of sub-quantum effects just from observations of them. And from observations of raindrops on the porch a standard model of existence may in principle be inferred — if you like, a sort of microscope for computational models of existence. We know more or less how to compute them, even though there are details of over-fitting to address to produce a useful predictive model. There would appear to be no incomputable ‘randomess’ — there is only easy to compute and hard to compute, and also ‘requiring a lot of data’ to be sure.
You might argue: “we know that incomputable and unknowable things exist. What about about the halting problem?” Turing himself famously proved limits to computation. He showed that computing is “incomplete” and unable to do all things, and provided a short example: “what is a program that can tell me whether any program given to it will halt (finish)?” — this is an incomputable question and it was shown that no program exists that can test all programs, and so computing is formally incomplete. True… but the program that is the answer to that question lies outside of existence. It is, Turing himself proved, not in The Set of All Computable Things. If you believe that incomputable and unknowable things exist in the universe, in Nature, simply provide a single example! In fact, I don’t think we have or will find any examples of incomputable things in our universe. If you believe an incomputable thing exists in Nature, share with us a description of how you understand this works, and computer science will (likely) show you that shows you an algorithm representable in computation, and subject to computation. “We don’t understand, therefore computers can’t” (in the case of quantum mechanics), is a “you” problem, not a computability problem. The universe appears to be within what is mathematically ‘complete’ (in a more narrow sense) because the universe itself appears absent of any incomputable things. Even though a computable universe contains people asking for incomputable things (such as the halting problem), so far as we can see the universe has refused to produce even a single incomputable thing within itself. This is what we so far what observe — no strong evidence against computability.
Discrete.
Finite.
Within what is in computationally ‘complete’.
We have no cause yet to believe it is not so for our own existence.
Mathematics and computing are formally known to be incomplete. Not all question have answers. But we have no cause yet to believe it is so for answers within our existence to questions about our existence.
But “I can’t find refutations” I guess is a “me” problem now. Well now, you can’t expect me to have all the answers. I will humbly point out in my defense that whether the universe contains incomputable elements at all seems like the biggest open question in all of science.
2. From Theory, Towards Practice
Does this… you know… matter? Yes and no. We’re talking about impractically huge computational questions. You can’t actually run The Program That Runs All Programs in our universe. Don’t be absurd! You’d quickly run out of space after a mere handful of steps. And there are serious issues of compressibility — the program describing the current state of the universe might necessarily … not fit within it. The shortest program for the universe might turn out to be just as big or bigger than the universe itself. However, the point about computers and computability remains — the mind-boggling universality. The Program That Runs All Programs really does seem to describe All The Things that can be. Let’s give this set a big U… The Universe, so that it’s not confused with our own tiny little universe.
Given enough time and space, there appears literally nothing in existence that is not computable.
Alan Turing’s toy is so simple that it seems difficult to avoid running into it. When we write new computer programming languages, one thing you can do is write a “Turing Machine” simulator in it and have your program run other programs. When you do, you have proven that your programming language can also do All The Things too — we say it is Turing Complete. But you don’t even need to be looking within computing here to find yourself trapped in Turing’s model. In the 1970’s, Mathematician John Conway imagined The Game of Life. You can play it on a large checkerboard, and it has just these few rules:
And lo, the Lord spoke and said, “Yeah, dude… that’s Turing Complete too! It too can do All The (Computable) Things. Amen!” All the universes — from a checkerboard. You could, if you wanted, also have it simulate a Turing Machine … and you may then have that machine run The Program That Runs All Programs. You just need a really big checkerboard, lots of space and patience. But somewhere in there, in this finite checkboard, there is in principle your entire existence. You and all of your thoughts. If there’s something we should learn from the Game of Life, it’s that universal computing seems almost inevitable from mathematical systems that look like these kinds of discrete, finite processes.
In retrospect, this shouldn’t surprise us. State and tables of rules to follow. This is all a Turing machine consisted of in the first place. I hope set theorists, who look for a simplest universal model of mathematics are turning green with envy here. Here we have an even simpler model that contains all the math that can be thought.
Can computers? When it comes to questions related to your familiar existence, the answer seems likely to be always be yes… but for the difficulties of enough time and space. For matters merely limited to existence, it appears rather hard not to be computationally captured within the set of things found in the Program That Runs All Programs.
Can we be more directed? Can we ask more specific and practical directed questions about our present universe through the lens of computing? Are there shortcuts that avoid simulating things from the start of existence to find our present day and beyond? How common are the things that look like our universe in the set of All The Computable Things. Do simulations of the Universe reveal what is hidden from within them?
As models of nature, these Universal models of computation come with a big caveat. It’s easy to back-fit theories and models to what we see. It is when models make new predictions that we can test, and the predictions appear true, only then we can start to separate the coincidental chaff from the existential wheat. Physics is a wasteland of failed models — but physicists at least play good scientists and try to test and even disprove their models, and prefer to reject that which is not testable. Even though dark matter and string theory seem to be notable exceptions, eventually they insist upon the rigor of experiment so that we can replace belief with evidence. Criticism can be laid against The Program That Runs All Programs, and theories of a computable existence — it’s not yet falsifiable through experiment, as its not helpful in being predictive — we can’t yet test if its true — and we have little idea about how to answer this problem.
Enter Wolfram’s Physics project. From insanely simple computational rules (processes that transform graphs/networks) universes pop into existence that have rules strangely similar to our own, and seemingly able to explain, “Why space?”, “Why time?”, “Why quantum mechanics?”, “Why general relativity?”, “Why thermodynamics?” … on and on. At least, from the point of view of beings that would inevitably spring into existence in those mathematical sets.
https://www.wolframphysics.org/
Its bananas! We have, again from almost nothing, the inevitable signs of ourselves. Best of all, here we have a sort of theoretical computational microscope that can make predictions that we may soon be able to understand and test. If it turns out that it can make verifiable predictions of physics, we will have bridged a divide between physics and Universal computation and it will certainly be the greatest discovery in physics, mathematics, computing and philosophy — a unifying theory of existence.
Understanding how to search computational space for processes consistent with reality and predictive of reality is profoundly interesting. The Set of All The Things that The Program That Runs All Programs produces is mind-boggling enormous — recall, it contains not just every bit of information in every step of our universe, but all universes, and all other computable things. However, we are just 100 years into computing! And there are so vanishingly few universes that show the unlikely pattern of raindrops that you see on your doorstep that it gives hope that surely there’s a practical way to search and sieve through All The Things for our universe, and so discover a lens into it — its past, and its future. Or at least useful approximations of it. Could the computer scientist in 100 years, maybe be an oracle — a seer of the future?
Beneath the hubbub of deep learning and AI, European researchers have been asking questions along these lines for quite some time — the answers: some mindbogglingly big questions are not as impractical as you you might think. Marcus Hutter quietly introduced the AIXI framework for an optimal “Universal” decision making agent, learning and improving in the space of programs, but constrained by its observations in its own universe. It is optimal but impractical… and yet its not hard to imagine practical approximations of it. Schmidhuber introduced the Speed Prior — it suggests that the probability of a hypothesis given some finite observations can in some Universal sense be found in just O(n³+C) — and it does this work in the set of all programs. If you don’t know what this means, don’t worry. But if you’re a computer scientist, you may have just dropped your spoon in your cereal and found milk running down your chin. We’ve gone from mindbogglingly big numbers involved in dealing with the set of All The Things to (maybe .. one day) to algorithms that can make Universal predictions and require merely galactically impractical resources.
Is something even more practical possible? Soon we will have exciting new tools available to us. A few years ago a brilliant coworker of mine, Phillip Adkins, a mathematician, asked me whether I thought deep learning could lead to artificial general intelligence. I pointed out then that neural networks almost exclusively dealt with simple input and outputs — there is so much that they can’t do. And, at least, can’t do easily or well because they are not capable of performing general computing and because they don’t work in this grand Universal set of computation — the ability to solve particular (most!) kinds of task just isn’t in them, and they didn’t seem like they’ll be good representations of solvers for them. Can they add new or repair old programming? Can they replace a computer programmer? Can they improve themselves and significantly be applied to new tasks? Can they prove theorems? They can’t. They can’t even represent the problem. They can’t do even a tiny slice of All The Things because they don’t themselves operate fully in the world of computing and computer programs — they are not working in the space of Universal algorithms. He fired back — “Why can’t they? Why won’t they?” Well… good questions. This was perhaps just 10 years ago. Today the answer is that they can and they do.
“Computers Can’t” … can’t want exactly? I hear it spoken over and over that computers can’t do this or that. In 2018, “Computers do not create art”, wrote one philosopher. A position that was difficult to agree with at the time, increasingly difficult to take seriously a year later with the production of, frankly, jaw dropping generative image models, and appears categorically false in the context of the (impractical) Program That Runs All Programs, which, you know, … contains All the Lived Experience. All the Angst and Suffering, and so also All The Art. You may not be able to run The Program That Runs All Programs to simulate all the art, but given the the Universal nature of computing I’ve explained, I hope you’ll agree that it will in principle be possible to produce computer programs that can do anything a person can.
The next time you encounter someone you who begins “computers can’t” politely point them to The Program The Runs All Programs, and ask them to sit back down. “Impractical!” they will protest. Remind them that exact simulations of the universe are just not required. What exactly do you think is in practice (!) likely beyond the scope of these Universal machines when we relax the requirement for sub-quantum and sub-atomic precision?
Computing as a practice is just getting started.
3. Crictics. The Near Future
Today where are we? LLMs, Large Language Models (think ChatGPT) can write programs, and run them too. Do they do it well? No. Not always. Not yet, at least. In many ways, they are downright lousy. They know vast amounts but understand little. But does AI need to “understand” programs as people do to be useful and practical, and sufficiently capable enough to lift itself up by its bootstraps? Did people? No we did not. We evolved — we did not “think” ourselves into improvement, and so took millions of years to get where we are. AI has the benefit of being able to try millions of versions of itself in short order — days, hours. We tried something like this in the past with “genetic programming” and “evolutionary programming” which (almost) blindly searched the space of all programs. It had its uses, but has largely come up short, at least in comparison to the utility of today’s differentiable computing. The problem: computer programs are “brittle” and the search through the space of programs appeared undirected, and full of dead-ends. Small changes to programs breaks them, and we didn’t have an efficient way to automatically write programs effectively, or improve existing ones. But now … now we have AI that can do actual programming. And can perform directed improvements to programs, and repair programs, and write new programs, and write and run tests for programs. Not in cosmic timescales, but in seconds. For the same reasons, AI today can now also do calculus better than you. It can form new geometry proofs and do the SAT exams better than you. AI recently passed the law bar exam. With the advent of LLMs, it’s become crystal clear that the representability of programs in learning systems — how to produce and effectively manipulate these programs is a big nut that is really being cracked. To be clear, LLMs aren’t yet … great… at this. But for all of the failings of LLMs, I see no evidence that we won’t, in a very short time, see AI lifting itself up by its bootstraps. Will it? Can it? I see no evidence that AI will not. And remember, as I said earlier, people have been rather limiting to the progress of computation — we program computers using the representations that our tiny minds allow. Universal computing and AI have no such limitations.
We’ve had algorithms and algorithm frameworks intended to work in this larger more expansive way since at least 1987 — not just learning algorithms, but algorithms that rewrite themselves to learn faster, to develop theories and hypotheses about the world, and even having curiosity as a formal goal, to act as a good scientist does and to actively test and refute its theories. In particular, they were conceived to be Universal — representationally unconstrained and designed operate freely within the space of computer programs. In 1987, we lacked the tools to build these systems and the ability to navigate within the space of programs. Today, I think we have them.
“AI so stupid!” “AI can’t even,” cry academic critics of today’s language models. They are not wrong, exactly. But we’re some months into seeing truly useful AI here — it’s a little like watching a parent scolding a child for an imperfect violin recital. It really doesn’t matter. Barely enough here, is good enough. The major advance today is not the “amount of intelligence” — this will come over time. Being able to have programs successfully “think” about programs at all places new AI in an open space where it now at has access to work in set of All The Things toward its solution, including practical, directed, improvements to itself, if we permit it. AI is now a ship with a compass that can sail around what is possible and practical in the sea of All The Things. It is a profound and expansive shift. I’d argue we’re crossing a more profound threshold today than we might with the advent of any artificial general intelligence (AGI) — a discussion mired by shifting comparisons to human intelligence. The hubris! In the Pale Blue Dot, Carl Sagan reflects how the entirety of humanity exists on a single tiny dot seen by the camera of the Voyager 1 spacecraft as it passed by Saturn. Carl just wasn’t thinking big enough. Our entire existence is a microscopic speck compared to Turing’s Universe that AI is now entering.
If your God is the creator of All The Things, what is the computer programmer that writes programs that work within and create within the space of “All The Things”? In a real sense, the computer programmer is about to become a minor God — creating that which certainly determines which paths that we will travel through in the set of All The Things.
The time where AI is programming and navigating around the set of All The Things is arriving because (approximate) Universal computing is now surely coming. Why wouldn’t we expect AI to quickly exceed and replace its programmers, and beyond? Questions along the lines of: “will AI…?” and “can AI …?” will soon be more directly and trivially answered by asking only “is that part of the set of All The Things reachable by AI?” And so too, it is a great time to also ask, “should AI …?”
∎
Also see:
A list of undecidable problems. (A list of things don’t exist in nature!)
https://en.m.wikipedia.org/wiki/List_of_undecidable_problems
Computation and its limits, 2010. Cockshott, Mackenzie, and Michaelson
A Computer Scientist’s View of Life, the Universe, and Everything. Jürgen Schmidhuber https://people.idsia.ch/~juergen/everything/html.html
Algorithmic Theories of Everything. Jürgen Schmidhuber https://people.idsia.ch/~juergen/everything/html.html
The Universe is a Computer. You Again Schmidhuber expanding upon Konrad Zuse. https://people.idsia.ch/~juergen/digitalphysics.html
The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions. J. Schmidhuber. https://people.idsia.ch/~juergen/speedprior.html
The Incomputable Reality. Barry Cooper. Nature.
https://www.nature.com/articles/482465a
What Computers Will Never Do. Messerly. Reasoning and Meaning. January 23, 2018 https://reasonandmeaning.com/2018/01/23/what-computers-will-never-do/
Why Computers Won’t Make Themselves Smarter. Ted Chiang March 30, 2021 https://www.newyorker.com/culture/annals-of-inquiry/why-computers-wont-make-themselves-smarter
Tegmark’s Computable Universe. Tegmark is a cosmologist but seems late to the game, but also noted that incompleteness (Godel and Turing) doesn’t prohibit a computable universe. That which is mathematically incomplete lives outside of nature.
https://en.wikipedia.org/wiki/Mathematical_universe_hypothesis