输入只读的 Turing 机

阐述

是一种 Turing 机，但输入的纸带具有固定长度且为只读的；还有另一个工作纸带可以读写，只有该纸带上的空间算作它的空间复杂度。

显然，对于至少为线性的空间复杂度类，它与普通的 Turing 机是等价的，因此我们只会在用次线性的情况下使用这个模型。

组态

由于输入纸带是不变的，它的组态只包含

• 状态
• 工作纸带的内容
• 输入纸带和工作纸带上的读写头

这样，如果空间复杂度为 $f(n)$，则组态的数量为 $n2^{O(f(n))}$。

实例

L 复杂度类和 NL 复杂度类都用到这个模型。

性质

相关内容

参考文献