微客导航 » 文章资讯 » 证明线性有界自动机 LBA ⊂ PSPACE 在 TOC 中？

证明线性有界自动机 LBA ⊂ PSPACE 在 TOC 中？

2023-06-07 15:25:03 438

线性有界自动机(LBA)是图灵机的受限形式，其中输入磁带是有限的。

例子

证明LBA⊂PSPACE

PSPACE是上下文相关语言集的超集。

现在证明LBA=PSPACE，

我们使用磁带缩减空间压缩定理，它指出，

对于每一个k带S(n)空间有界离线图灵机M和常数c>0，存在一个单带cS(n)空间有界离线图灵机N使得L(M)=L(N)。

以下身份适用于-

DSPACE(S(n))=DSPACE(O(S(n)))

和NSPACE(S(n))=NSPACE(O(S(n)))

由于LBA是单带n空间有界图灵机，因此它遵循-

LBA=NSPACE(n)---------------------(1)

现在根据萨维奇定理，如果S是完全空间可构造的并且S(n)>log(n)那么

NSPACE(S(n))⊆DSPACE(S^{2}(n))-------------(2)

最终证明

LBA=NSPACE(n)......by(1)

⊆DSPACE(n^{2})........by(2)

⊂DSPACE(n^{3})........根据空间层次定理

⊆PSPACE

SpaceHierarchy然后需要S(n)它是完全可以空间构建的。