Re: [問卦] 真的可以使用0和1寫程式的八卦嗎?

作者: roger29 (想不到)   2015-08-17 11:53:31
完全只用0和1理論上應該是可以,不過應該還要經過不少轉換會很麻煩的吧,
但是用一些數字來寫程式倒是可以的,這其實就是一個Turing Machine(圖靈機)啊,
但是要用圖靈機來寫程式非常困難,一個簡單的指令實作可能要幾十甚至幾百行,
既然這樣為什麼不去寫寫C或是Python之類的玩玩就好勒?
一個標準的圖靈機是由硬體和軟體兩大部分所組成的,
硬體的部分就是一段理想上是無限長一格一格的記錄帶,一個記錄格可以放一個symbol。
還有一個讀寫頭,每一次讀寫頭可以讀取某格上的symbol,
還可以把這個symbol替換成別的並且選擇移動方向(左右或不動)。
軟體就是程式的部分啦,一個圖靈機的指令大致上這樣:
{current state}{current symbol}{new symbol}{movement}{new state}
一開始圖靈機都是從state 0開始,而還沒執行程式前你記錄帶上的東西就是你的input。
所以你下一個指令假如是這樣:
0 _ 1 R 0
這個指令做的事就是若你的state為0且讀寫頭指向的記錄格為空(_),
則將此記錄格填入new symbol也就是1,接著往右移動一格(R),
跳到新的state(還是0)。
所以應該很多人知道這一行指令碼會讓圖靈機做什麼了,
他會一直往右寫1寫下去,所以執行之後你的記錄帶看起來大概是這樣:
..._ _ _ _ _ _ _ _ _ 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

讀寫頭起點
只要寫一個1的話,也很簡單,只要把上面那一行改成
0 _ 1 R 1
就可以了,這一行和上面那行的差別只在new state原本是0現在是1,
當第一個記錄格被寫入1之後,它會跳到state 1,
但由於state 1我們沒有相對應的代碼,所以這個程式就停止了(halt)。
像上面這樣,一些更複雜的動作可以也可以用多行指令碼來實作,
不過好像還沒看到怎麼用數字寫程式,
其實只要做一個很直觀的mapping,就可以把上面一行的五個符號對應成數字了。
state:原本就是數字(0 1 2...)
symbol:假設是two-symbol的話,就是0(代表空白)和1。
movement:往左=0,往右=1,不動=2。
類似這樣,就可以把0 _ 1 R 1改成00111,
雖然這樣不是只用0和1來寫,但是再經過幾個去轉換,
也是可以轉成真的只用二進為來表示這段指令碼。
比如先把00111用某種方式轉成十進位的一個自然數,在把這個自然數用二進位表示這樣。
不過大概想一下就知道,用這種方法寫程式非常非常沒有效率,
介紹一個網站: http://morphett.info/turing/turing.html
這是一個圖靈機simulator,即你可以在這裡寫你的圖靈機代碼並用這個模擬器跑,
google搜尋Turing machine simulator也有其他類似的可以玩。
下面這段指令碼拿去是把一串k個1的input變成2k個1的指令,就相當於是乘以2的動作,
0 1 2 r 1
1 1 1 r 1
1 _ 3 l 2
2 1 1 l 2
2 3 3 l 2
2 2 1 r 3
3 3 1 * 5
3 1 2 r 4
4 1 1 r 4
4 3 3 r 4
4 _ 1 l 2
有興趣可以複製這指令碼去跑跑看,假如你初始是111,跑完就會變成111111這樣。
實作一個乘以2的指令碼就這麼複雜而且不直觀,沒事幹麻用這玩意寫程式?
然後這段可以改寫成一大堆數字:
0121111111103122111223312221133312531214411144331440112
不過既然圖靈機要實作這麼麻煩,圖靈機還有啥用勒?
舉例來說,圖靈機有一個優點就是它的架構非常簡單(相比於我們用的電腦),
但是我們可以拿圖靈機來驗證很多東西,藉此知道某些我們電腦的限制,
比如一個natural number to natural number的function能不能用電腦計算出來?
若圖靈機可以,我們的電腦就可以,反之則不行,
而從圖靈機去驗證容易的多,因為它的架構非常簡單,類似這種情形。
※ 引述《WeiMyWoW (...)》之銘言:
: 很久以前,那還是我用win98的時候有次我系統崩潰了,
: 因為我是電腦白吃,我朋友給我介紹了一個高手來幫我修電
: 腦。
:   
:   他看了一下電腦,問我有沒有98的光碟,我說沒有。
:   
:   他想了一下,叫我把固定電話拿給他,我想修電腦要電
: 話幹什麼,但人家是高手,我也不好說什麼,就把電話拔下
: 來給他了。
:   
:   他把電話線空著的一頭接在電腦的一個插孔內,然後進
: 入了dos,然後就開始在電話上不停的按著鍵,他按鍵的速度
: 非常快,但是只按0,1兩個鍵,我搞不懂這有什麼用,但也
: 不敢問,看了半個多小時,他還是不停的按這兩個鍵,我漸
: 漸的有些睏,我問他這東西要搞多久,他說要幾個小時,我
: 給他倒了杯茶,就一個人去隔壁睡覺了。
:   
:   醒來的時候,一看已經過了4個多小時,我起身到隔壁,
: 看見他正在98裡面調試,過了一會兒,他說,你試試,我坐
: 上椅子用了一下,真的好了,我當時也不懂電腦,謝過人
: 家就走了。
:   
:   後來我慢慢對電腦有了瞭解,終於瞭解,原來當時那位
: 高手是用機器語言編了一個98系統,我後來問我朋友那位高
: 手的下落,我朋友說前幾年去了美國之後,杳無音訊....
:  
: 是說電子訊號本來就是高電位和低電位組成,也就是0和1,但真的可以拿來寫程式嗎?
作者: EinArthur (雷姆好可愛喔雷姆)   2015-08-17 11:54:00
嗯嗯我也是這麼想ㄉ
作者: p72910 (總是有刁民想害朕)   2015-08-17 11:55:00
就是finite state machine啊 這麼簡單還講這麼多
作者: lainhoter   2015-08-17 11:55:00
我在教計算理論也是這樣跟學生說,不過你有個字錯了
作者: LFD (壞掉的LED)   2015-08-17 11:57:00
我看到原文的版本是有人拿針在光碟片上面戳
作者: leobear (雷歐)   2015-08-17 11:57:00
喔喔
作者: kopune (無限期支持 i☆Ris)   2015-08-17 11:57:00
你是 零一系?
作者: saiya (台南中肯伯)   2015-08-17 11:59:00
你是 零一士 ?
作者: chadhsieh (謝老闆)   2015-08-17 12:00:00
以前的打孔機不就是這樣?
作者: arbwen ( )   2015-08-17 12:00:00
請問一下 常看電影演電話拿起來用個奇怪哨子吹一聲再按鍵那個奇怪哨子吹一下個作用是什麼呀?
作者: vn509942 (如履薄冰)   2015-08-17 12:02:00
寫程式 程式卡上打洞
作者: ymx3xc (U文多多)   2015-08-17 12:03:00
恩恩恩
作者: cena59473 (感謝小狗)   2015-08-17 12:05:00
推你
作者: locklose (允)   2015-08-17 12:07:00
吹笛子應該是要特殊頻率,電話撥號聲本身就是用頻率控制科南還有一集就是人聲撥號這樣
作者: philxiao (Sting)   2015-08-17 12:09:00
補充一個有趣的程式語言:Whitespacehttps://zh.wikipedia.org/wiki/Whitespace不是用01寫,而更有趣--看起來是一片空白!!但是能跑!!

Links booklink

Contact Us: admin [ a t ] ucptt.com