Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Prolog and Turing-Completeness

24 views
Skip to first unread message

Timothy S Meyer

unread,
May 3, 1993, 2:44:41 PM5/3/93
to
I've read in several places where Horn clause programming is Turing-
complete. Is Prolog programming Turing-complete? By Prolog programming
I mean definite Horn clause programming with exactly one clause having no
positive literal (which represents the goal). Am I right in phrasing this
question?

Lars-Henrik Eriksson

unread,
May 4, 1993, 3:44:08 AM5/4/93
to
In article <10...@blue.cis.pitt.edu> mey...@pitt.edu (Timothy S Meyer) writes:
I've read in several places where Horn clause programming is Turing-
complete. Is Prolog programming Turing-complete? By Prolog programming
I mean definite Horn clause programming with exactly one clause having no
positive literal (which represents the goal).

The short answer is: yes.

Am I right in phrasing this question?

I don't know. I would have thought it so obvious that Prolog, being a
general purpose programming language, is Turing-complete that it is
possible that we mean different things.

Anyway, the FUN answer:

Given a TM with a transition table where the entries have the form:

<state, symbol, newstate, newsymbol, movement>

meaning, as usual, that if the machine is in the given state, reading
the given symbol from the tape, it will enter newstate, write
newsymbol on the tape and move the tape according to movement, which
can be one of l (left), r (right), and n (none).

Further assume that "stop" is the name of the final state, and that
the symbol "empty" is written on all empty tape.

A tape will be represented as two Prolog terms, Left and Right. Left
is a list of all symbols to the left of the read head, in reverse
order. Right is a list of the symbol under the read head and all
symbols to the right of it. After the end of each list, the tape is
assumed to have the symbol "empty" written everywhere.

For each transition table entry, we write a Prolog clause:

If movement is n:

tm(state, Left, [symbol | Right], FinalLeft, FinalRight) :-
tm(newstate, Left, [newsymbol | Right], FinalLeft, FinalRight).

If movement is l:

tm(state, Left, [symbol | Right], FinalLeft, FinalRight) :-
tm(newstate, [newsymbol | Left], Right, FinalLeft, FinalRight).

if movement is r, we define two clauses:

tm(state, [X | Left], [symbol | Right], FinalLeft, FinalRight) :-
tm(newstate, Left, [X, newsymbol | Right], FinalLeft, FinalRight).
tm(state, [], [symbol | Right], FinalLeft, FinalRight) :-
tm(newstate, [], [empty, newsymbol | Right], FinalLeft, FinalRight).

In addition the the clauses obtained from the transition table, we
need the clauses:

tm(State, Left, [], FinalLeft, FinalRight) :-
tm(State, Left, [empty], FinalLeft, FinalRight).
tm(stop, Left, Right, Left, Right).

Now, the goal

tm(startstate, Left, Right, FinalLeft, FinalRight)

where <Left,Right> is the (nonempty part of) the initial tape, will
run the TM and return the final tape configuration in
<FinalLeft,FinalRight>.

So for each TM, we can construct a Prolog program. The program clauses
even have a single (or no) atom in the body, and it uses only one
single non-unary functor (the list constructor)!
--
Lars-Henrik Eriksson Internet: l...@sics.se
Swedish Institute of Computer Science Phone (intn'l): +46 8 752 15 09
Box 1263 Telefon (nat'l): 08 - 752 15 09
S-164 28 KISTA, SWEDEN Fax: +46 8 751 72 30

0 new messages