樹莓派、樹莓派之學習、樹莓派之教育

紙張、鉛筆和橡皮擦

??

火山噴發

蘭花草

胡適名言︰

寧鳴而死，不默而生。
要怎麼收穫，先那麼栽。
為學有如金字塔，要能廣大，要能高。
保守永遠是多數，年輕人只管向前衝。

蘭花草
詞︰胡適 曲︰佚名

我從山中來 帶著蘭花草
種在小園中 希望花開早
一日看三回 看得花時過
蘭花卻依然 苞也無一個

轉眼秋天到 移蘭入暖房
朝朝頻顧惜 夜夜不相忘
期待春花開 能將夙愿償
滿庭花簇簇 添得許多香

當『博大精深』遇上『溫文婉約』是否『輾轉反側』？？

飘逸

《2012艾倫．圖靈誕生一百周年》紀念小展

一九三六年艾倫‧圖靈 Alan Turing 發明了一台『 a-machine 』 ── automatic machine ──，這個『自動機器』現今稱作『圖靈機』。一種想像中之長髮飄逸仙女才擁有的『計算』機器，一個能幫助科學家理解『機械運算極限』的工具。

二零壹二年世界各地的計算機學家與數學家，都紀念這個他之『百歲冥壽』，為此舉辦許多學術和展覽之活動，並將此年定為『圖靈年』。

竹簡《孫子兵法》

圍棋

博弈论-囚徒困境

tumblr_inline_mnqztjx5y71qz4rgp

200px-Théorème-de-Brouwer-dim-1.svg

Théorème-de-Brouwer-(cond-2)

《孫子兵法‧始計篇》

孫 子曰：兵者，國之大事，死生之地，存亡之道，不可不察也。故經之以五，校之以計，而索其情：一曰道，二曰天，三曰地，四曰將，五曰法。道者，令民于上同意 者也，可與之死，可與之生，民不詭也。天者，陰陽、寒暑、時制也。地者，高下、遠近、險易、廣狹、死生也。將者，智、信、仁、勇、嚴也。法者，曲制、官 道、主用也。 凡此五者，將莫不聞，知之者勝，不知之者不勝。故校之以計，而索其情。曰：主孰有道，將孰有能，天地孰得，法令孰行，兵眾孰強，士卒孰練，賞罰孰明，吾以 此知勝負矣。將聽吾計，用之必勝，留之；將不聽吾計，用之必敗，去之。計利以聽，乃為之勢，以佐其外。勢者，因利而制權也。兵者，詭道也。故能而示之不 能，用而示之不用，近而示之遠，遠而示之近。利而誘之，亂而取之，實而備之，強而避之，怒而撓之，卑而驕之，佚而勞之，親而離之，攻其不備，出其不意。此 兵家之勝，不可先傳也。夫未戰而廟算勝者，得算多也；未戰而廟算不勝者，得算少也。多算勝，少算不勝，而況無算乎！吾以此觀之，勝負見矣。

從孫子兵法的『廟算』，到圍棋的『對奕』，至於遊戲理論之『策略』，都是一種『計算』，『算計』著一類『輸贏』。荷蘭數學家和哲學家魯伊茲‧艾格博特斯‧楊‧布勞威爾 Luitzen Egbertus Jan Brouwer，一位數學直覺主義學派的創始人，觀察『攪拌的咖啡』之餘說︰任何時刻這杯咖啡，總有一個點是『不動的』。

圖靈百年之後，『計算』並沒有變得更『簡單』，『爆炸』般的『知識』也沒使得『邏輯』推演更加『清晰』。或許那台『仙女計算機』並沒有『使用手冊』？還是她有使用手冊，祇可惜缺少那個伴隨著通過『圖靈測試』之『演算法』的呢？？

拉丁語 tertium non datur 聲稱︰

任何命題 P, \ (P \ \vee \sim P) 必真。

這個叫做『排中律』的概念，有直覺主意的數學家反對，後來還成立了一個『數學建構主義』的流派。這不就是句『空話』的嗎？又何必需要反對？原因在於並非所有的概念都是可以，像『真假』、『是非』與『對錯』般的『二分』，在『黑白』之外不只有『灰』，甚至還有『色』。所以使用排中律一不小心就可能產生『虛假兩難論證』False dilemma。比方說有人論證想反駁『小三之歌』的『沒有拆不散的家庭，只有不努力的小三』︰

假使愛情堅定，無論如何考驗也不會改變；如果愛情不堅定，沒有小三也難長存。只有愛情堅定才會攜手建立家庭，所以再努力的小三也沒有用。

作者不知『堅不堅定』的兩極之間，果真該不該有『其他愛情』的存在？因此無法判斷這個論證對錯是否如此？？而『直覺邏輯者』卻認為應該取消排中律︰

平面上任何一條不自相交連續之『封閉曲線』C，將平面分成『三』個區域，『C 之外或C 之內』之『二分』不包含著『C 之中』，但它不是才是 C 的啊！！

看來仙女早已遠離，那就說說存在的這台『圖靈機』吧！根據『 Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.)』所定義︰

