隨機存取圖靈機

計算複雜性理論內,隨機存取圖靈機(random-access Turing machines)是一種變版的圖靈機,用來處理大小較小的複雜度類,特別是使用對數時間的複雜度類,像是DLOGTIME以及對數譜系

定義

編輯

在隨機存取圖靈機上,多了一個特殊的指針磁帶,大小是對數空間,字母是二進位單字(0和1)。圖靈機有一個特殊的狀態(state),當指到這個狀態而指針磁帶的數字(二進位)是'p'時,圖靈機會將工作磁帶上面的指針移動到輸入的第p個符號。

這特性讓圖靈機可以直接讀取輸入的特定字母,而不需要花時間去處理整條輸入。這對使用少於線性時間的複雜度類來說,是必要的(因為處理整個輸入的時間是線性時間)。

參考資料

編輯
  • N. Immerman Descriptive complexity (1999 Springer), chapter 5