Archive for 七月, 2010

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

廣告

做臭我個朵

2010/07/13

啡大電腦系有個不明文的傳統——從不直接由中國招收博士研究生——系裏絕大部份中國學生都是在美國大學諗本科的,聞說原因是學生質素參差、其成績和其他往績含有水份的機會頗大、系裏沒有中國教授於是缺少直接聯繫、清華北大的高材生都跑到柏克萊普林斯頓了、餘下的落差太大風險太高,畢竟收一個研究生每年牽涉幾十萬港元的開支,與其倒進咸水海不如多請幾個訪問學人互相切磋擴闊視野。

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

我敢本著良心向全世界大聲說,我在啡大的所作所為對得住天地對得住香港。早前聽見敝系教授說中國學生的質素在提升,心裏開心好一陣子,自覺對國家有了點點貢獻。

每見一些不濟的同學,我不禁想「你不如番歸唔好响度獻世!」。看見接二連三來自中國的造假新聞,自不然會恨之深痛之切。

你老味你造假你死你事吖,但仆你個街你造假你做臭我個朵呀!

知唔知咩係stereotype呀?別人誤以為香港位於日本,我反覺得榮幸,那是因為別人認同香港高質素的服務。但中國製造又代表甚麼呀?這麼多造假造假造假,要別人怎樣相信我們也能做出世界級的科學研究?要欺騙人麻煩欺騙得高明些少,話曬出貓唔好太高分,閣下老作自己有博士學位,其實一吹就露底。

正正因為這麼多造假學歷假論文,啡大電腦系才不收中國學生,閣下造假到頭來累番自己人!

直到拾回自己

2010/07/11

人愈大愈覺得自己功利掛帥,做事的背後總隱隱埋藏著某些動機,每個決擇總起碼有某程度的得失計算利害考慮,行事時往往是為了其他目的,有時那些其他目的甚至羞於啟齒。

比方說,諗博士努力寫論文其實不是因為喜歡做科學研究而是為了日後豐厚的薪金,日以繼夜開發電腦系統跟其他軟件供應商比拼只為搏聘書一份,在外國讀書定時給娘親寫家書是因為怕她於百忙中忘記給自己寄生活費,在別人的網誌踴躍留言不過是為該作者的垂青,花一個下午寫文向報章投稿亦主要不為跟讀者交流而是希望豐富自己的履歷,去歐洲旅行給女朋友寫明信片是為省卻代買名牌手袋的舟車累頓,在夜半煲完電視劇給論文導師發電郵報告研究進度也不過為暗示明天早上閣下不用旨望找到我。

每當夜半夢迴反醒自己一天以來的所作所為,在興幸自己運用小聰明走過一關又一關後,發覺原來自己十分邪惡,做事時往往別有用心地為了其他目的。雖然白天時總能把動機掩飾一下,但晚上於床上輾轉反側,覺得這樣無盡的計算實太過自我抑壓,不禁問,究竟我這樣功利的生活意義何在?

最近開始認真地打羽毛球,認真是指一切都要盡量做得好。由最基本的發高遠球練起,自己靜靜地站在羽毛球場一角不斷重覆練習發球,目的是令到每一球都落在底線旁的一角;然後跟波友一來一回地打高遠球,就是想要聽見擊球一剎那鏗鏘悅耳的聲音;最後計分打比賽,贏輸絕無相干。每次打完羽毛球,拖著沉重的身驅回家,我都覺得舒暢無比。起初我不明所以,打波除耗盡體力外一無所有:羽毛球場上女生少之又少,自己又經常打失波累街坊輸比賽毫無成功感,老闆又不在場於是無需表現勇猛,我永遠打不贏林丹謝杏芳,打羽毛球是換不了錢和成就的。實不能解悉為何打羽毛球能使這樣功利的我身心舒暢。

不過,漸漸發現原來做運動使人身心舒暢的奧妙之處,正正在於它的輸贏無關痛癢,一場比賽便只不過是一埸比賽,於是打羽毛球的動機和目的就只是為了把羽毛球打好,沒有其他利害考慮,動機十分純潔。一天到晚我都在數算利害得失,羽毛球場反成為一片寧靜的空間。常聽人說「要拾回自己」,想來意義就是如此。

(刊於同日《香港經濟日報》)

%d 位部落客按了讚: