4

The Wikipedia section on this topic is a mess. It states:

Pure Prolog is based on a subset of first-order predicate logic, Horn clauses, which is Turing-complete. Turing completeness of Prolog can be shown by using it to simulate a Turing machine:

(emphasis added)

And then it goes on to show code that uses things that are not Horn clauses (! and once):

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
 
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

OK, so Prolog is Turing-complete. No one doubted that. What about pure Prolog?

If pure Prolog is, in fact, Turing-complete, how come we seemingly can't implement list intersection (the first list filtered by membership in the second list) in it? All implementations use at least one of the following: !, \+, findall, call directly or indirectly.

MWB
  • 11,740
  • 6
  • 46
  • 91
  • Added an implementation for "intersect" to my sidebar-like answer. What's missing? – David Tonhofer Dec 18 '20 at 11:45
  • If I understand the code in your question correctly, it interprets a *nondeterministic* Turing machine and *incorrectly cuts away correct executions*. A mess indeed. But given a *deterministic* Turing machine, the code without `!` and `once` would be pure and correct. With a *nondeterministic* Turing machine, the code without `!` and `once` would be pure and *more correct than now* since it would explore all possible executions. This shows that pure Prolog is Turing complete, both for deterministic and nondeterministic machines. – Isabelle Newbie Dec 18 '20 at 11:51
  • @IsabelleNewbie Sidenote: This is certainly clear, but still: there is a qualitative difference between the nondeterminism of Prolog and the nondeterminism of the TM. In cut-less Prolog, "nondeterminism" means "I will be back later, the state is on the stack and I can roll back the entire store of variable contents". For the TM, "nondeterminism" means "choose any of the several possible next states, at random" (which raises the question where those random selection comes from). That's like doing a `random_between(1,N,Choice)` for the `N` next possible clauses, then cutting. No going back. – David Tonhofer Dec 18 '20 at 12:10
  • Depending on taste, one may also consider the nondeterministic TM to branch off into `N` Everettian universes (and in each universe, it commits) in order to be able to accept a problem in NP in polynomial time... – David Tonhofer Dec 18 '20 at 12:13
  • 1
    I've never seen nondeterministic automata described as *requiring* randomization. Rather, semantics is usually "there exists *some* path leading to an accepting state". That is certainly something that Prolog can determine. And more, since it can (within limits of fairness) enumerate all possible ones. – Isabelle Newbie Dec 18 '20 at 13:02
  • @IsabelleNewbie Are you suggesting replacing `once(rule(...))` with `rule(...)` and removing the line containing `!`? – MWB Dec 18 '20 at 13:10
  • Yes. If you remove those the test from the Wikipedia page still succeeds exactly once with the same answer, the only difference is that it leaves a choice point. Also I realize now that the example Turing machine isn't nondeterministic after all (I don't know why I misread it before), so some of the above is moot. But most of it still stands. – Isabelle Newbie Dec 18 '20 at 14:17
  • @IsabelleNewbie "I've never seen nondeterministic automata described as requiring randomization" That's right, but it always felt like some ontological blind spot to me. "there exists some path leading to an accepting state" yeah but that path is never recorded nor is it backtracked over. Nor is properly constructed or selected. It's just some magical path through the Everett multiverse. It exists. Okay.‍♀️ – David Tonhofer Dec 18 '20 at 21:20

3 Answers3

4

how come we seemingly can't implement list intersection (the first list filtered by membership in the second list) in it? All implementations use at least one of the following: !, \+, findall, call directly or indirectly.

Please note that the answer using if_/3 does not need any cut at all. The cut (or if-then-else) is here merely for performance and robustness reasons (that is to catch determinate cases and to signal errors in case of unintended use). You can expand it all to a version without any such constructs. It will terminate the same way, but be less efficient in current implementations.

Here are the purified versions of if_/3 and (=)/3:

if_(If_1, Then_0, Else_0) :-
   call(If_1, T),
   (  T = true, call(Then_0)
   ;  T = false, call(Else_0)
   %;  nonvar(T) -> throw(error(type_error(boolean,T),_))
   %;  /* var(T) */ throw(error(instantiation_error,_))
   ).

