Co sprawia, że ​​PROLOG Turing jest kompletny?

Wiem, że można udowodnić, że PROLOG jest kompletny z Turinga, tworząc program symulujący maszynę Turinga w następujący sposób:

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]).

Źródło

Zastanawiam się jednak, które części języka PROLOG można usunąć (szczególnie symbole funkcji, przeciążanie klauzul, rekurencja, unifikacja) bez utraty kompletności Turinga. Czy same symbole funkcyjne Turinga są kompletne?

Jest to dość niezawodna zasada, że ​​kompletność Turinga zależy od umiejętności konstruowania odpowiedzi lub wartości pośrednich o nieograniczonym „rozmiarze” oraz zdolności do zapętlania lub powtarzania nieograniczonej liczby razy. Jeśli masz te dwie rzeczy, prawdopodobnie masz kompletność Turinga. (Mówiąc dokładniej, jeśli potrafisz zbudować arytmetykę Peano, to na pewno masz kompletność Turinga!)

Załóżmy na chwilę, że już rozebrałeś arytmetykę. Będziemy również założyć, że nie masz żadnych non-logicznych funkcji, takich jak atom_chars, asserti tak dalej, które umożliwiają ogólne shenanigans.

Po usunięciu symboli funkcji nie można tworzyć odpowiedzi ani półproduktów o nieograniczonych rozmiarach; możesz używać tylko atomów pojawiających się w programie i zapytaniu. W rezultacie zestaw wszystkich możliwych rozwiązań dowolnego zapytania jest skończony , więc zajęcie najmniej ustalonego punktu programu / zapytania zawsze zakończy się. Datalog (język zapytań relacyjnej bazy danych oparty na Prologu) działa na tej zasadzie.

Podobnie, jeśli ograniczyłeś Prolog tylko do prymitywnej rekurencji (która nie obejmuje rekurencji jako przypadek zdegenerowany), wówczas ilość rekurencji, którą możesz zrobić, jest ograniczona rozmiarem zapytania, więc wszystkie obliczenia zostaną zakończone. Potrzebujesz więc ogólnej rekurencji dla kompletności Turinga.

I oczywiście, jeśli masz ogólną rekurencję, możesz wyciąć całą masę funkcji i zachować kompletność Turinga, w tym ogólną unifikację (wystarczy konstrukcja i dopasowanie wzorca na najwyższym poziomie), negację i cięcie.

Uzupełnienie doskonałej odpowiedzi przez @Pseudonim i nawiązanie do ostatniego pytania „Czy same symbole funkcji są kompletne?”.

Prawdopodobnie masz na myśli: czy język składający się tylko z symboli funkcji może być kompletny w Turingu?

Odpowiedź brzmi: tak - pomyśl o językach programowania funkcjonalnego, takich jak ML i Haskell.