The simplest non-trivial program pattern in logic programming is
the following one :
$$lefteginarrayl
p( extitfact)leftarrow
p( extitleft)leftarrow p( extitright).
leftarrow p( extitgoal).
endarray
ight.defglobble#1gobble$$
where extitfact, extitgoal, extitleft and extitright are
arbitrary terms. Because the well known extitappend program
matches this pattern, we will denote such programs `` extitappend-like''.
In spite of their simple appearance, we prove in this paper that
termination and satisfiability (i.e the existence of
answer-substitutions, called the extitemptiness problem) for
are undecidable. We also study some subcases depending on the number
of occurrences of variables in extitfact, extitgoal,
extitleft or extitright.
Moreover, we prove that the computational power of extitappend-like programs
is equivalent
to the one of Turing machines ; we show that there exists an
extitappend-like universal program. Thus, we propose an equivalent of
the Böhm-Jacopini theorem for logic programming. This result
confirms the expressiveness of logic programming.
The proofs are based on program transformations and encoding of
problems, unpredictable iterations within number theory defined by
J.H. Conway or the Post correspondence problem.