In his paper ”The complexity of songs”, Knuth introduced the notion of the space complexity of a song and used it to account for music history. For example, compared to a song whose lyrics must be memorized verbatim, a song with a refrain has its space complexity reduced by a constant factor. To justify the quest for songs with reduced space complexity, Knuth appeals to cognitive science:

It is known [3] that almost all songs of length n require a text of length ~ n. But this puts a considerable space requirement on one’s memory, if many songs are to be learned; hence our ancient ancestors invented the concept of a refrain [14].

Knuth proceeds to give many examples of songs of differing space complexity, including ”m bottles of beer on the wall”, which has space complexity O(log n) because the song of m verses has length n = Θ(m log m) but can be defined in space O(log m). (The “log m” in ”m log m” is because it takes Θ(log m) words to name each m in English.)

There are actually two quantities that can be reasonably called the space complexity of a song. First, there is the length of the shortest program that generates the song, akin to Kolmogorov complexity. In cognitive-science terms, this is the amount of long-term memory needed to store the song for future recall. Second, there is the space required to generate the song, akin to the space complexity of an algorithm. In cognitive-science terms, this is the amount of short-term memory needed to perform the song. For many songs, the long-term and short-term space complexities coincide. This is the case for ”m bottles of beer on the wall”.

Which of the two notions did Knuth have in mind? On one hand, his citation ”[3]” above refers to Chaitin’s paper “On the length of programs for computing finite binary sequences: statistical considerations”. So, I would say long-term. On the other hand, after explaining how ”m bottles of beer on the wall” witnesses that there exist songs of complexity O(log n), Knuth failed to make the obvious further remark that “10^m−1 bottles of beer on the wall” witnesses that there exist songs of (long-term) complexity O(log log n)”. So, I would say short-term.

Below is another set of lyrics with long-term space complexity O(log log n) but short-term space complexity O(log n). I think its use of the A-not-A construction is more natural than restricting bottle counts to numbers of the form 10^m−1, but you may disagree. I’ll leave translation into English as an exercise.

這首歌
是指數成長
不是指數成長？

（指數～指數～～
　成長～成長～～喔～～
　指數～指數～～
　成長～成長～～喔～～）

你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長？

（指數～指數～～
　成長～成長～～喔～～
　指數～指數～～
　成長～成長～～喔～～）

我會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長？

（指數～指數～～
　成長～成長～～喔～～
　指數～指數～～
　成長～成長～～喔～～）

他好奇
我會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不好奇
我會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長？

（指數～指數～～
　成長～成長～～喔～～
　指數～指數～～
　成長～成長～～喔～～）

這是什麼雕像、誰的雕像？西元 2005 年 6 月見於法蘭克福總站屋頂。

What is this sculpture; who are this sculpture? Seen in June 2005 above Frankfurt main station.

坐了這麼多年的飛機，我已經有點不清楚到底去過哪些機場了。以後恐怕越來越享受不到航空旅遊的樂趣了。 After so many years of flying, I am no longer sure exactly which airports I have been to. I’m afraid the joys of air travel will be scarcer in the future.

要是能把去過的火車站也畫成地圖就太好了，不過想必很難。 It would be great if I could also draw a map of all the train stations I have been to. It’s pretty difficult though.

1. 紅蘿蔔刨絲，加上鹽巴、薑末、蒜末、白醋、麻油，在碗中拌勻備用。
2. 同時用湯鍋開始燒開水，準備煮麵。
3. 茴香根切絲。
4. 菜鍋裡熱橄欖油，加茴香根絲炒一兩分鐘，然後轉小火燜。
5. 同時用湯鍋下螺絲麵（即 fusilli，用 campanelle 也不錯）。
6. 趁兩個鍋正在煮的空檔，切蔥（丁或絲）與香菜。
7. 麵快煮熟時，把碗中出的鹽水倒進菜鍋，同時加入白蔥。
8. 麵熟時馬上瀝水，加入菜鍋拌炒，混合其餘材料（青蔥、香菜、紅蘿蔔）即成。

