寻找Prolog程序的Busy Beaver函数值，求n<39的更大下界

著名的忙碌海狸函数用于衡量n状态m符号的停机图灵机的最大复杂度：一种版本以空白带启动，统计停机时磁带上最终的1的数量；另一种版本统计停机前的总移位次数。

由于Prolog表达能力极强，研究忙碌海狸风格的Prolog程序颇具意义。为此制定以下Prolog程序及查询规则：

• 程序与查询必须是纯Prolog：不得使用库、标准谓词、数字、not或cut。
• 程序加查询的大小以总符号数计量：包括谓词、函数、常量及变量的出现次数。
• 运行复杂度以执行查询时的总调用次数计量。采用Prolog标准过程语义：按顺序执行子句，从左到右执行子目标。一次调用指尝试匹配子句头部（无论成功或失败）。程序必须能停机，成功或失败均可。

据此，Prolog版忙碌海狸函数BB_Prolog(n)定义为：所有大小为n符号且能停机的Prolog程序加查询的最大调用次数。

示例1：大小38符号的Ackermann程序 #

以下是总符号数为38（5+10+15+8）的Prolog程序加查询，执行213次调用后停机，因此BB_Prolog(38) >= 213。该程序用后继函数（s）和零（o）表示数字，计算Ackermann函数，查询对应计算Ackermann(4,0)=13。

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。

示例2：大小31符号的随机程序 #

通过研究随机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的情况。

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