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.

### Preliminaries

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, which goes as follows:*Mr. Meeseeks*‘ general order**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. Meeseek*s 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 **master**s 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