從程式員的角度來說，大多數程式員對於scratch不感冒，因為這專門給孩子玩的。的確，積木的方式不適合專業程式員寫代碼，程式員也更喜歡敲鍵盤，但其實plc的梯形圖卻也算是此類(電路的原理圖思維上有很大差別，屬於真實電路拓撲，不能算此類)。然而別小看scratch，怎麼說，它也是圖靈完備的。而且，過程 ...
版權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須註明原文網址 http://www.cnblogs.com/Colin-Cai/p/8972752.html 作者：窗戶 QQ：6679072 E-mail：[email protected]
從程式員的角度來說，大多數程式員對於scratch不感冒，因為這專門給孩子玩的。的確，積木的方式不適合專業程式員寫代碼，程式員也更喜歡敲鍵盤，但其實plc的梯形圖卻也算是此類(電路的原理圖思維上有很大差別，屬於真實電路拓撲，不能算此類)。然而別小看scratch，怎麼說，它也是圖靈完備的。而且，過程支持遞歸，雖然帶不了返回值。但是，換個思維，我們完全可以通過變數的方式傳遞返回值。
雖然計算速度會很慢，但是還是可以設計出一個圖靈機。
思路其實也不是那麼麻煩，scatch變數是弱類型的，支持list。雖然理論上，即便scratch沒有這個list也是圖靈完備的，但畢竟要麻煩好多。
我們製作圖靈機，則利用list來放圖靈機的紙帶。圖靈機的各種規則當然也要放list上，規則是{x||x為狀態}、{x|x為紙帶值}、{x||x為狀態}、{x|x為紙帶值}、{左，右}上的一個五元關係，代表著當前狀態、當前紙帶值、將來狀態、將來紙帶值、磁頭方向。為了方便，分5個list來裝。當然，狀態、紙帶值都用0開始的整數來表示就已經可以，左右用01表示。另外，初始狀態為1，接受狀態為1，拒絕狀態為2。
圖靈機的運行並不複雜，這裡不贅述，忘記怎麼運行的請參考https://en.wikipedia.org/wiki/Turing_machine
以下是圖靈機：
輸入圖靈機的參數
設置紙帶的初始值
圖靈機的運行過程
顯示運行結果
點小旗觸發全套動作
哈哈，麻雀雖小，五臟俱全。雖然scratch只是孩子玩的東西，它理論上卻可以實現所有的可運算，很神奇不是嗎？
程式文件下載:
