Alan Turing's "Computing Machinery and Intelligence"

Paper Artificial Intelligence

論文の紹介

論文: A. M. Turing (1950) Computing Machinery and Intelligence. Mind 49: 433-460.

この論文にあるイミテーションゲームは2014年のアメリカドラマ映画のタイトルにもなっています。

イミテーション・ゲーム／エニグマと天才数学者の秘密(字幕版)

イミテーション・ゲーム／エニグマと天才数学者の秘密(字幕版)

Can machines think? （機械は考えることができるか？）

と作中でチューリング博士が尋ねられた質問は、この論文にとって非常に重要な問いです。 この問いに対して、人間の身体的能力と知的能力の間を区別して論じるため、 「イミテーションゲームをこなせる機械が存在するかどうか」という問いに置き換えて議論している。 イミテーションゲームは、別名「チューリングテスト」とコンピュータが知的かどうかを判定するテストとして有名です。

同様に、論文中では「機械」を「デジタルコンピュータ (digital computer)」に限定して議論している。 このデジタルコンピュータの一種として、チューリングが考案した計算機構モデルである「チューリング機械 (Turing Machine; TM)」が有名です。 （ただし、この論文中ではチューリング機械について言及しているわけではない。）

チューリング博士の考えでは、イミテーションゲームをこなすことのできる機械が実現可能であると述べている。 これは、論文が出版された1950年の技術に限定せず、デジタルコンピュータがその万能性を十分に発揮できるという条件を満たす場合について考察している。 つまり、1950年からみた未来の技術発展も考慮に入れている。

I believe that in about fifty years' time it will be possible, [...] , to make them play the imitation game so well [...]. The original question, "Can machines think?" I believe to be too meaningless to deserve discussion.
（私は約50年後にはイミテーションゲームをこなすことができると信じている。元の「機械は考えることはできるか？」という問いは、議論するに値しない意味のないものになると信じている。）

以上からも、現在の人工知能（Artificial Intelligence; AI）や認知科学といった現在の分野の先駆者であることは見て取れる。 数学的な反論、意識に関する立場からの反論だけではなく、神学的な反論や超能力を信じる立場からの反論など、 当時の人々の様々な反論に対して議論をしていることも特徴である。

そのチューリング博士は論文の最後に、こう締めくくっている。

We can only see a short distance ahead, but we can see plenty there that needs to be done.
（我々は少し先の未来しか見通すことができないが、やるべきことはたくさんあることはわかる）

論文を読んだ感想

2014年に、チューリングテストを合格したというニュースが飛び込んできた。 Turing Test 2014において、スーパーコンピュータ Eugene が、判定者の33％から「人間かコンピュータかを判別出来ない」と評価された。 これは情報工学における歴史的快挙であるが、この合格に異議を唱えている学者もいるとのこと。

論文では、出版年である1950年から50年後、つまり2000年以降（21世紀）について、 平均的な質問者が 5分間やりとりしても 70% 以上の 確率で正しい判断はできなくなると述べている。 チューリング博士が予測した未来には、未だ到達をしているわけではないが、知性を持った機械の登場は今後現れる予兆の一つではないかと思う。

参考文献

AOJ #0033 Ball (玉)

Probramming Contest Search algorithm C++

問題の概要

問題文: AIZU ONLINE JUDGE #0033 Ball (玉)
　最初に与えられた1数値の入った10個の玉を、2つの筒に順に振り分ける問題。 振り分ける際に、各筒の最上部の玉の値より大きくなければならないとした時、振り分けられるかどうかを判定する。

解答例

1. 貪欲法（グリーディー法; greedy algorithm）を用いた解法

　1つ目の玉から順に見ていき、筒B→筒Cの順番で入れられる時点で入れていく方針。 この時、各筒の最上部の値を確認すると、筒Cより筒Bの方が値が常に大きくなる。 どちらの筒にも玉を入れられる時には、常に値の大きい筒Bの方に入れることとなるため、筒Cの値を常に最小の値にし続けることができる。

2. 全探索を用いた解法

筒は2本、玉は10個しかないため全組合せでも 2^{10} = 1024 通りしかない。したがって、全探索を用いても速度的な問題は一切ない。

2.1 深さ優先探索（DFS: Depth-First Search）を用いた解法（再帰関数版）

　配列balls[]に入力された玉の順序が格納されており、それを引数idxによって順に指定し、条件を満たす限り再帰を続けている。 引数b,cは筒B,Cそれぞれの最上部の玉の数値を保持しており、それよりballs[idx]が大きければ問題の条件をみたす。 筒BまたはCのいずれかでも成り立つことが分かった場合、trueを返し、どちらも満たさなければfalseを返すようになっている。

2.2 深さ優先探索（DFS: Depth-First Search）を用いた解法（スタック版）

　現在の状態として現在取り扱っている玉のidxと、筒B,Cの最上位の玉の値を tuple<int, int, int> より表現している。 それらの状態をスタック stack<tuple<int, int, int> > states に積むことでそれぞれの状態を格納している。 条件を満たす限り筒に玉を入れていき、最後まで入れることができる状態が一つでもあれば探索を終了し、YESを出力している。 また全ての状態を探索し、どの状態についても最後まで入れることができなかった場合はループを終了し、NOを出力している。

2.3 Bitを利用した二分木に対する全列挙を用いる解法

　10個の玉を筒BとCへ順番に入れていき、現在の各筒の一番上の玉より値が大きいかどうかを確認するという手法で実装している。 どの玉をどちらに入れるかは変数bitの2進数によるフラグを利用し、0は筒Bを、1は筒Cを意味している。 配列top[]に保持している現在の各筒の一番上の玉の値と比較し、それより小さかった場合は満たさないため次の状態へ移行している。

3. その他の解説サイト

総評

　基本的な問題のため、様々な解法がある。 競技プログラミング初心者にとって、うってつけの練習問題だと思う。

　以上のソースコードは以下のGithub上にて参照可能です。 https://gist.github.com/farma11/c34af9de7c9a184dc7a0a576455851f1

github.com