改天來畫個 sequence diagram 吧。

台灣官員使用的邏輯好像比美國法官使用的直覺邏輯更細密一點：不但「互不否認 φ」不一定蘊涵「φ」，而且「互不否認互不否認 φ」也不一定蘊含「互不否認 φ」。直覺邏輯裡 ¬¬¬φ → ¬φ 是定理（證明是 λc.λx.c(λk.kx)），換言之「互不否認」是續繼 monad。

「個人自由以不妨害他人自由為前提。」
「他人自由以不妨害個人自由為前提。」

「警察行使的是公權力，出手打警察就是錯！警察在值勤時受傷，誰來道歉負責？」
「人民行使的是私權利，警察打出手就是錯！民眾在下班時受傷，誰來道歉負責？」

「動員了民眾就得管好，不能以『有宣佈解散』等藉口卸責，無論申請書的動線寫到哪。」
「動員了警察就得管好，不能以『沒下令撤旗』等藉口卸責，無論管制區的界線畫在哪。」

「民眾集結，迫使警察耗資動員、強勢防範，以免因小失大。警察的暴力是被逼出來的！」
「警察集結，迫使民眾耗資動員、強勢防範，以免因小失大。民眾的暴力是被逼出來的！」

「可見台灣人民還不會平和訴求，所以集會遊行應需申請，並提高保證金的門檻。」
「可見台灣政府還不會保障人權，所以警察值勤應需繳械，並進行監視器的攝影。」

「學生的本分就是讀書，更應守法。」
「警察的本分就是挨打，更應守法。」

「警方受到公共監督，所以應可壟斷使用暴力，以維護社會的法治與人民的安全。」
「警方可壟斷使用暴力，所以應受到公共監督，以維護社會的法治與人民的安全。」

「警察行為若涉嫌觸法，大家應靜待司法公訴，民眾不應訴諸暴力。」（但是司法的權力，還不是靠人民的賦予才有所依據嗎？又若狀況緊急，或司法不公呢？）
「民眾行為若涉嫌觸法，大家應靜待司法公訴，警察不應訴諸暴力。」（但是司法的權力，還不是靠警察的執行才有所落實嗎？又若狀況緊急，或司法不公呢？）

紅菜頭用滾水煮過後剝皮剁碎，放回水中繼續用小火煮，並且加入蕃茄的醬 (tomato paste)、切片的洋蔥、鹽、以及少許泰式紅咖哩醬。等到所有原料融為一鍋深紅，再煮沸加入粉絲。小心粉絲超會吸水，不要加太多，不然變成羅宋炒粉絲。約十分鐘後粉絲煮軟，即可撒香菜告成。

我從美國的圖書館借到賴明珠翻譯的《世界末日與冷酷意境》，而 Dylan 則從丹麥的圖書館借到 Alfred Birnbaum 翻譯的 Hard-boiled Wonderland and the End of the World。為什麼兩本書連書名的順序都相反呢？我搞不清楚。難道日文說「張三と李四は依序上車」的意思，是李四先上、張三後上嗎？真傷腦筋。

我也很驚訝，中文譯本看似長篇的一本小說，為什麼譯成英文就縮水成中篇的樣子了？中譯本有 535 頁，英譯本則只有 400 頁，而且內頁本文所占的面積 (typeblock 中文怎麼說？) 差不多，英文的字體還稍大一些。

細看才發現，的確村上春樹的書在英譯過程中常會有所編修 (可能作者本人也有參與)，要不然就是賴明珠成天胡思亂想。試比較：

「胃擴張。」她說。「所以怎麼吃都不會胖。」

「喔。」我感嘆道。「那飯錢可要花不少囉。」事實上她把我連明天中午的飯量都一個人吃完了。

「那當然。」她說。「在外面吃的時候，通常連吃兩家。首先是吃拉麵或餃子輕微暖暖身，然後再正式吃飯。薪水大概都是吃掉的吧。」

