Nan*_*ncy 2 prolog logic-programming subset turing-complete
如果我有一个只包含一个功能符号的逻辑编程子集,我能做什么吗？
我想我不能,但我不确定.如果编程语言是图灵完备语言,它可以做任何用户想要的事情.我被告知这意味着它必须能够执行if..then..else命令,递归和自然数应该被定义.
任何帮助和意见将不胜感激!
在经典谓词逻辑中,公式级别和术语级别之间存在区别.由于n元函数可以表示为(n + 1)个 - 谓词,因此仅限制函数符号的数量不会降低表达性.
在prolog中,公式和术语水平之间没有区别.您可以选择一个n元符号p并尝试通过p的嵌套对图灵机或等效概念(例如递归函数)进行编码.
根据我的直觉,我认为这是不可能的:你基本上可以用变量作为叶子描述n-ary树,但是你可以随时统一这些树.这意味着每个规则头将在递归派生期间匹配,因此您无法表达任何案例区别.不过,这只是一个非正式的论点,而不是一个证据.
PS你可能也对monadic逻辑感兴趣,其中只允许一元谓词.这个一阶逻辑片段是可判定的.