随机存取图灵机

在计算复杂性理论内，随机存取图灵机(random-access Turing machines)是一种变版的图灵机，用来处理大小较小的复杂度类，特别是使用对数时间的复杂度类，像是DLOGTIME以及对数谱系。

定义

在随机存取图灵机上，多了一个特殊的指针磁带，大小是对数空间，字母是二进制单字(0和1)。图灵机有一个特殊的状态(state)，当指到这个状态而指针磁带的数字(二进制)是'p'时，图灵机会将工作磁带上面的指针移动到输入的第p个符号。

这特性让图灵机可以直接读取输入的特定字母，而不需要花时间去处理整条输入。这对使用少于线性时间的复杂度类来说，是必要的(因为处理整个输入的时间是线性时间)。