… 像用重機關槍掃射倉庫一樣驚人的食慾。我準備吃一星期採購來的食品眼看著就要光了。那些法蘭克福香腸我原來打算用來做美味的 Sauerkraut 酸菜香腸的。

”Gastric dilation,” she confessed. “It doesn’t matter matter how much I eat. I don’t gain weight.”

”Must run up quite a food bill,” I said. Truth was, she’d gastrically dilated her way through tomorrow’s dinner in one go.

”It’s frightening,” she said. “Most of my salary disappears into my stomach.”

… A regular machine gun of a hunger, this girl!

前面這一句 “gastrically dilated her way” 實為妙筆，但是且慢，拉麵呢？餃子呢？酸菜呢？一星期的採購、在外面連吃兩家的美味，就這樣胃擴張掉了，有點可惜。之後還有分段留白等的差異。我個人覺得，比較冗長的中譯本，讀起來比較有味道。可能我的閱讀也有胃擴張的毛病。是不是跟吃素有關。

我對本書結局的解讀，是情勢逆轉、皆大歡喜的好萊塢完結篇。分道揚鑣代表兩個「我」只擦身而過，就像《珈琲時光》裡的電車那樣。有別人看法相同嗎？

(後記：有些地方中譯反而比英譯少了一段。)

為了讓我的 ThinkPad 風扇安靜一點，最近想要把它的 BIOS 升級到最新的版本。因為我的電腦上沒有裝 Windows，只有裝 Linux，所以除非麻煩地重灌 Windows，否則不能使用 IBM 或聯想發佈的 Windows 版 BIOS 升級程式。

以往在 ThinkPad X20 系列的年代，IBM 除了 Windows 版的升級程式以外，還會發佈一張軟碟開機片。也就是我可以下載一個 1.44MB 的檔案，寫到一張軟碟上用來開機。這張軟碟的內容其實是 IBM 用 DOS 拼湊而成的，開機以後 AUTOEXEC.BAT 會自動執行升級程式。就算沒有 ThinkPad 擴充的軟碟機，或手邊沒有空著不用的軟碟（我最近一次看到軟碟好像是馬蓋先的「醜小鴨」那集吧），也可以用 SYSLINUX 的 MEMDISK，直接從下載檔案裡的虛擬軟碟開機。例如我用 GRUB，在 /boot/grub/menu.lst 裡加上一段

title  MEMDISK
kernel (hd0,5)/lib/syslinux/memdisk
initrd (hd0,7)/ccshan/tmp/floppy.img

即可用 /usr/lib/syslinux/memdisk 從 /home/ccshan/tmp/floppy.img 裡的虛擬軟碟開機，因為 (hd0,5) 是我的 /usr 分割區，而 (hd0,7) 是我的 /home 分割區。就算既不用 GRUB 也不用 Linux，也可以用 PXELINUX 從網路上別台電腦上的虛擬軟碟開機進行升級。

現在時代不同了，ThinkPad X60 系列的 BIOS 已經大得軟碟裝不下了，於是 IBM 發佈的開機片不再是軟碟而是光碟。我沒有光碟機，也不想重灌 Windows，所以希望從虛擬光碟開機進行升級，但是事情沒那麼簡單，因為 MEMDISK 只會模擬磁碟，不會模擬光碟。這是因為從光碟開機的過程比從磁碟複雜，要遵從 El Torito 標準進行。IBM 的這張光碟開機片，除了把新的 BIOS 及其更新程式放在一般的 ISO 9660 檔案系統以外，另含一張虛擬的軟碟開機片。當一位有錢擴充 ThinkPad 的用戶，用燒好的實體光碟開機時，ThinkPad 會從實體光碟上載入虛擬軟碟，執行虛擬軟碟上的 DOS。這份 DOS 的 CONFIG.SYS 與 AUTOEXEC.BAT 得先載入實體光碟機的驅動程式，才能讀到前述的 ISO 9660 檔案系統，以執行實體光碟上的 BIOS 更新程式。