=(X, X, true).
=(X, Y, false) :-
   dif(X,Y).

And, in case you do not accept the call/2 and call/1 (after all both are not part of first order logic), you would have to expand each use accordingly. In other words, all uses of if_/3 are such that such an expansion is possible.

As for Turing completeness, this is already established using a single rule. See this question and the references contained therein how this is possible (it is really not that intuitive).

false
  • 10,264
  • 13
  • 101
  • 209
  • 1
    Can you post a logically pure version of `if_/3`? – MWB Dec 18 '20 at 20:15
  • OK, `call` is pure in HiLog at least. – MWB Dec 18 '20 at 20:22
  • @MaxB: See above. – false Dec 18 '20 at 20:26
  • Looks like you are also using the inequality (inside `dif`), like David's answer, which is technically non-Horn (see comments under it). – MWB Dec 18 '20 at 20:33
  • @MaxB: Without dif/2 ( or at least [iso_dif/2](https://stackoverflow.com/a/20238931/772868) ) it is impossible to do anything useful. Note that `dif/2` was present in the very first Prolog (dubbed Prolog 0), it later got removed... – false Dec 18 '20 at 20:43
  • *"Without dif/2 ( or at least iso_dif/2 ) it is impossible to do anything useful."* Can you implement the Turing machine without it? :-) – MWB Dec 18 '20 at 20:45
  • @MaxB: Yes, you can implement a Turing machine without dif/2. But you cannot even implement intersection or similar predicates. – false Dec 18 '20 at 20:47
  • _"As for Turing completeness, this is already established using a single rule."_ I **knew** it! And they called me crazy! – David Tonhofer Dec 18 '20 at 21:14
  • @false Maybe make (\=)/2 horn? Is this possible with a finite set of clauses? –  Dec 18 '20 at 21:14
  • @DavidTonhofer: Did you invent/discover that encoding yourself? I found it most puzzling. And still am. – false Dec 18 '20 at 22:21
  • @false No invention. But I had a hunch that something like that might be possible, I need to read this. – David Tonhofer Dec 19 '20 at 09:37
  • ... it looks like Prologers use a different notion of 'purity' than Hornness. – MWB Dec 19 '20 at 10:26
  • @MaxB: Would you consider CLP(B) or CLP(Z) not pure? – false Dec 19 '20 at 16:12
  • Depends on your definition. Wikipedia (quoted in the Q) defines "purity" as being Horn. – MWB Dec 19 '20 at 17:01
  • @MaxB: It depends on your intention. What is the motivation to insist on Horn only except for a purely historical perspective? Since Phillipe Roussel's Thesis of May 1972 (that is a month or two prior to Prolog's inception) there has been dif/2 (originally =. that is, equals sign with a dot below). – false Dec 19 '20 at 17:29
  • *"Yes, you can implement a Turing machine without dif/2. But you cannot even implement intersection or similar predicates."* -- to avoid extended discussions in the comments, I'm posting a [new question](https://stackoverflow.com/questions/65425800/). – MWB Dec 23 '20 at 14:20
2

You can build a Turing Machine with your language, whereby the current tape and inner state are represented as "accumulator terms". It's just that you cannot use the "!" to commit to a selected clause for an essentially deterministic "proof", so a real implementation would be laden with ever-growing stack (that will never be visited again) in addition to growing terms. But in the Turing Universe, space is free, time is infinite and thermodynamically usable energy is abundant (plus there is a big heat sink around). No worries!

Actually a nice exercise to build Marvin Minsky's minimal Universal Turing Machine in pure Prolog.

Edit: How about this implementation of "intersect". What's missing?

