该6子句纯Prolog程序是否为停机性未知的最小程序?是否存在更小的?
关于停机性未知的最小纯Prolog程序的问询
目前以下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's Problem)**的猜想:仅当n < 8时,n!+1=m²有解。
现正式提出问询:是否存在停机性未知的更小纯Prolog程序?要求如下:
- 仅使用“纯”Prolog
- 禁止使用库、标准谓词、数字、
not及cut
笔者研究过诸多未解决问题,未找到对应更小程序,布罗卡德问题在相关编程竞赛案例中也属最小范畴之一。
编辑说明:判断程序是否停机颇具挑战性,已将示例移至新问题。
内容的提问来源于stack exchange,提问作者Lewis Baxter
相关产品推荐
相关产品推荐