我徹夜試驗，發現可以用實體硬碟代替實體光碟，成功升級了我的 BIOS。基本的想法是，在一個實體硬碟的新分割區裡，結合軟碟上的 DOS 開機程式以及光碟上的 BIOS 升級程式。詳情如下。

首先得在實體硬碟裡造一個分割區，如下例 /dev/sda2。這個分割區不用很大，比 IBM 發佈的光碟檔稍大一點就夠了（約 5MB），不過必須位於實體硬碟的前 1024 個磁柱以內（這是 DOS 的限制，迫使我用 gparted 把原本在硬碟最前面的分割區稍微縮小了一點，幸好那只是我的 /usr/local 分割區而已，不很麻煩），而且必須是初選而非邏輯分割區（迫使我用 sfdisk -d 把一個不常用的初選分割區備份然後暫時刪除，升級完再用 sfdisk -uS -N… -O… 小心放回分割表內）。

在分割表裡，這個分割區的型別應設為 6 號（也就是 FAT16 的意思），並且可開機旗標應設為真，因為我們就是要用它開機。但是要把它作成 DOS 的開機分割區，除了新造檔案系統

$ sudo mkdosfs /dev/sda2

以外，還需一番移花接木。我從 IBM 下載的光碟檔名為 7buj25uc.iso，其中內含的虛擬軟碟開機片是從位元組位址 0xA800 (= 43008) 開始的 1.44M (= 1474560) 個位元組。為了方便，我把這部份資料擷取成為另一個檔案 7buj25uc.img。

$ dd if=7buj25uc.iso of=7buj25uc.img skip=43008 count=1474560 bs=1

這兩個數字是我邊用 tweak 查看光碟檔、邊參考 El Torito 標準文件找到的。我早知道的話，也可以用 Joachim Selke 寫好的程式直接擷取。

要能從 /dev/sda2 這個分割區開機，必須把 7buj25uc.img 這張軟碟的內容複製進去，但是有兩點需要注意的地方。第一，不只要複製檔案，還要複製檔案系統最開頭的開機磁區，但是不能蓋掉裡面所謂的 BIOS 參數區塊，因為那裡存有分割區大小等資訊。第二，根目錄裡表列的第一個檔案必須是 IBMBIO.COM，第二個必須是 IBMDOS.COM，不然開機磁區裡的程式會找不到。

開機磁區是檔案系統開頭的 512 個位元組，其中 BIOS 參數區塊佔用的是位址 3 到 62 之間的 59 個位元組，所以我把區塊前的 3 個位元組與區塊後的 450 個位元組分別從軟碟複製到分割區裡。

$ sudo dd bs=1 count=3 if=7buj25uc.img of=/dev/sda2
$ sudo dd bs=1 seek=62 skip=62 count=450 if=7buj25uc.img of=/dev/sda2

然後我把軟碟裡的所有檔案都複製到分割區裡，但是先複製 IBMBIO.COM 與 IBMDOS.COM。（以下指令假設已存兩個空目錄 /mnt/pool 以及 /mnt/loop。）