% horn_intersect(++List1,++List2,?List3)
% List3 is the intersection of List1 and List2
% Assumptions: 
% 1) All the members of List1, List2, List3 are grounded
%    No unbound variables (a non-logical concept)
% 2) We don't care about determinism. The same solution
%    may be generated several times (as long as it's right)
%    Choicepoints are not removed.
% 3) There is a dataflow direction: (List1,List2) --> List3.
%    This also ensures that this is a function (only one solution,
%    though represented by a set of equivalent solutions)
%    These are not foreseen:
%    Going the other ways (List1,List3) --> "an infinite set of List2 templates"
%    Going the other ways (List2,Listd) --> "an infinite set of List1 templates"
%    Going the other ways List3         --> "an infinite set of (List1,List2) templates tuples"
%    However, accepting a (List1,List2,List3) is ok.

horn_intersect([],_,[]).
horn_intersect(_,[],[]).

horn_intersect([X|Xs],List2,[X|Ms]) :- in(X,List2),horn_intersect(Xs,List2,Ms).
horn_intersect([X|Xs],List2,Ms)     :- not_in(X,List2),horn_intersect(Xs,List2,Ms).

in(X,[X|_]).
in(X,[K|Ms]) :- X\=K,in(X,Ms).

not_in(_,[]).
not_in(X,[K|Ms]) :- X\=K,not_in(X,Ms).

:- begin_tests(horn_horn_intersect).

test(1,[true,nondet])           :- horn_intersect([a,b,c],[a,b,c],[a,b,c]).
test(2,[true,nondet])           :- horn_intersect([b],[a,b,c],[b]).
test(3,[true,nondet])           :- horn_intersect([a,b,c],[b],[b]).
test(4,[true,nondet])           :- horn_intersect([a,b,c],[],[]).
test(5,[true,nondet])           :- horn_intersect([],[a,b,c],[]).
test(6,[true,nondet])           :- horn_intersect([x,y],[a,b],[]).
test(7,fail)                    :- horn_intersect([x,y],[a,b],[u,v]).
test(8,[Out == [], nondet])     :- horn_intersect([x,y],[a,b],Out).
test(9,[Out == [a,b], nondet])  :- horn_intersect([a,b,c],[a,b],Out).
test(10,[Out == [a,b], nondet]) :- horn_intersect([a,b],[a,b,c],Out).
test(11,[Out == [], nondet])    :- horn_intersect([x,y],[a,b],Out).
   
:- end_tests(horn_horn_intersect).
David Tonhofer
  • 14,559
  • 5
  • 55
  • 51
  • 1
    I'm just editing my Q to include a reference to that .... – MWB Dec 18 '20 at 09:58
  • Yours is probably the most declarative `intersection` I've ever seen! Although strictly speaking `\=` is not in FOL ([only = is](https://en.wikipedia.org/wiki/First-order_logic#Logical_symbols)), so its negation makes the clause non-Horn, I suspect that adding `\=` still keeps the language declarative. – MWB Dec 18 '20 at 12:00
  • 1
    @MaxB negation is in first order logic, so if equality is (and it isn't necessarily!), then so is the negation of equality. The more interesting question is whether `\=` always has the same semantics as in first order logic. The most interesting question is: If we can express a Turing machine without negation, why can't we express list intersection without it? – Isabelle Newbie Dec 18 '20 at 13:05
  • @IsabelleNewbie My point is that using negation in the body of a definite clause makes it non-Horn. `\=` is not part of the syntax of FOL (see link) – MWB Dec 18 '20 at 13:07
  • Right, I get your point now about non-Hornness. I still think that the question of expressing intersection without negation is the most interesting part of this puzzle. – Isabelle Newbie Dec 18 '20 at 14:18
  • @IsabelleNewbie You could do it if you had a database of the allowed domains of the list elements. Then you just enumerate the list elements via that domain, and retain those for which equality triggers in both input lists. This is also the only sane way to implement `p(X) :- \+ q(X)` ... `p(X)` has to spit out the `X` from some domain for which `\+ q(X)`. – David Tonhofer Dec 18 '20 at 21:13
0

If you enconde states as Peano numbers, and use 0 for halt.
And s(X) for all non-halt states. Then you dont need a cut:

perform(0, Ls, Ls, Rs, Rs).
perform(s(Q0), Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    rule(s(Q0), Sym, Q1, NewSym, Action),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

But you could also show "Computational Completeness" by way of showing
that pure Prolog can do µ-recursion inside Peano numbers.