数据模拟计算类？

Question

数据录不是图灵完整的。

但是它的计算类是什么？

它是否等同于有限状态机或下推机 (即上下文无关).还是介于两者之间？

Answer 1

让我们假设我们可以访问以下谓词，无论是内置的还是用语言定义的：

Head(x, y) iff y is a list and x is the first element in the list
Tail(x, y) iff x and y are lists and x is the same as y but is missing y's first element
Equal(x, y) iff x and y are the the same thing

首先，我认为很明显，这种语言可以接受所有的常规语言。根据Myhill-Nerode定理，正则语言的最小DFA中的所有状态都对应于不可分辨关系下的唯一等价类。似乎每个等效类/状态都有一个谓词来表示与输入字符串对应的列表是否属于该类，然后只有当与接受状态对应的谓词之一为真时，另一个谓词才是正确的。因此，对于具有偶数a和奇数b的语言{a，b}，最小DFA有四种状态：

 O
 |
 V
q0<---a--->q1
 ^          ^
 |          |
 b          b
 |          |
 V          V
q2<---a--->q3

在这里，q2是唯一的接受状态。我们的DataLog程序看起来可能如下：

Q0(()).
Q0(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q1(z).
Q0(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q2(z).
Q1(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q0(z).
Q1(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q3(z).
Q2(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q3(z).
Q2(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q0(z).
Q3(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q2(z).
Q3(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q1(z).
EvenAOddB(x) :- Q2(x).

基于这个例子，我认为很明显，我们总是可以以这种方式编码转换，因此任何常规语言都可以被接受。因此，DataLog至少和确定性有限自动机一样强大。

我们可以定义如下：

// Last(x, y) iff x is the last element of y
Last(x, y) :- Head(x, y), Tail(z, y), Equal(z, ()).

// AllButLast(x, y) iff x and y are the same list but x is missing the last element of y
AllButLast((), (x)).
AllButLast(x, y) :- Head(w, x), Head(z, y), Equal(w, z),
                    Tail(w', x), Tail(z', y), AllButLast(w', z').

现在，我们可以识别上下文无关语言a^n b^n中对应于字符串的列表：

// ANBN(x) iff x is a list beginning with n 'a's followed by n 'b's
ANBN(()).
ANBN(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x),
           Last(w, z), Equal(w, 'b'), AllButLast(z', z),
           ANBN(z').

很容易调整谓词以找到偶数回文的语言，从那里很容易找到所有回文的语言。我相信我们也可以接受一些语言，如平衡括号等。基于这一经验，我猜想我们可以接受所有的上下文无关语言。

我们能得到一种上下文敏感的语言吗？让我们尝试一下a^n ^n^n。如果我们假设DataLog为整数类型内置了如下谓词：

Zero(x) iff x is equal to zero
Successor(x, y) iff x and y are integers and x = y + 1

我认为我们可以这样做：

ANBNCN(()).
ANBNCN(x) :- Zero(y), ANBNCNZ(x, y).

ANBNCNZ(x, y) :- BN(x, y).
ANBNCNZ(x, y) :- Head(w, x), Equal(w, 'a'),
                 Last(z, x), Equal(z, 'c'),
                 Tail(u, x), AllButLast(v, u),
                 Successor(r, y), ANBNCNZ(v, r).

BN(x, y) :- Head(w, x), Equal(w, 'b'),
            Successor(y, z), Tail(u, x),
            BN(u, z).

以上所述如下：

• 空字符串位于a^n b^n c^n中。
• 否则，如果f(s，0)为真，则字符串位于a^n ^n^n中。
• 如果s只包含'b‘的n个实例，则f(s，n)为真。
• f(s，n)为真，如果s以a开头，以c结尾，f(s'，n+ 1)对中间的所有事物都是真的。

这应该有效，因为f(s，n)的每一次递归调用都会从末端剥离一个a和一个c，并记住它计算了多少。然后，一旦所有的a和c都消失了，它就会计算出b的许多实例。

基于这一点，我的感觉是，我们可能也可以做一些或所有对上下文敏感的语言。也许，缺乏无界执行正是线性有界自动机(短语结构语法中的生成必须不超过LHS)与一般无限制文法(其中间形式可以任意增长和缩小)的区别。