查找 Prolog 程序的 Busy Beaver 值

Question

著名的 Busy Beaver 函数测量了最复杂的图灵机，其大小为 n 个状态和 m 个符号，然后就停止了。在一个版本中，机器从空白磁带开始，并在停止时测量磁带上最终的 1 数量。另一个版本测量停止之前所花费的时间（发生的轮班总数）。请参阅：忙碌的海狸。

因为 Prolog 是一种非常昂贵的语言，所以研究 Busy Beaver Prolog 程序会很有趣。我为 Prolog 程序和查询提出这些规则：

程序和查询必须是纯粹的：它们不能使用库或标准谓词、数字、not 或 cut。

Prolog 程序加上查询的大小的衡量标准就是符号总数：谓词、函数、常量和变量出现的次数。

运行复杂度的衡量标准是执行查询时的调用总数。使用 Prolog 的标准过程语义：按顺序执行子句并从左到右执行子目标。 call 表示尝试匹配子句的头部（可能会成功，也可能不会成功）。程序必须停止，但成功或失败无关紧要。

因此，Busy Beaver Prolog 函数

BB_Prolog(n)

= 任何 Prolog 程序所进行的最大调用次数加上大小为 n 个符号的查询，然后停止。

这是一个 Prolog 程序的示例，加上大小为 38 个符号 (5+10+15+8) 的查询，该查询在执行以下命令后停止 213电话。所以，

BB_Prolog(38) >= 213

。该程序使用后继 (s) 和零 (o) 表示的数字来计算阿克曼函数。该查询对应于计算 Ackermann(4,0) = 13。请参阅 Ackermann 函数。

a( o,    N,    s(N) ).                                    
a( s(M), o,    A    ) :- a(   M,  s(o), A ).                
a( s(M), s(N), B    ) :- a( s(M), N,    A ), a( M, A, B ).     

:- a( s(s(s(s(o)))), o, X ).  

Ackermann(5,0) = 65533 的调用次数超过 12000000，所以

BB_Prolog(39) > 12000000

。

通过调查一些随机的 Prolog 程序，我发现以下程序和查询 31 个符号 (5+3+18+5) 进行 174 次调用并停止（成功）。所以，

BB_Prolog(31) >= 174

。

p( X,      f(o,o) ).  
p( X,      X      ).   
p( f(X,o), Y      ) :- p( o, Z ), p( Y, o ),  p( f(Y,W), f(Z,X) ).

:- p( f(o,o), o ) .

任何人都可以找到

BB_Prolog(n)

的更大界限，特别是对于 n = 31 或其他 n 值 < 39?

Answer 1

这看起来是一个有趣的练习，但如果没有简单的自动化、标准化的呼叫计数方法，我们就无法完成它。微型计数元解释器：

:- dynamic calls/1.

count_calls(Goal, N) :-
    retractall(calls(_)),
    asserta(calls(0)),
    count_calls(Goal),
    calls(N).

count_calls(true).
count_calls((A, B)) :-
    count_calls(A),
    count_calls(B).
count_calls(Goal) :-
    Goal \= true,
    Goal \= (_, _),
    clause(Goal, Body),
    retract(calls(C)),
    C1 is C + 1,
    asserta(calls(C1)),
    count_calls(Body).

这与你的计数不一致：

?- count_calls(a(s(s(s(s(o)))), o, X), N).
X = s(s(s(s(s(s(s(s(s(s(...)))))))))),
N = 107 ;
false.

作为参考，SWI-Prolog 的调试器对此进行了 112 次调用，因此我认为我的解释器比您的 213 次调用更接近“基本事实”。