Apa yang membuat PROLOG Turing-lengkap?

15

Saya tahu itu dapat dibuktikan PROLOG adalah Turing-complete dengan membangun sebuah program yang mensimulasikan mesin Turing seperti ini:

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

Sumber

Namun, saya bertanya-tanya bagian mana dari bahasa PROLOG yang bisa dilucuti (terutama simbol fungsi, klausa overloading, rekursi, unifikasi) tanpa kehilangan kelengkapan Turing. Apakah fungsi simbol itu sendiri Turing lengkap?

programming-languages turing-completeness logic-programming prolog Lenar Hoyt
sumber
4
Anda hanya memerlukan fitur prolog yang digunakan dalam cuplikan kode Anda.
Yuval Filmus
1
Pernahkah Anda melihat pertanyaan ini ?
Raphael
2
@YuvalFilmus: Mungkin ada cara lain pemrograman mesin Turing di PROLOG.
Lenar Hoyt

Jawaban:

18

Ini adalah aturan praktis yang cukup dapat diandalkan bahwa kelengkapan Turing tergantung pada kemampuan untuk membangun jawaban atau nilai antara "ukuran" tanpa batas dan kemampuan untuk mengulang atau mengulangi jumlah yang tidak dibatasi berkali-kali. Jika Anda memiliki dua hal itu, Anda mungkin memiliki kelengkapan Turing. (Lebih khusus, jika Anda dapat membangun aritmetika Peano, maka Anda tentu saja memiliki kelengkapan Turing!)

Mari kita asumsikan untuk saat ini bahwa Anda sudah menghilangkan aritmatika. Kami juga akan menganggap bahwa Anda tidak memiliki fitur non-logis seperti atom_chars,assert , dan sebagainya, yang memungkinkan shenanigans umum.

Jika Anda menghapus simbol fungsi, Anda tidak dapat membuat jawaban atau perantara dengan ukuran tidak terbatas; Anda hanya dapat menggunakan atom yang muncul dalam program dan kueri. Akibatnya, himpunan semua solusi yang mungkin untuk setiap kueri terbatas , jadi mengambil titik yang paling tidak pasti dari program / kueri akan selalu berakhir. Datalog (bahasa permintaan basis data relasional berdasarkan Prolog) bekerja berdasarkan prinsip ini.

Demikian pula, jika Anda membatasi Prolog hanya untuk rekursi primitif (yang tidak menyertakan rekursi sebagai kasus degenerasi), maka jumlah rekursi yang dapat Anda lakukan dibatasi oleh ukuran kueri, sehingga semua perhitungan berakhir. Jadi Anda perlu rekursi umum untuk kelengkapan Turing.

Dan, tentu saja, jika Anda memiliki rekursi umum, Anda dapat memotong sejumlah fitur dan mempertahankan kelengkapan Turing, termasuk penyatuan umum (konstruksi dan pencocokan pola tingkat atas sudah cukup), negasi, dan potongan.

Nama samaran
sumber
2
Satu klausa tanduk biner sudah cukup .
false
Poin yang sangat bagus. Saya tidak berpikir tentang kuantifikasi, tetapi itu memang pendekatan lain.
Nama samaran
0

Melengkapi jawaban yang bagus dengan @Pseudonim dan merujuk ke pertanyaan terakhir Anda "Apakah simbol fungsi sendiri sudah selesai?".

Anda mungkin bermaksud: Bisakah bahasa yang hanya membuat simbol fungsi menjadi Turing-Complete?

Jawabannya adalah ya - pikirkan bahasa Pemrograman Fungsional seperti ML dan Haskell.

François Bry
sumber