This article explains concepts of computation, multithreading, and non-determinism through examples based on character Mr. Meeseeks from Rick and Morty, a popular animated sitcom.
There are two objects of interest that are important for the reader to be acquainted with – Mr. Meeseeks and Mr. Meeseeks Box.
Although this section lists their most important properties, I recommend to also watch the first 18 seconds of this video.
Mr. Meeseeks has the following traits.
- Mr. Meeseeks is summoned through the use of a Mr. Meeseeks Box.
- Newly summoned Mr. Meeseeks accepts input from his summoner.
- Upon receiving the input, Mr. Meeseeks interprets the input as a command and does his best to fulfill it.
- Upon completion of the command, Mr. Meeseeks stops existing.
Mr. Meeseeks Box has the following traits.
- Mr. Meeseeks Box can be used by humanoid beings to summon Mr. Meeseeks.
- Mr. Meeseeks Box never breaks or degrades in any way.
- Mr. Meeseeks Box can only be used finitely many times – if for no other reason other than the finiteness of available space.
For simplicity, Mr. Meeseeks Box is omitted from the rest of the article, and should only be understood as an abstract object describing the rules for summoning Mr. Meeseeks. The article assumes that a Mr. Meeseeks Box is within our possession.
Mr. Meeseeks as a computing platform
Before explaining how Mr. Meeseeks could be used as a computing platform, let’s briefly define what terms computation and computing platform mean.
Consider an algorithm that is being used to process some input.
This process is called computation.
It is universally agreed upon that computation generally proceeds in discrete, atomic steps.
A computation that terminates has a finite amount of atomic steps.
Computing platform is the figurative box within which the computation takes place.
Examples of computing platforms include the famous Turing Machine, or a computer.
So how could Mr. Meeseeks be used as a computing platform?
We summon Mr. Meeseeks and give him an algorithm and an input to use for computation.
A simplified example of this is as follows.
- summon and ask a Mr. Meeseeks to tell you the first 1000 prime numbers starting from 0
- wait for the results
It seems Mr. Meeseeks could be replaced by an arbitrary computing platform, e.g. a computer with an appropriate program or a Turing Machine that solves the problem of finding prime numbers.
But could Mr. Meeseeks replace an arbitrary computing platform?
Performance aside, the answer is yes.
The simplest way of proving Mr. Meeseeks is Turing complete is by showing Mr. Meeseeks is capable of simulating an arbitrary Turing machine.
Assuming that Mr. Meeseeks has the intellectual capacity of at least an average human, he most certainly can.
In fact, it’s relatively easy for humans to simulate Turing Machines.
One can write down an arbitrary Turing Machine on a piece of paper and start “solving” it step by step for any input.
Now, let’s use Mr. Meeseeks in a more controlled manner, more like a CPU or a Turing Machine.
This gets us closer to the fundamentals, and lets us atomize the computation process.
In addition, let’s make use of multiple Mr. Meeseeks during the computation.
- prepare an arbitrary algorithm and an input into the algorithm for Mr. Meeseeks to compute
- summon and ask a Mr. Meeseeks to complete the recursive Mr. Meeseeks‘ general order, which goes as follows: If the computation isn’t yet finished, complete a computation step, and then summon a new Mr. Meeseeks to fulfill the Mr. Meeseeks‘ general order using the latest context passed on by the previous Mr. Meeseeks. Otherwise, the computation is finished and the Mr. Meeseeks is to return the computation results.
- wait for a Mr. Meeseeks to return the results
This approach is quite similar to a genuine computation process.
Observe the presence of a recursive subroutine – both recursion and subroutines are hallmarks of modern computer programming.
Furthermore, the creation and workload of each Mr. Meeseeks happens to closely mimic the concept of threads.
Mr. Meeseeks and multithreading
Indeed, one could simulate the computation workflow from the end of the previous section using threads that perform one computation step, create a new thread, pass the computation context to the newly created thread, and then die.
Despite how slow this would be in practice, it is a neat mental exercise for grasping the basic concepts of multithreading, parallelism, and concurrency.
Consider the previous task of asking Mr. Meeseeks for the first 1000 prime numbers.
Instead of giving this task to a single Mr. Meeseeks, it is possible to make multiple Mr. Meeseeks work in parallel in order to achieve the end result faster.
- summon the master Mr. Meeseeks whose task is to keep track of all reported prime numbers, and then return them
- for each number n from 1 to 10000, summon and ask a Mr. Meeseeks whether n is a prime number. If so, have him report it to the master
- wait for the master Mr. Meeseeks to return the reported prime numbers
Hopefully, the end result is achieved faster due to multiple Mr. Meeseeks working together in parallel. At any one time, there may be multiple coexisting Mr. Meeseeks, independent with their own tasks and computation contexts, which corresponds to real world multithreading.
Note that just like it would be the case with a computer running this parallel algorithm, there are obvious problems.
The algorithm only uses a single master Mr. Meeseeks whose job is to collect partial results from every other Mr. Meeseeks. This master Mr. Meeseeks may be a performance bottleneck. Multiple masters would help mitigate this issue.
Another issue is that it may not be worth summoning so many Mr. Meeseeks, as summoning them may take longer than it takes them to finish their individual tasks. This can be mitigated by giving individual Mr. Meeseeks larger workloads, e.g. having them verify 100 numbers instead of just 1.
Mr. Meeseeks and non-determinism
Mr. Meeseeks can also help explain the concept of non-determinism, as in non-deterministic Turing Machines or the famous P vs NP problem (N stands for non-deterministic).
Multithreading and non-determinism may be imagined as similar concepts, and with a few adjustments, multithreading would be as computationally powerful as non-deterministic Turing Machines.
Let us make a few adjustments that would render Mr. Meeseeks as powerful as non-deterministic Turing Machines, and in effect, display the difference between deterministic and non-deterministic computing platforms.
- Mr. Meeseeks Box can now be used instantly (in zero time).
- Mr. Meeseeks Box can now be used infinitely many times.
- Mr. Meeseeks now take zero time to communicate with each other.
- Mr. Meeseeks is now always aware of all possible ways to branch the computation from the current step.
Take a moment to ponder the possibilities that previously weren’t available.
Recall the parallel prime number finder algorithm, which had a problem regarding having to summon 10000 Mr. Meeseeks, which would surely take a long time.
This problem would disappear entirely.
However, to really drive the point home, let us use the upgraded Mr. Meeseeks to solve a problem for which only non-deterministic efficient (meaning polynomial time) algorithms are known.
In practice, this means that although we can’t work out a solution efficiently for such a problem, we can efficiently verify whether a given answer is a proper solution or not.
For the upgraded Mr. Meeseeks, this is not an issue.
- summon the master Mr. Meeseeks who does the next step, and then returns the correct solution
- summon a Mr. Meeseeks for each possible answer to the problem, who then verify their own answers and report the correct one to the master
- wait for the master Mr. Meeseeks to return the correct solution
See how this algorithm is just as good as if we could actually efficiently compute the answer?
This will never be generally possible with multithreading, because creating threads takes time, because we only have a finite amount of CPUs available, and because real CPUs would spend non-trivial effort generating all the possible answers (possibly infinitely many).
Nevertheless, it serves well to outline the differences between multithreading and non-determinism.
Published on June 10, 2019 by Mário Uhrík