前些日子提到 Ackermann's function 後，也讓我回想起一些有趣的小問題。
其中一個，是寫個程式，它不管輸入什麼，都會輸出自己（這份程式）。這個問題之所以有趣，一部份的原因，是因為乍看之下，要求得一組解（寫出一個能夠「輸出自己」的程式），似乎並不困難。但真的如此容易嗎？有興趣的人可以試試看。
第一次碰到這個問題，也是在 Maryland 時，計算理論老師 (Dr. Smith) 的講義裡，某個習題提到的。當時是沒有出這項作業，但我有花幾個小時嘗試寫過，並沒有成功。（嗯，還是一樣，沒有成功解出的問題，比較會印象深刻...）
在課堂上，老師也提到過，我們可以證明：不管是哪種程式語言 （只要它們的計算能力相同，都是 Turing-complete -- 現在幾乎所有的程式語言，像是 C、BASIC、JAVA、LISP、PASCAL、PROLOG，甚至 PHP，都是 Turing-complete），總是存在著（無限多個）這樣的程式，它們可以輸出「它們自己」（此證明可參考這本書末，對習題 2.13 的解答）。
自己則是在數年後，從 BBS 上看到有人貼出用 C 語言實作的漂亮答案。我將它稍微修改，展現成 PHP 的程式碼：
<?php $s='<?php $s=%c%s%c;printf($s,39,$s,39); ?>';printf($s,39,$s,39); ?>
你能夠自己寫出這樣的程式嗎？
4 則留言:
咕狗大神真好用 :)
http://www.nyx.net/~gthompso/quine.htm
裡面有各式各樣語言寫的程式，有得寫的還真複雜，不過好像沒有 PHP 寫的.
哈哈，看來貓還是咕狗大神的虔誠信徒呢...
呵，上次貼迷宮時按到 Anonymous，我是 Lab303 的學弟。記得這個東西的理論基礎是在 Michael Sipser 寫的 Introduction to the Theory of Computation 裡面提到的 Recursion Theorem（另外一個觀點是從 fixpoint 來看待）。
以前做過一個題目，題目給定一個很奇怪的程式語言，storage 只有一個 queue 和 26 個 register。做什麼運算都是從 queue 的前面摘兩個出來，算好以後再塞回去。當初沒有時間去思考這個計算模型是否和圖靈機等價，因為他太難用了。做什麼運算都沒有辦法立刻得到結果，要等到 queue 裡的東西被吞吐過一輪後才能拿到，而什麼時候算吞吐過一輪？很難判斷。
有趣的地方在於，雖然在寫一般的程式時非常吃力（例如第一子題要求寫排序程式，就花了我很多時間），但是要寫自我產生的程式卻是非常容易呢。這讓我想到，自我產生的程式的最弱的條件是什麼？也許不用到圖靈機那麼強呢。
是了，在 Sipser 的這本書，p.198 有給出 self-referencing program 的存在性證明。
還是對網路服務 (Internet 基礎設施、Blog service 等) 與檢索技術 (Google search) 的進步感到敬佩。沒有這些（當然啦，前提是要有 content providers，還有會看 Blog 的人），如何能在這麼短的時間內，就能夠找到 "The Quine Page" 與 Sipser 的證明呢？
張貼留言