隨機存取圖靈機

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

定義

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

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