Reddit is weird. We can all agree on that. But sometimes, interesting things get popular on here.
Recently, a post became popular on r/theydidthemath, where a person requested to verify if a popular tweet [2] telling you can run Doom on 16 billion crabs is correct or not.
While the jokes poking fun at how Doom can run on anything, to all the bad computer and Crab puns in the comment threads are incredibly fun to go through, the main idea behind it is extremely interesting as well.
The numbers that the Redditors are commenting on seem to disagree with the Tweet, however, the number may vary with lots of considerations. If you're trying to emulate a Ti-83, like this commenter [3], you are getting a value of 340000 crabs to play doom. However, if you try to emulate an old PC from the time Doom originally came out, like this commenter [4], you get approximately 10 billion crabs, more in line with the tweet.
But as user u/obi1kenobi1 points out [5] in a response to the first comment I linked, the biggest challenge to playing a crabby game of doom is clock speed. Each processor can do a certain number of calculations per second. The more Calculations per second, the faster the computer, the more frames you get in your Demon Slaying fun. However, for ALL the crabs to move, and in sync with each other, it would be impossible to get it to be fast enough to be meaningful in any way. To render one frame of E1M1, it'd take years, if not centuries of time in Crab Cycles.
However, there's one more reason why this wouldn't work. And to get there, we've got a lot of fun stuff to talk about here, everything from Emergent Behaviour to maths where 1+1 equals 1.
You didn't see that coming?
A couple of proteins, fats, metallic ions, carbohydrates, and a whole lot of water. At their core, any cell in any organism, from the bacteria to the tallest trees, to the largest whales to the longest snakes, these things are essentially what we're made of. On their own, they don't do much. They just... exist. You wouldn't expect something complex coming out of a cocktail of proteins, fats, ions, carbohydrates, and water. But.... That is what life is. A cocktail of some unlikely chemicals.
Or perhaps some ants. The abilities of an entire ant colony of millions of ants is much more complex than what an individual ant does. (Kurzgesagt - In a nutshell, has an amazing video explaining this better [6]) Here's another amazing and beautiful example of emergent property that made rounds on the internet a couple of years back. [7]
Something with simple behavior can end up giving rise to some extremely complex structures. The examples aren't just limited to biology. The world's geopolitical scenario could be considered an example. Hundreds of nations all interacting with one another gives rise to complex relations, but that again is a result of hundreds of thousands of people interacting with one another, each with individual motivations. The formation of snowflakes is another example when it comes to complex structures arising out of simple details.
But we can get simple systems emerging from complex interactions between millions of such individual units as well. Take thermodynamics for instance. PV=nRT is a much simpler method to describe what goes in a box of gas than all the complex kinematic equations with millions of variables describing the Brownian motion inside. Similarly, with fluid dynamics. Of Course, the Navier Stokes equation is extremely complex. However, it's still simpler to describe a system through drag and Reynold's number than the kinematics of each individual particle.
Similarly, classical mechanics appears as a special case of quantum mechanics and relativistic mechanics. The entire field fo computer science is an emergent property of the behaviors of transistors.
Simpler, or complex systems appearing out of interactions of millions of little individual units, is part of a fascinating topic called Emergence.
And that is how our crabputer works.
1 + 1 = 1, and the world of boolean mathematics
Any logical statement can be categorized as a true statement or a false statement. And the ways of combining them, and For example,
The sun rises in the east is a true statement.
CW's Riverdale is a good TV show is a False statement.
In the English language, there are a bunch of conjunctions that are used to join sentences. As such, we can join these statements and make a compound statement. There are two conjunctions of note here. AND and OR.
Let's join the above sentences with AND and look at the compound statement's overall truth.
The sun rises in the east AND CW's Riverdale is a good TV show.
To determine the truth of this statement, we need to see that the first part AND the second part are true. If any of the two is false, then it becomes an overall false statement. As such, the above statement is false.
The sun rises in the west AND CW's Riverdale is a bad TV show.
As you can see, changing the order of the true statements does not change that the overall statement is still false.
The sun rises in the east AND Garlic Bread is the snack on the planet.
This would be an overall true statement, as we are seeing both the parts of the statement to be true.
Of course, if both of the parts of the sentence were false, it'd still be a false statement.
Let's join the above sentences with OR and look at the compound statement's overall truth.
The sun rises in the east OR CW's Riverdale is a good TV show.
To determine the truth of this statement, we need to see that the first part OR the second part are true. If any of the two is True, then it becomes an overall false statement. As such, the above statement is true.
The sun rises in the west OR CW's Riverdale is a bad TV show.
As you can see, changing the order of the true statements does not change that the overall statement is still still True.
The sun rises in the east OR Garlic Bread is the snack on the planet.
This would be an overall true statement, as we are seeing both the parts of the statement to be true.
Of course, if both of the parts of the sentence were false, it'd still be a false statement.
Let's try to represent this mathematically.
Throughout history, the logical mathematics has been represented with various symbols. But I'll share the one I learnt it from.
Each individual statement, if it's true, can be represented as a 1, and if it's false, as a 0.
For an And Statement, if both are True, ie 1, it's going to be true, ie, output is 1. Otherwise it's going to be zero. Hence, we can represent the And function by a multiplication. This can also be visualised through a truth table. It is a table, with all possible inputs for a given logical function, and all the possible outputs for the same function.
Similarly, we can see that when we add 0 and 1, we'll get a 1, and if we add two 0s together, we'll get a 0. The behaviour of the addition function is similar to the behavior of the OR gate. Hence, we use the addition symbol as the representation for an OR gate.
There's a little issue however. In conventional algebra, 1+1 equals two, not 1 like the OR gate requires. The brilliant mathematicians came up with a brilliant solution for this problem. Just hand wave it away, telling 1+1=1 ONLY in Boolean Algebra, and leave it at that.
There are two other logic gates, XOR, and NOT gates, and together, these four form basically all of the computers we use on a daily basis. XOR gate returns a true value only if both the inputs are the same. And as you guessed, the NOT gate just changes True to a False, and a False to a True.
Technically, an XOR gate can be built with a combination of AND, OR, and NOT gates. But it shall be left as an exercise for the reader.
But, how did crabs do this?
Well, the story begins when the scientists observed the crabs moving in the wld. The overall swarm seems to be moving in an orderly fashion, but the individual crabs move in a chaotic pattern. And on top of that, we can see that the swarm has an active front, and a passive tail. The tail of the swarm just follows the swarm, which implies that there's some form of directional preference to how the individual crab will move. There's clearly some form of order within this chaos.
Understanding this turbulence within the swarm can help us predict the direction the entire swarm will move.
So how does the swarm move?
Well, let's imagine a swarm of three crabs on a chessboard. Each crab is akin to the king in Chess, capable of moving one box in any of the eight directions. This is called the Crab's Moore Neighbourhood. (Basically, one unit square in all directions.)
Here, the pink squares represent the Moore Neighbourhood
Since there's a directional preference for the crabs, there is a higher probability that the crab will move to three of the eight squares. Let's define something called a POPULARITY. Basically, a value for all the eight squares around the crab. Higher the popularity, the more likely the crab is going to go that square.
First, we go each crab by crab, and assign the Popularity for all it's squares around it. Now, we got to account for two things. If one of these squares has a crab in it, it's popularity becomes 0. If it's overlapping with the box of another crab, then we add their popularities as the popularity of the square.
The common square with highest popularity
Finally, once we're done with that, we look at the positions with the most popularity, and see how many crabs can move to that position. We select one of these crabs randomly, and move it to the position. Once we're done with the most popular sites, and the crabs have moved, we can repeat the process.
Of course, this isn't a perfect representation. Each crab is an individual, and crabs don't really have an algorithmically coordinated plan on how to move when in a swarm. (Not one we properly understand, at least). There will be crabs that will wander around.
But there is one thing you can notice from the logic here. If two swarms of crabs meet at an angle, the combined swarm will move in the direction along the angle bisector of that angle. This is the emergent behaviour that the researchers used.
With this in mind, we can make easily make an OR Logic gate. Here's how the researchers represent the OR logic gate.
Since we're dealing with boolean values, we'll just have to see if there are crabs or not. It doesn't really matter with how many crabs are there in the output.
Okay, we got a working OR gate. But what about an AND gate?
Well, for that, we just make an open end for opposite the two input roads. This way, unless there's a collision (ie, both inputs being 1), there won't be an output in the main output in the middle. Along with this, you can also get a version of NOT gate on the two side roads you just made.
Now you might be thinking, Woah that's amazing. This is so cool. When can I get my new crabputer?
Here's the thing. If you try to fix an AND gate in real life, it's not going to work as perfectly as you'd imagine based on simulations. The crabs are individuals, and they'll do their own thing, as we discussed. When the researchers made the AND gate and tested it, most crabs went down the expected road. But there were a lot of crabs that wandered off. In the end, the output is the one where the most crabs enter.
The final challenge for making a crabputer, and running DOOM, is the inherent mechanism of the logic gates we're going to be making it out of. It's not perfect. And for computation, that lack of perfection is going to cause a lot of problems.
But this behaviour isn't unique to crabs. Any crowd, be it humans or bees will exhibit a similar property. In theory, you could construct a logic gate with Bangalore Traffic, and perhaps use that to make a computer.
[1] https://www.reddit.com/r/theydidthemath/comments/m8vi9p/request_how_many_of_these_crabs_would_it_actually/?utm_source=share&utm_medium=web2x&context=3
[2] https://twitter.com/NORMALHOROSCOPE/status/1372078896951087109?ref_src=twsrc%5Etfw%7Ctwcamp%5Etweetembed%7Ctwterm%5E1372078896951087109%7Ctwgr%5E%7Ctwcon%5Es1_c10&ref_url=https%3A%2F%2Fwww.pcgamesn.com%2Fdoom%2Fcrabs
[3] https://www.reddit.com/r/theydidthemath/comments/m8vi9p/request_how_many_of_these_crabs_would_it_actually/grjmied?utm_source=share&utm_medium=web2x&context=3
[4] https://www.reddit.com/r/theydidthemath/comments/m8vi9p/request_how_many_of_these_crabs_would_it_actually/grjp5po?utm_source=share&utm_medium=web2x&context=3
[5] https://www.reddit.com/r/theydidthemath/comments/m8vi9p/request_how_many_of_these_crabs_would_it_actually/grke3xl?utm_source=share&utm_medium=web2x&context=3
[6] https://www.youtube.com/watch?v=16W7c0mb-rE
[7] https://youtu.be/ix66tQ93bdU
All the information about the Boolean mathematics is based on my understanding of the topic from Sumitra Arora's Computer Science with Python Class 11 textbook.
I did my best to summarize the original research paper here. You can read the original paper here. Gunji, Yukio-Pegio & Nishiyama, Yuta & Adamatzky, Andrew. (2012). Robust Soldier Crab Ball Gate. 20. 10.1063/1.3637777.
I realize most of this stuff is confusing for most people. Start a comment thread if you've got thoughts, be it of confusion, excitement, or both. And I hope you had as much fun reading this, as I had writing this post.
Comments
Post a Comment