Archive for 七月, 2010

The Inception of Computer Science (Spoiler)


The Inception of Computer Science

Justin Yip
Brown University
Box 1910, Providence, RI02912, USA


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.


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.


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.


Thank you Pascal Van Hentenryck for an insightful discussion (GC is actually his idea).




在洋人眼中香港確是中國不可分割的一個部份,香港學生便就是中國學生,二者基本上沒有分別。背著這個身份使我很在意中國學生在其他人眼中的地位,我不介意別人享受陽光海灘時笑我們如牛般勤力只顧生產沒有生活每週工作上六七十小時(如Malcolm Gladwell在Outliers說亞洲人視努力工作是民族性是件美德),但我極之在意別人覺得我們虧覺得我們廢覺得我們礙事覺得我們只會抄襲。














%d 位部落客按了讚: