Linear Bounded Automata（线性有界自动机）的标记定位相关问题

标准LBA的核心定义限制：磁带初始写入时会在输入串两端固定放置不可修改、不可越过的左右边界标记（通常记为⊣和⊢），读写头的所有操作都只能在两个标记之间的区间内执行。

针对你提出的三个疑问，逐一解答如下：

• 标准LBA模型中，标记必须固定位于输入字符串的两端，左标记紧挨输入第一个字符左侧，右标记紧挨输入最后一个字符右侧，不存在偏移空间。
• 你提到的「标记间距为输入长度的常数倍」属于LBA的等价扩展模型，也常被称为线性空间受限图灵机：该模型允许可用磁带长度为输入长度n的固定常数k倍（k是模型预设参数，和输入无关），这种场景下左右标记不需要完全贴合输入串两端，只要间距不超过kn即可，该模型和标准LBA的计算能力完全等价。
• 不管是标准LBA还是上述等价扩展模型，标记的定位规则都是模型的固定属性，不允许针对每个输入字符串单独动态调整标记位置。如果你需要左标记始终位于输入字符串正前方，直接采用标准LBA的定义即可满足需求，不需要额外调整规则。

内容的提问来源于stack exchange，提问作者insert_clever_username