随机存取图灵机

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

定义 编辑

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

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

参考资料 编辑

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