2009年6月13日星期六

Turing Machine

Automata這一科終於學完了
總結自己從automata中學到的,主要就是TM
學TM之前的DFA、PDA都只是TM的基礎
它們的用途不大
而TM是現代的Computer的理論模型
兩者也是很相似的

TM是讀取Tape上的input,進行一些操作
然後Tape上的symbol就是output
這和電腦的硬件設計差不多
首先Program會載入到RAM裹面,包括所有instructions和data
然後電腦會讀取RAM裹面的instruction,產生一個output
並存放在RAM裹面
………………………………
所以TM的限制也是Computer的限制
TM不能模擬另一個TM的功能
電腦也是一樣的
但現在有很多虛擬機軟件,可以很好的模擬另一台電腦
同時有一大堆模擬器,可以玩NDS、GBA等主機的游戲
不是說TM不能模擬另一個TM嗎?

據說現在的虛擬機軟件,其實是一種特殊的算法
它有一定的概率可以得出正確的結果
但並不能保證100﹪可以運行
如果虛擬機裹跑的OS出了問題,整個虛擬機都會掛掉的
或者因為我們都能接受這個限制,所以就把虛擬機當成普通軟件吧
發佈留言

熱門文章