本記事はエムティーアイ Advent Calendar 2021の10日目の記事です。
※タイトルと内容はあまり関連していません。
※Prologを初めて触りました、程度の記事です。
はじめに
先日、ロボットがパラドックスを考えて壊れてしまう描写を観てからというもの、
Prologならどうなるのか（またどう解決するのか）が気になり夜しか眠れません。
ただ、「Prolog パラドックス」と調べてもあまり記事は出てこなかったため、実際に試してみました。
書いてみる
文法
Prologを初めて触るため、文法を確認します。
a(b). % b = a
a(b, c). % bとcは、aという関係を持つ
a :- b. % bならば、a
a :- b, c % bかつcならば、a
自己言及のパラドックスを書く
試しに「私は嘘つきです」という自己言及のパラドックスを与えてみます。
上記のパラドックスをProlog内でどう表現すべきか分からなかったのですが、以下のように記述してみました。
% "lierが何かを言う"場合の規則を以下のように捉える
% not(hoge) :- is_lier(X), say(X, hoge).
% hoge :- not(is_lier(X)), say(X, hoge).
not(is_lier(X)) :- is_lier(X), say(X, is_lier(X)).
% Xがlierである、かつ、Xが（Xはlierである）と言うならば、Xが話す内容（Xはlierである）は偽である
is_lier(X) :- not(is_lier(X)), say(X, is_lier(X)).
% Xがlierでない、かつ、Xが（Xはlierである）と言うならば、Xが話す内容（Xはlierである）は真である
実行結果
案の定パラドックスに陥り、何も結果を返してくれません。
実行過程のトレース
嘘つきか嘘つきでないかを延々とループしてしまっているようです。
パラドックスを回避する
いくらプログラムと言えど延々とループさせるのは酷なため、なんとか回避させてあげたいです。
Wikipedia 自己言及のパラドックスのページ
上記のページによると、言語を階層化させるのが一つの解決策のようです。
階層化して書いてみる
上位の言語が下位の言語に言及する形のみを残してみました。
% Xが第0階層 数字の大きい方を上位とする
% is_lierが第1階層
is_lier(X) :- say(X, is_lier(X)). % 第2階層 xはlierであるが、第2階層には適用されない
say(akiyama, is_lier(akiyama)).
実行結果
関係性が上位から下位の一方向のみになったため、trueと返してくれました。
実行過程をトレースしてみても、ループが発生していないことを確認できます。
結論
Prologに自己言及のパラドックスを与えると、（手動でトレースする限りでは）延々とループして答えを出せない状態になりました。
また、上位から下位への一方向の言及のみを残すことで上記のループを解決できました。
個人的には矛盾を抱え爆発することを期待していたため、少し残念です（）。
おまけ
試しに他のパラドックスも書いてみます。
ワニのパラドックス
※簡潔にするため、母親だけを登場させてます。
% ワニが母親を食べるか食べないについて
not( eat(crocodile, mother) ) :- plan( crocodile, eat(crocodile, mother) ), not( can(crocodile, eat(crocodile, mother)) ).
% ワニは母親を食べようとしている、かつ、ワニが母親を食べられないならば、ワニは母親を食べない
not( eat(crocodile, mother) ) :- plan( crocodile, not(eat(crocodile, mother)) ), not( can(crocodile, eat(crocodile, mother)) ).
% ワニは母親を食べようとしていない、かつ、ワニが母親を食べられないならば、ワニは母親を食べない
eat( crocodile, mother ) :- plan( crocodile, eat(crocodile, mother) ), can( crocodile, eat(crocodile, mother) ).
% ワニは母親を食べようとしている、かつ、ワニが母親を食べられるならば、ワニは母親を食べる
eat( crocodile, mother ) :- plan( crocodile, not(eat(crocodile, mother)) ), can( crocodile, eat(crocodile, mother) ).
% ワニは母親を食べようとしていない、かつ、ワニが母親を食べられるならば、ワニは母親を食べない
% ワニが母親を食べることができるかできないかについて
not( can(crocodile, eat(crocodile, mother)) ) :- eat( crocodile, mother ), guess( mother, plan(crocodile, eat(crocodile, mother)) ).
% ワニが母親を食べる、かつ、母親がワニは母親を食べようとしていると推測するならば、ワニは母親を食べられない
can( crocodile, eat(crocodile, mother) ) :- not( eat(crocodile, mother) ), guess( mother, plan(crocodile, eat(crocodile, mother)) ).
% ワニが母親を食べない、かつ、母親がワニは母親を食べようとしていると推測するならば、ワニは母親を食べられる
% ワニと母親に関する事実
guess( mother, plan(crocodile, eat(crocodile, mother)) ).
% 母親はワニが母親を食べようとしていると推測する
% plan( crocodile, eat(crocodile, mother) ). % どちらかを初期状態として想定
% ワニは母親を食べようとしている
plan( crocodile, not(eat(crocodile, mother)) ). % どちらかを初期状態として想定
% ワニは母親を食べようとしていない
実行してみると、こちらも延々とループしていました。
環境
Windows 10
WSL 2/Ubuntu 20.04 LTS
SWI-Prolog
https://www.swi-prolog.org/