以下 6 个子句的“纯”Prolog 程序是否会停止尚不清楚。
:- f(s(s(s(s(s(s(s(s(N)))))))),F), m(S,S,s(F)).
f(o,s(o)).
f(s(N),G) :- f(N,F), m(s(N),F,G).
m(o,_,o).
m(s(X),Y,Z) :- a(Y,P,Z), m(X,Y,P).
a(o,Y,Y).
a(s(X),Y,s(Z)) :- a(X,Y,Z).
它基于与 Brocard 问题相关的猜想，即 n!+1=m^2 仅有 n 的解 < 8.
是否有一个较小的 Prolog 程序，其停止情况未知？
仅允许“纯”Prolog，因此禁止使用库和标准谓词、数字、not 和 cut。
我检查了许多未解决的问题，但找不到相应的较小程序。
是否有一个较小的 Prolog 程序，其停止情况未知？
这一切都取决于您的程序大小指标。如果您只考虑子句（或文字）的数量，但不考虑术语的大小，那么答案是肯定的，有这样的程序。图灵机可以用单个（递归）二进制规则和一个事实进行编码。由于您只对停止感兴趣，因此甚至不需要事实。请参阅这个问题了解编码（的想法）。