『單磁帶』one-tape 圖靈機是一個有序七元組 M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle ，此處

Q 是一個有限非空的『狀態』 state 集合

\Gamma 是一個有限非空的『磁帶上字母符號』集合

b \in \Gamma 是一個『空白符號』，唯一允許在任意計算步驟中無限次出現在磁帶上的符號

\Sigma\subseteq\Gamma\setminus\{b\} 是不包含空白符號的『輸入符號』集合

q_0 \in Q 是『初始狀態』

F \subseteq Q 是『最終狀態』或稱作『接受狀態』，一般可能有 q_{accept}, q_{reject},q_{HALT}

\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} 是稱作『轉移函式』transition function，其中 L,R 代表『讀寫頭』之向『左，右』移動，還有的增加了『不移動』no shift 的擴張

220px-Maquina

300px-Turing_machine_2b

500px-State_diagram_3_state_busy_beaver_4_

220px-Lego_Turing_Machine

220px-Hopcroft-ullman-old

圖靈機 M 將以下面方式運行：

開 機的時候首先將輸入符號字串 \omega=\omega_0\omega_1\ldots\omega_{n-1} \in \Sigma^* 依序的從左到右填寫在磁帶之第 0, 1, \ldots , n-1 編號的格子上， 將所有其它格子保持空白 ── 即填以空白符 b ──。 然後 M 的讀寫頭指向第 0 號格子，此時 M 處於狀態 q_0。 機器開始執行指令，按照轉移函式 \delta 所描述的規則進行逐步計算。 比方如果當前機器的狀態是 q，讀寫頭所指的格子中的符號是 x， 假使 \delta(q,x) = (q', x', L)， 那麼機器下一步將進入新的狀態 q'， 且將讀寫頭所指的格子中的符號改寫為 x'， 然後把讀寫頭向左移動一個格子。 設使在某一時刻，讀寫頭所指的是第 0 號格子， 然而根據轉移函式它的下一步又將繼續向左移，此時它停在原處不動，也就是說，讀寫頭永遠不會移出了磁帶的左方界限。 設若在某個時刻 M 根據轉移函式進入了某種最終狀態 q_{final}， 則它立刻停機並留下磁帶上的結果字串。由於轉移函式 \delta 是一個部分函式，換句話說對於某些 q,x, \ \delta(q,x) 可能沒有可用的轉移定義， 如果在執行中遇到這種情況，機器依設計約定也將立即 q_{HALT} 停機。

Anthony Morphett 先生用『JavaScript』寫了一個『 Turing machine simulator 』網頁︰

使用方法︰

一、載入某一範例程式，或者在『TM 程式區』自己寫作一個

二、在『初始輸入』Initial input 打入磁帶初始字串

三、按 Run 鍵開機執行，直到它『停機』halt 或者它可能會一直執行，或者說『當機』。按 Stop 鍵打斷執行中的程式。按 Step 鍵可以單步執行。

四、按 Reset 鍵回到初始狀態，可以重新再跑程式。

程式語法︰

程式的每一行是『《當下狀態》《當下符號》《新寫符號》《讀寫頭方向》《新入狀態》』這樣形式的轉移函式。你可以用任何『數字』或是『字母符號』代表《□□狀態》，狀態之命名區分著大小寫的不同。『halt』表示『停機』的『最終狀態』；機器的『初始狀態』稱作狀態『 0 』。你可以用任何『字元符號』代表《○○符號》，符號之命名同樣區分著大小寫的不同，『 _ 』已指定為『空白符號』。讀寫頭方向應該用『 l 』向左、『 r 』向右，以及『 * 』不移動。其次『 ; 』之後的所有符號視為『程式註解』將被忽略。最後當『 * 』被用在《當下符號》或《當下狀態》的時後表示任何『字元』或『狀態』都符合所指；而被用在《新寫符號》或《新入狀態》之時意味著它們『不改變』。

一九三七年艾倫‧圖靈寫下『初始第一例』時說︰

 “A machine can be constructed to compute the sequence 0 1 0 1 0 1…” (0 <blank> 1 <blank> 0…) ( Undecidable p. 119 )

可以使用 Anthony Morphett 的圖靈機模擬器，寫作︰

 ;Turing’s very first example

0 * * * b

b _ 0 r c
c _ * r e
e _ 1 r f
f _ * r b

在『可計算性』computability 的理論中，『窮忙的水獺 』 Busy Beaver 是指在一類符合某種『設計規範』的圖靈機中，停機之前『跑得最久最多步的』或是『輸出最多個非空白符號』的那個『贏家』。這個窮忙的水獺之函數，是一個『不可計算的』noncomputable 函數，下面是一個有著『三個狀態』之窮忙的水獺程式︰

500px-State_diagram_3_state_busy_beaver_2B.svg

State_diagram_3_state_busy_beaver

;3-state busy beaver

0 * * * a

a _ 1 r b
a 1 1 l c
b _ 1 l a
b 1 1 r b
c _ 1 l b
c 1 1 r halt

 

─── 不藉著紙張、鉛筆和橡皮擦，

又怎麼能計算窮忙之水獺的嘗試 ───