The Inception of Computer Science (Spoiler)

2010/07/28

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).

廣告

16 回應 to “The Inception of Computer Science (Spoiler)”

  1. Patrick Says:

    雖然對文章一知半解 (computer programming 只懂一點MySQL 和 PHP) , 但Inception真的幾好睇 (唔知算唔算off topic….)

  2. C.M. Says:

    真係幾 geek… a very geekily interesting metaphor. (十個good)

  3. 強記小廚 Says:

    潛行凶間(Inception)呢類電影真係美國人幾buy嘅題材,最早同進入電腦(Inception係玩到入人腦)相關嘅電影,應該係Tron《電子世界爭霸戰》。
    部片真係睇到我痴,我過陣時仲係個小學生,已經有"商業保安程式","數碼化"等概念。仲有破天荒技術-簡單又原始的 CG畫面,開啟咗日後電腦動畫嘅發展

  4. Says:

    Good thoughts! 其實我覺得套戲同 Matrix 有啲似,可能分唔清邊邊係真實個部份。但我覺得 computer scientist 啲幻想力真係好勁,佢地先 imagine, 再 implementation , 最後竟然將有電無電(即 0 同 1) 可以搞到我地用既所有電腦/電子產品咁既樣。

    哈, 套戲可以諗吓續集,夢入面可以做好多研究,然後 return 返啲超高科技既野返黎??

  5. leona Says:

    The movie actually casts an open-ended question to the audience – Is Cobb back to the reality? Or is he permanently “trapped" at a certain level of dream?

    In your section “Garbage Collection", it seems that you believe Cobb has succesfully saved Saito to make the latter honour his arrangement?

  6. Manie Says:

    Justin,

    I am impressed by your efforts in illustrating an idea which you might have interested in and wish to share with us. I patiently read over every word of the article but still lost track in the middle. Nevertheless, I appreicate that you did try to elaborate the idea for layman’s understanding. Even I am an alien of computer programming, I can grasp some idea from your elaboration. Moreover, I only find a few grammatical mistakes throughout the passage.

  7. Justin Says:

    強記:等我有時間睇下先!

    鎚:我覺得導演有時係刻意模糊夢同真實,尤其結尾度。呢個導演,真係鬼才黎。

    Leona: wahaha, can’t believe you read the whole thing!
    And, the Garbage Collector Cobb can have BUGS, and falls into an endless loop!

    Manie: Thanks mum!

  8. j Says:

    so funny to read your post

    u r a funny cs guy

    what ‘s ur research topic?

    rgds
    another 馬料水大學畢業生 many yrs ago

    • Justin Says:

      I design and implement Optimization systems.

      幸會!

      • Stephen Yeung Says:

        在別人的潛意識植入其它思想去改變人, 同利用buffer overrun去進行入侵差唔多, 植入攻擊代碼, 奪取root權限.

  9. Stephen Yeung Says:

    戲中所提及的潛意識保護, 同CPU的Excute Disable Bit, Windows的Data Execution Protection都好相似~

    成套戲好似做緊有班人要去carck人地個system…..

  10. lxm1117 Says:

    this is great!


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

%d 位部落客按了讚: