※ 引述《alang (活力!!)》之銘言：
: ※ 引述《hotball (哲哲魚)》之銘言：
: : 電腦不是 FSM……是 Turing Machine...
: : 但是這和 C++ 好像沒什麼直接的關係口也……
: 嗯 是沒有甚麼關係 不過能不能解釋一下甚是turing machine
: 我有看到書有寫 可是看不太懂....
啊…………這個嘛………其實很多書都有啦……
不過既然你說看不太懂，那我就非常非常簡單的說一下……
Turing Machine 如果不用數學的方式來說的話，可以看成有一個無限長的帶子，
上面有很多一樣大的格子，格子裡面可以寫字。字的種類可以自己定義，比如說
A ~ Z、或是 1 和 0 等等。另外格子裡面也可以不寫字，即空白。
然後，有一個機器，裡面可以存放一個狀態，狀態的種類也可以自己定義。機器
有一個磁頭，可以在帶子上移動，也可以讀、寫格子裡面的東西。一開始，磁頭
的位置在帶子的最左邊（即開頭）。
機器有一個函數，決定讀到某個字時，要把磁頭往某個方向移動一格（或不移動）
而且把狀態改成「下一個狀態」。
最後，還有兩種狀態，分別是 Qaccept 和 Qreject。當狀態變成 Qaccept 或
Qreject 時，機器就停止運作。且若最後狀態是 Qaccept，則說這個機器
accept 這個字串（就是帶子上寫的字啦！），反之則說 reject 這個字串。
對某個 Turing Machine M，它所可以 accept 的字串的集合，寫成 L(M)，
稱為 M 的 language。
Turing Machine 大致上是這個樣子，當然它的 formal definition 是很數學化的，
也比較嚴謹……不過那比較不容易弄懂……
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: kimicat.m1.ntu.
> -------------------------------------------------------------------------- <
作者: while ('a' == "a") 看板: C_and_CPP
標題: Re: 請教一個 FSM的問題???
時間: Mon Jan 4 23:11:37 1999
※ 引述《hotball (哲哲魚)》之銘言：
: 啊…………這個嘛………其實很多書都有啦……
: 不過既然你說看不太懂，那我就非常非常簡單的說一下……
: Turing Machine 如果不用數學的方式來說的話，可以看成有一個無限長的帶子，
不過事實上來說，
現在的電腦架構也不可能容納無窮的記憶體，
所以將有限記憶體的所有可能狀態，
視為不相同的state，
而將整個電腦視為一fsm亦不為過。
比較有疑問的是電腦所處理的輸入，
如果是由人類所輸入，
那麼和定義中也許會不同。
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ccsun4.ee.ntu.e
> -------------------------------------------------------------------------- <
作者: hotball (哲哲魚) 看板: C_and_CPP
標題: Re: 請教一個 FSM的問題???
時間: Tue Jan 5 01:03:33 1999
※ 引述《while ('a' == "a")》之銘言：
: ※ 引述《hotball (哲哲魚)》之銘言：
: : 啊…………這個嘛………其實很多書都有啦……
: : 不過既然你說看不太懂，那我就非常非常簡單的說一下……
: : Turing Machine 如果不用數學的方式來說的話，可以看成有一個無限長的帶子，
: 不過事實上來說，
: 現在的電腦架構也不可能容納無窮的記憶體，
: 所以將有限記憶體的所有可能狀態，
: 視為不相同的state，
: 而將整個電腦視為一fsm亦不為過。
: 比較有疑問的是電腦所處理的輸入，
: 如果是由人類所輸入，
: 那麼和定義中也許會不同。
其實這個問題就是在 I/O 的地方……不過這其實相當難說，因為人類倒底是什麼樣的
架構並不清楚……上次曾看到新聞說某數學家在發展「實數模型」的計算模型，但是
那很可能根本就無法 implement 出來……
> -------------------------------------------------------------------------- <
作者: while ('a' == "a") 看板: C_and_CPP
標題: Re: 請教一個 FSM的問題???
時間: Tue Jan 5 01:06:51 1999
※ 引述《hotball (哲哲魚)》之銘言：
: 其實這個問題就是在 I/O 的地方……不過這其實相當難說，因為人類倒底是什麼樣的
: 架構並不清楚……上次曾看到新聞說某數學家在發展「實數模型」的計算模型，但是
: 那很可能根本就無法 implement 出來……
純以i/o來說，
tm的i/o不也是開始時就給定的？
另外，在某種程度之內，
電腦的存取可算是random access，
而非turing machine model中那樣sequential式的。
> -------------------------------------------------------------------------- <
作者: hotball (哲哲魚) 看板: C_and_CPP
標題: Re: 請教一個 FSM的問題???
時間: Tue Jan 5 01:51:25 1999
※ 引述《while ('a' == "a")》之銘言：
: ※ 引述《hotball (哲哲魚)》之銘言：
: : Turing machine 也可以做到 random access 吧……
: : 不過這好像不太重要……
: 計算時間/效率時差很多……
當然是差很多，不過也不過是三次方而已……
: : 不過，提到這個 I/O…… FSM 基本上是不能 output 什麼東西的……
: : 算是一個比較簡單的模型……Mealy machine 比較像電腦……
: 把某些state當成有output的話，
: 其實也不是不可以，
: 不過基本定義是沒有沒錯……
提到這個，我一直在想，真實世界中有沒有可能保存一個「實數」呢？
比如說，用一個能量值來保存之類的……不過似乎不太可行，因為測量
時一定會出現誤差。這樣是不是表示計算系統一定會限制在像
Turing Machine 這樣的東西中呢？
如果真的是這樣的話，那人的大腦，是不是也是一種類似 Turing Machine
的東西？
> -------------------------------------------------------------------------- <
作者: while ('a' == "a") 看板: C_and_CPP
標題: Re: 請教一個 FSM的問題???
時間: Tue Jan 5 19:13:48 1999
※ 引述《hotball (哲哲魚)》之銘言：
: 提到這個，我一直在想，真實世界中有沒有可能保存一個「實數」呢？
: 比如說，用一個能量值來保存之類的……不過似乎不太可行，因為測量
: 時一定會出現誤差。這樣是不是表示計算系統一定會限制在像
: Turing Machine 這樣的東西中呢？
您可以參考關於quantum computing方面的東西，
它所使用的bit並不只是零或一而已，
並且宣稱某些問題上exponentially faster than dtm.
雖然目前quantum computing沒有什麼實現的可能，
不過要說未來都不可能成真倒也未必，
但是，在這種模型上設計演算法的觀念和傳統有些差異。
(以上是我看過兩、三篇簡介後大致的了解)
: 如果真的是這樣的話，那人的大腦，是不是也是一種類似 Turing Machine
: 的東西？
基本上我覺得不太像吧。(純感覺就是了)
> -------------------------------------------------------------------------- <
作者: while ('a' == "a") 看板: C_and_CPP
標題: Re: 請教一個 FSM的問題???
時間: Tue Jan 5 23:32:07 1999
※ 引述《hotball (哲哲魚)》之銘言：
: 雖是如此，但是據我所知 quantum computing 似乎主要是為了 handle NPC 問題
: 它好像沒有超過 TM（它應該也不能處理 halting problem 吧？）不過我是不太
: 清楚就是了。
它的計算能力我也不清楚，不過跟據下面這段話
Therefore, there is no possibility of giving a mathematical proof
that quantum Turing machines are more powerful than classical
probabilistic Turing machines (in the unrelativized setting) unless
there is a major breakthrough in complexity theory.(SIAM Journal '97)
也似乎無法否定qtm比tm強的可能性？
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ccsun4.ee.ntu.e