The Inception of Computer Science
Justin Yip
Brown University
Box 1910, Providence, RI02912, USA
Abstract
A recently released movie, Inception, illustrates human ability of inception, implanting ideas to others mind through dreams. The story line is based on “Little Harmonic Labyrinth” by Douglas Hofstadter, a professor of Cognitive Science at Indiana University. The key aspect of inception is to secretly implant ideas to the subject’s subconscious that he will never know it is implanted. This article discusses the movie in a computer science perspective, and argues that the movie itself is an attempt of inception of computer science concepts into the audience’s mind.
Procedure Call
In the movie, people enter and share the same dream via a device and the dream context is created by the mental projection of all dreamers. Cobb and his teammates dash in the subject’s mind and perform certain task, i.e. extraction or inception. When success, or dead, or timeout, the dreamer leaves the dream and returns to the reality. This mechanism indeed mimics procedure call in computer programming. Variables and objects (dreamers) enter a routine (dream) and perform some tasks, when they are done, they leave the routine and resume in the caller (reality).
Sometimes, the subject’s (for example, Fischer) subconscious is trained to guard against intruder, and he may also be well-informed about mind inception/extraction hence a single dream may not be suffice to carry the operation out. Multi-level dream is therefore applied. In a dream, Cobb sedates the victim again and enter another level of dream, dream-within-a-dream. They come closer to the subject’s subconscious and the subject is more apt to accept new ideas. The same thing is very common in computer science too. A procedure often invoke other procedures for a finer grained task.
Recursion
Indeed every procedure can invoke other procedure, and such process can go infinitely. Here we consider a special case: a recursion, a self-invoking procedure.
Cobb experimented it with Mal, his wife, they went into very deep level in the dream. It was good when it started, as they had so much time and they created their world freely in the dream. However, as time goes by, they lost track of reality. Mal failed to distinguish dream and reality. She thought the reality is yet another level of dream and killed herself in hopes of getting back to the “reality”.
This problem, in computer science, is commonly known as “Stack overflow error”. Stack is a piece of memory that stores information during a procedure call. When a procedure is invoked, the invoking program will store the current position and other meta-information in the stack. Once the procedure is terminated, it uses the meta-information stored in the stack to return to its caller. But computer has limited memory capacity. A finite amount of meta-information can be kept in the stack. When the stack reaches its limit and can no longer store more information, a “Stack overflow error” is casted and the program goes to limbo. The human brain may not be as discrete as a computer, which leads to a problem of failure to detect when the brain capacity is reached. Instead, the brain may overwrite information in a lower level, and this might be the cause of Mal’s problem of messing up dream and reality.
Cobb attempts to eliminate this problem alternatively. He forbids Ariadne to create the dream context using the details in reality. He insists that the dream world should contain some inconsistent structure (inconsistent in the sense of physical reality) to allow the dreamer to distinguish dream and reality. He is essentially trying to prevent self-invoking calls. In addition, a Totem, which has different behavior in reality and dream, is also used. The Totem is actually the base condition in a recursion.
Garbage Collection
Under normal circumstance, death in a dream results in awakening in reality. When special sedative, which provides stability for multi-level dream, is used, a dead person will be sent to the state of limbo and the person in reality will turn into a state of coma, and all his memory will be gone. Saito is severely injured in the gun fight at the first level, and eventually he is dead in the third. This poses a problem for Cobb, as Saito agreed to remove Cobb’s criminal charges when the inception is succeeded. If Saito losts in the limbo, coma in reality make him impossible to honor the arrangement and Cobb will be arrested immediately at the time he reaches the immigration. Therefore Cobb needs to secure Saito in limbo. It took Saito 50 years to be located by Cobb.
If we regard each passenger in the first class cabin as a memory space, a man in coma is essentially an useless piece of memory. Such piece of useless memory is merely a waste of memory space. We call it memory leak. The object is lost (all memory references are disconnected from the root) in the course of a procedure leads to lost of a person in reality. Therefore dead people in the dream has to be garbage collected, no matter actively or passively, by someone to reclaim the memory space. Cobb is the garbage collector. First he collected Mal, then Saito. Garbage collection exists in most modern programming languages, it makes our life so much easier. Thanks Cobb!
Exponential Runtime
In optimization, we often tackle NP-complete problems by enumerating all possible solutions (in a smart way). Enumeration is often implemented as a depth-first-search, which is usually a self-invoking procedure. Every level in the search procedure usually invoke a polynomial number (to the input size) of self-invoking calls. As a direct consequence, assume every procedure takes the same running time, the whole search takes exponential time. Despite enormous effort has been made to squeeze the runtime, the optimization researchers are all in limbo thanks to the NP-hardness nature.
Our dream goes faster than the reality. 5 minutes in reality equals to 1 hour in the dream. The same mechanism applies in dream-within-a-dream. It took a split seconds for the van to drop from the bridge to the water, while so much things happened in the deeper level. It is the best demonstration of exponential explosion when we tackle NP-hard problems. Cobb and Mal created the whole world in dream, since they had so much time.
This also imposes a substantial line of research. Instead of spawning the search procedure into thousands of sub-processes to arrays of hundreds of multi-core processors, hoping one of them gets into the right branch and find a solution, we may simply dive into a dream of deeper level and solve all kinds of NP-hard problems there, and report the wall-clock time in reality. What a good way to tweak experiment! I guess I can publish 1000 papers a year. As the reader would expect, I will write them in the dream.
Conclusion
The director has hidden a vast amount of computer science concept in the movie. It is obvious that he is trying to implant computer science concepts into the audience mind. Nonetheless, of course, the author of this paper, being a computer scientist, is fully aware of that.
Acknowledgement
Thank you Pascal Van Hentenryck for an insightful discussion (GC is actually his idea).
凍啡走甜 