Find Busy Beaver values for Prolog programs

Question

The famous Busy Beaver function measures the most complex Turing Machine with a size of n states and m symbols, and that halts. In one version the machine starts with a blank tape and measures the final number of 1's on the tape when it halts. Another version measures the time taken (total number of shifts that occur) before halting. See: Busy Beaver.

Because Prolog is such an expessive language it would be interesting to investigate Busy Beaver Prolog programs. I propose these rules for Prolog programs and query:

The program and query must be pure: they cannot use library or standard predicates, numbers, not or cut.

The measure of the size of the Prolog program plus query is simply the total number of symbols: number of occurrences of predicates, functions, constants and variables.

The measure of the running complexity is the total number of calls when executing the query. The standard procedural semantics of Prolog is used: execute clauses in sequential order and execute subgoals left-to-right. A call means an attempt to match the head of a clause (which may or may not succeed). The program must halt, but whether it succeeds or fails is irrelevant.

So, the Busy Beaver Prolog function BB_Prolog(n) = the maximum number of calls taken by any Prolog program plus query with a size of n symbols, and that halts.

Here is an example of a Prolog program plus query of size 38 symbols (5+10+15+8) that halts after making 213 calls. So, BB_Prolog(38) >= 213. The program computes the Ackermann function using numbers represented by successor (s) and zero (o). The query corresponds to computing Ackermann(4,0) = 13. See Ackermann Function.

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 ).  

With Ackermann(5,0) = 65533 the number of calls is more than 12000000, so BB_Prolog(39) > 12000000.

By investigating some random Prolog programs I discovered that the following program and query with 31 symbols (5+3+18+5) makes 174 calls and halts (with success). So, 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 ) .

Can anyone find larger bounds for BB_Prolog(n), specifically for n = 31, or for other values of n < 39?

Answer 1

This looks like a fun exercise, but we can't work on it without a simple automated, standardized way of counting calls. Tiny counting meta-interpreter:

:- 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).

This disagrees with your counts:

?- 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.

For reference, SWI-Prolog's debugger counts 112 calls for this, so I think my interpreter is closer to a "ground truth" than your count of 213 calls.