last day (15 days later) » 

11:27 AM
Created to discuss the motivations and clarify Question 24894349, about Logic Programming with one function symbol: can it be Turing complete?
 
11:47 AM
It is certainly possible to have a "programming language" with minimal syntax elements (such as a single function symbol) that implements Turing complete computations. The Question asks about this in connection with "logic programming" and seems specifically to ask about Prolog (based on tag).
 
12:13 PM
In the Comments the OP (Nancy) raises the issue of whether the Herbrand universe is "limited". The Herbrand universe corresponds to all the terms of a first-order language that can be constructed from constants and function symbols. If the language contains no constant symbols (perhaps as intended here), then an arbitrary constant symbol may be added.
While such a Herbrand universe may be limited in its construction to one function symbol (and one arbitrary constant), it will still be infinite. For a nice introduction to the topic of Herbrand models in the context of Prolog & logic programming, see this blog post from 2012.
 
12:42 PM
So to clarify the Question, are we assuming that we start from a standard Prolog language with lists, or from some more limited programming language that has only one "function symbol", perhaps a functor of two arguments?
If the latter, then one immediate difficulty is that Prolog rules are rules for predicates, so how would we express rules without at least one predicate symbol to write rules for?
If there is the ability to write rules for a predicate, then it seems attractive to implement Rule 110 for cellular automata as a Prolog predicate, which is known to be Turing complete.
 
 
4 hours later…
5:08 PM
Perhaps I've given Nancy too much to think about, but the Question should either be clarified or closed, given that the request for clarification above has been outlined.
 
6:06 PM
I'm not sure if reasoning over the herbrand universe helps, exactly because you add the constant. With a unary successor function and a zero constant, it shouldn't be too hard to encode the recursive functions making you turing complete.
Btw it is clear that lists are not allowed, since they are represented by a binary cons (.) and the empty list ([]).
 
6:30 PM
Yes, it seems that one needs, if not a constant, then at least a builtin var/1 to identify ground terms (free variables), in order to have a base case rule to terminate a successful call.
 
 
4 hours later…
10:46 PM
yes, but var/1 extends your language anyway, so you don't run into problems anymore
 

  last day (15 days later) »