🚀 go-pugleaf

In article <3594@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes:
>Could you write an interpreter for Horn clause logic programming
>(which is semi-decidable) as a primitive recursive function?
>
>On the otherhand, if you view primitive recursive functions
>as adequate for general programming, you _could_ reply that
>a Prolog interpreter is not of real interest!  :-)
>
>	Frank Silbermann	fs@rex.cs.tulane.edu

How about a function F_k: HCLWFF -> {T,F, TimedOut}
where for horn clause wff P, F_k(P)= TimeOut if
the algorithm does not conclude within j**j**j**j ...
                                          k exponentiations
steps, where j is the length of P and k is a parameter bounding
the length. For decent sized k, 
F_k(P) = TimedOut means that P is not feasibly decidable using this
algorithm. Note that "steps" is a flexible notion here, and could include
quite non-trivial computation. Is there a reason why such a function is
significantly less useful than a partial function?