1 RAM與 圖靈機

1.1 RAM （random access machine）

• 有限數量的算術寄存器

• 無限數量的內存空間

• 指令集包括：

  • 從寄存器中讀/寫

  • 寄存器上的算術運算

  • 內存地址查詢

1.2 圖靈機可以模擬 RAM

如果一個計算在RAM上需要T(n)步的話，我們可以在圖靈機上使用最多步來模擬它

1.2.1 Church-Turing Thesis

每一個算法多可以用圖靈機來實現之

2 圖靈機的復雜度

2.1時間復雜度

模型： k-tape 確定性圖靈機

        一個圖靈機是T(n) 時間約束的（time bounded），當且僅當 對于每個n，以及每一個有n 尺寸的輸入w，M(w)在T(n)步（T次狀態轉移）后停止

2.2 空間復雜度

模型 “離線”k-tape 圖靈機

        1） tape 只讀

        2）一開始的k個讀寫 tape 是空白的

【類比成考試試卷和答題紙】

        一個圖靈機是S(n)空間約束的（space bounded），當且僅當對于每個n，以及每個有n尺寸的輸入w，M(w)最多需要掃描S(

總結

以上是生活随笔為你收集整理的NTU 课程笔记： PNP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。