This semester I’m taking a course on unconventional computation techniques, and one of the topics we covered was analog computation. Analog computers are a type of computer that use continuous physical phenomena like electrical, mechanical, or even chemical processes to model and solve problems. The main “programming language” for these computers is differential equations, more specifically, systems of polynomial ordinary differential equations (ODEs).
Through this paper, it can be proven that any discrete algorithm solved in polynomial time can be solved via a system of polynomial ODEs also in polynomial time.
An example of this is sorting, more specifically, bubble sort. If you are not familiar with bubble sort, it is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Surprisingly, bubble sort can be solved using a system of ODEs.
ODE for swapping two elements
The first step is to model the swapping of two elements in a list. Let’s say we have two elements and , and we want to order them such that . We can model the swapping of these two elements using the following ODE:
With this system of equations, if , then will grow to the value of and will decay to the value of as shown:
If , then the values will stay constant as shown:
The best way to understand this system is to understand the following differential equation:
where is a constant. The solution to this equation is , so when is positive, grows exponentially, and when is negative, decays exponentially. This intution can be used to understand the variable and how it affects the and variables. The , which initially starts at a really small positive value, acts as a “force” variable that controls the swapping of the and variables. acts similar to the constant. If , then is negative, and will decay to zero, and since it is a small positive value, it will decay super fast to zero, leaving the and variables unchanged. However, if , then is positive, and will grow, driving the down (because ) and the up (because ).However, as and get closer, the value will get smaller, the rate at which grows will get smaller, until , which is the point of inflection. After this point, will be less than , so , so will start to decay. This will cause the rate at which is decreasing and is increasing to decrease, until they both stop changing, which is the point of equilibrium, as shown in the first graph.
Here is the graph of the values swapping with also plotted:
You can see that grows when and decays when .
ODE for bubble sort
Now that we have the ODE for swapping two elements, we extend this to another ODE to model bubble sort for a list of 3 elements: This system of equations models sorting 3 elements such that . The is the “force” variable between elements and , and is the “force” variable between elements and . So for , it must have positive to make sure it is greater than , and it must have negative to make sure it is less than . The and variables are the “forces” that drive the elements to their correct positions.
Here is an example where the list is , or in our case . We want the end result to be , or . Here is the graph of the values swapping:
You can see that first and swap, but is idle, because from the information it has (only and ), it sees that it is in the correct position. However, once and swap, then and need to swap to get the correct order.
This can extend to any number of elements , as shown in this graph of sorting 10 elements:
Though this is not necessarily a practical way to perform computation at scale at the moment, I still think it is pretty cool you can take a discrete algorithm that is more of an abstract concept and model it using polynomial ODEs.