$ sudo mount -t msdos /dev/sda2 /mnt/pool
$ sudo mount -t msdos -o loop 7buj25uc.img /mnt/loop
$ sudo cp /mnt/loop/ibmbio.com /mnt/pool
$ sudo cp /mnt/loop/ibmdos.com /mnt/pool
$ sudo cp -u /mnt/loop/* /mnt/pool
$ sudo umount /mnt/loop

此時查看 /mnt/pool/config.sys 與 /mnt/pool/autoexec.bat 可以了解，這張虛擬開機片在掛上光碟以後會執行光碟上的另一個 COMMAND.COM。所以我在把光碟內容複製到分割區裡的同時，乾脆用光碟上的 COMMAND.COM 取代軟碟上 DOS 的 COMMAND.COM。

$ sudo mount -o loop 7buj25uc.iso /mnt/loop
$ sudo cp -i /mnt/loop/* /mnt/pool
cp: overwrite `/mnt/pool/COMMAND.COM'? y
$ sudo umount /mnt/loop

最後，我用文字編輯器修改 /mnt/pool/config.sys，把其中的 A: 統統換成 C:（因為要從硬碟而非軟碟開機），並且拿掉呼叫 COMMAND.COM 那一行後面給的參數。

$ vi /mnt/pool/config.sys
$ sudo umount /mnt/pool

大功告成。重新開機以後，請 GRUB 啟動這個新的分割區

root (hd0,1)
makeactive
chainloader +1

即可進入 IBM 的 BIOS 更新程式。

美國航空頒發的金卡、以及美國政府頒發的綠卡，張張都攸關大家在美國的生活。它們就如同深藏不露的礦泉水，讓不肖之徒伺機正中我們飛安的要害，又如同免費提供的行李牌，幫地勤人員千里尋回我們失散的骨肉。在這鳳凰花開、四面驪歌的時節，您是否也在金綠之間猶豫不決呢？與其腳踏兩條船，不如把雞蛋集中以便管理。為方便您睿智的抉擇，記者謹將兩卡的十二優劣點整理如下。

The gold card issued by American Airlines and the green card issued by the American government are each an integral part of our American lives. They are as powerful as the hidden water bottles that strip us of flight safety; they are as handy as the free luggage tags that unite us with abducted children. In this season of blooming Delonix regia and booming Auld Lang Syne, are you also hesitating to choose between gold and green? Decide wisely which basket to put your eggs in, with the help of this 12-point summary of the two cards’ pros and cons.

美國航空金卡 American Airlines gold card		美國政府綠卡 American government green card
✗	其實是塑膠的 Actually plastic	✗	其實是白色的 Actually white
✓	使用 Helvetica 字體印製，中性無襯線 Typeset using Helvetica, a neutral sans-serif typeface	✗	使用 Arial 字體印製，仿製沒水準 Typeset using Arial, a cheap knock-off typeface
✗	附送精美彩色印刷《新會員指南》一本，十二頁無索引 Comes with a guide for new members printed in 12 pages of fine color but without index	✓	附送精美彩色印刷《新移民指南》一本，一百頁附索引 Comes with a guide for new immigrants printed in 100 pages of fine color and with index
✓	有搭機、住宿、購物等多種參加方式 Qualify in a variety of ways: flights, accommodations, shopping, etc.	✓	有就業、依親、投資等多種參加方式 Qualify in a variety of ways: employment, family, investment, etc.
✓	接受會員挑戰，三個月衝刺後拿到身份 Get it in 3 months when you enter a Membership Challenge	✗	要求補送證據，三個月期限後失去身份 Lose it in 3 months when you receive a Request for Evidence
✓	快速通過出境安全檢查 Avoid long security lines at departure	✓	快速通過入境邊防檢查 Avoid long immigration lines at arrival
✓	選位、客服優先 Priority for seats and customer service	▵	謀職、徵兵優先 Priority for jobs and military service
✓	每飛行萬哩，可在網上免費獲取升級證 Earn complimentary upgrades online every 10,000 miles	✓	每居留兩年，可在網上付費申請回美證 Apply for reentry permits online every 2 years
✓	旅館、租車公司等合作夥伴提供優待 Special offers on hotels and cars from partner companies	✓	國家、過境機場等合作夥伴提供優待 Special offers on transit and visas from partner countries
✓	票選傑出空服人員 Vote for great flight attendants	✓	票選傑出校務委員 Vote for great school board members
✓	一年換一張新卡 Renew every year	✓	十年換一張新卡 Renew every decade
✓	在貴賓室裡靜待登機 Lounge while waiting for your flight	✓	在移民監裡靜待入籍 Lounge while waiting for your naturalization