Non-Newtonian Computing?
A Physics Analogy
The original foundation of modern physics is Newtonian mechanics; given a collection of objects and their positions, velocities, and some knowledge of the forces between them, you can compute their trajectories by playing time forward one small step at a time. There is a tremendous amount of useful work that can be done with simply this tool, but modern physics would have a fraction of its current utility if we had merely stopped there.
Physics can be reframed in different ways. Another framing is Lagrangian mechanics, which looks at both the kinetic and potential energy of a system and asks how to convert that potential energy into kinetic energy in the minimal amount of effort. There is also Hamiltonian mechanics, which looks at the sum of kinetic and potential energy and analyzes the consequences of the total energy being conserved. Hamiltonian mechanics in particular lends itself easily to extremely rich mathematical tools such as linear algebra and group theory, as any physical system can be framed as rotations of a high-dimensional sphere (conservation laws are encoded as a constant radius) and is the foundation of a great deal of modern quantum mechanics.
It's worth asking if a similar analogy can be made in computing - are we currently stuck on "Newtonian computing", with future computing paradigms on the horizon as future developments? What might these things look like? Where should we look? What might we expect to come out of them?
We probably shouldn’t stick to this analogy too strictly - though perhaps a creative person could come up with some fairly literal translation of Lagrangian mechanics or something that might actually be useful. That’s not where I would start though, these examples from physics are just an analogy.
The Idea
Specifically what we’d likely be looking for is an alternative way of viewing computation. Currently much of computing is based on a simple gate-based model; you have some collection of bits, you pass some subset of them in as inputs to a gate, and this performs an operation on the input to generate a collection of new output bits. These outputs can be added to the pile of bits, or perhaps if you have limited memory can overwrite existing bits.
Whatever alternative frameworks we develop would still need to encode all of this, but might highlight some new relationship or property that wasn’t obvious from simply staring at a sea of gates.
Reversible Computing
Reversible computing may be one interesting perspective that may be deeper than we currently realize. This is a research area that already exists, though has a fairly small number of active researchers. It is concerned with the properties of computation that preserves information. All gates have an identical number of inputs and outputs, and all are bijective; every output has exactly one corresponding input. If you want to encode something like an AND gate, where three of the four possible inputs all map to the exact same output, additional “ancillary bits” are required to make these outputs different.
This is effectively conservation of information; while these ancillary bits may appear to store unnecessary junk information, they happen to encode just the right information required to run the circuit in reverse. Running circuits in reverse is in general NP-complete, and often can take exponential time. This is why breaking cryptography is hard, among many other things. What makes it hard is that there is a tremendous amount of guesswork in reversing a circuit; if you’re only told that an AND gate outputs a 0, you have no way of knowing if the inputs were 00, 01, or 10. A guess-and-check approach is fundamentally required, and while some amount of inference can be used to narrow the range of guesses, multiple unknowns in a large circuit tends to result in an exponential explosion of possible states to check.
Reversible computing preserves all of this information; if you have the ancillary bits, no guesswork is required. This is not magic, nor is it some threat to cryptography; the person who computed the cryptographic signature or whatever it is you’re trying to break would be the only person with those ancillary bits, and handing them over for an attacker to use is an obviously stupid idea.
Reversible computing will likely become more important in the future anyway. There are fundamental thermodynamic limits on the energy efficiency of computing (Landauer’s Principle), and we are only about 4-7 orders of magnitude away from hitting them (depending on ambient temperature). If we wish to throw away or erase information, this fundamentally takes the form of generating waste heat, which corresponds to a certain amount of energy spent. The only way within known physics of circumventing this is to build physically reversible computers that never generate waste heat because they never throw any information away1. This will require changing many deep and fundamental ideas around both software and hardware, and will undoubtedly require us to abandon CMOS transistors in favor of some fundamentally different technology.
If quantum computing ever pans out (I’m doubtful), it too is reversible, and will force reversible computing principles on any engineers who decide to use it.
With all this said, there is something very interesting in this idea of conservation of information that echoes conservation laws in physics; in fact, the extreme dependence on Hamiltonian mechanics found in quantum math and the inherently reversible nature of quantum computing are deeply related. It is likely that, with the right approaches, much of the rich mathematical toolbox that modern physics uses in Hamiltonian mechanics could likely be imported into studying computing, provided we choose to conserve information.
Constraint Solvers and NP
As stated above, reversing circuits is a problem that is exponentially hard, and fundamentally boils down to a great deal of guesswork. It is also NP-complete; complete in the sense that this problem is expressive and powerful enough to be able to emulate any other problem in NP, which is a truly vast range of problems including both almost all the problems we solve with computers daily as well as many more that most programmers are often too afraid to approach.
I also mentioned that there are inferences that can be made to reduce the amount of guesswork. If you are given an AND gate and a XOR gate that both receive the same inputs, and the AND gate returns a 0 while the XOR gate returns a 1, you can infer that at least one of the inputs must be a 1, which narrows the range of possible inputs to the AND gate from 3 to 2. The input must either be 01 or 10, as if it were 00 the XOR gate would have returned a 0. This is a simple example, much more complex inferences are possible too.
Overall, this approach to computing can be seen as looking at the entire state space of a problem (or at least looking at a collection of smaller and more manageable subspaces) and crossing out possibilities that don’t make logical sense, which in turn often can propagate information and cross out other possibilities. The overall problem is actually fairly simple, and most of the complexity comes from trying to do it with tractable amounts of computing power and memory, as the state spaces are exponentially large.
These inferences can dramatically reduce the amount of work required to solve these types of problems, though exactly how much work can be saved can be very difficult to answer. These systems can easily play by strange rules and approaches to the P-vs-NP and related problems have really only demonstrated that we will likely need to develop fundamentally new mathematical tools to see serious theoretical progress on the big, open questions.
While these problems can be very tricky to work with in theory in in the general case (they can be a bit easier to reason about if you focus on special cases), in practice they seem much more promising.
While there can be many situations where there are exponential explosions in difficulty, the past few decades of research into SAT solvers and similar algorithms have shown that there are a shockingly large number of cases - especially when dealing with "real world problems" where things turn out to be much more manageable. There are many very useful situations where the power of logical inference overwhelms exponentially exploding guesswork.
I would not be surprised at all if there are insights we can gain from studying these types of problems more carefully. If you encode a polynomial-time problem as a SAT instance or similar NP-complete problem, you tend to do so by building a circuit of gates using Tseytin transforms, and the way these gates are wired together creates a kind of information cascade where there is never any ambiguity or guesswork as long as gates are evaluated in the right order. Work on SAT solvers seems to suggest that there are more complex cases that involve only modest amounts of ambiguity that is easily resolved, and it’s worth asking if there are new types of algorithms that we could build that exploit this.
I personally find that a large chunk of modern “AI” hype is actually just using good-old-fashioned search/optimization algorithms, perhaps with a neural network bolted on. The notion that hard search algorithms can be accelerated substantially with the addition of a learning algorithm is nothing new, and caused a revolution in SAT solving before I was even born. The AI people are late to the party.
I also suspect (motivated by some personal research and projects of mine) that current research into backtracking algorithms (like the ones that SAT solvers use) is merely the tip of the iceberg, and that a tremendous amount of new innovation could be made with more serious effort into this space. I expect that such algorithms would likely prove much faster than these neural networks, though might be slightly more difficult to build than simply shutting your brain off and letting the GPUs go brrr.
Been a bit busy lately, though I’ve been thinking over some plans on where to take this blog in the future. I have some projects I’m working on that I’ll likely share here in the coming months. I’d also like to do an in-depth series on NP-complete problems and continue my neuroscience series, though we’ll see when I get around to that.
I should probably do a Bzo devlog soon.
Technically you’d actually want some kind of quasi-reversible computer that does throw information away, but only when told to. Reversible computers, like any computer, have a finite amount of memory, and so generating bits that cannot be discarded is not something that can be continued indefinitely. In many cases, work can be “uncomputed” to clear up more memory, though in some cases it might be cheaper or faster to simply spend some energy turning it into waste heat.
Reversible computers also will never use zero energy, but at the very least can be made more efficient until other bounds are reached.