日時：2019年11月28日 （木） 16:30-18:00

場所： 北海道大学 文学研究院 E304室

参加者： 20名

タイトル： From Turing Machines to Kripke Models

スピーカー： 佐野勝彦 (北海道大学文学研究院・准教授)

アブストラクト：
アラン・チューリングが1936年に提案したチューリング機械は、無限長のテープ上でヘッドを左右に動かし数字の読み書きをする単純な計算モデルですが、理想化された計算作業者の振舞いを捉えるモデルとして提案されました。実は、現在使われているプログラミング言語でできることは、どんなことでもこのチューリング機械による計算モデルで出来ることが知られています。この講演の前半では、チューリング機械の計算モデルで解ける問題と解けない問題について簡単に説明します。チューリング機械の計算モデルで解けない問題は、我々が使っているプログラミング言語でも解けないことになります。

チューリング機械の動作は視覚的に分かりやすいグラフ（フローチャート、状態遷移図）で書くことができるのですが、こういったグラフは至る所に見られるものです。論理学の分野ではこういったグラフはクリプキモデルといわれ、モデル上で生じる事態を記述する簡明な言語（様相論理）があります。講演の後半部分では、理想化された推論者（エージェントとよびましょう）の知識状態を表すクリプキモデルを導入して、エージェントへの告知行為がどのように各エージェントの知識状態を変えるかを簡単な例を使って紹介します。特に、Plaza が1989年に提案した、エージェント集団全体への公開告知行為を扱う予定です。