You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

该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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.07.12 02:22:01