毎日1冊、こちょ!の書評ブログ

2013年8月から毎日、「そうだったのか」という思いを綴ってきました。

コンピュータにできない事を考えた人、アラン・チューリング~できない事、やりたくない事から開放される為の思考法

チューリングの仮想機械(Wiki)
  1. 無限に長いテープ
  2. その中に格納された情報を読み書きするヘッド
  3. 機械の内部状態を記憶するメモリ

で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。

 ・ヘッド位置のテープに情報を書き込む

・機械の内部状態を変える

・ヘッドを右か左に一つ移動する

上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。

ここで認識しなかればいけないのは「ヘッドが移動をする」ということ。

 f:id:kocho-3:20140206081206p:plain

 

 チューリングを読む コンピュータサイエンスの金字塔を楽しもうペゾルド氏はコンピュータソフト関連の著述家。 「コンピュータには計算できない数がある。チューリング機械を動かしてコンピュータと数学の限界に答えを出す。不朽の論文「計算可能数とその決定問題への応用」(1936)の本当の意味がわかる。」

ヘッドが移動する事=現在のコンピュータのすべて

ほとんど何もしないコンピューターを想像することにより、チューリングは実際には極めて有用な「汎用」コンピュータを考えていた。これは革新的な概念であった。その時代には、コンピューターはある特定の目的のために設計される機械であると一般的に思われていた。コンピューターを論理で動く機械として考えていたチューリングは物事を良く把握していた。初期のコンピュータ制作者の多くがハードウェアによる実現を考えていたのに対し、チューリングは1936年からずっとソフトウェアを書いていた。チューリングにとっては、加算のような基本的な算術形式でさえソフトウェアで実現するものであった。(245ページ)

ここで筆者はチューリングを引用する。『どんな計算機(下記補足)も模倣する事ができるというデジタルコンピュータのこの特別な性質は、デジタルコンピュータは万能機械であるといい表すことはできる。この性質のもつ機械の存在は、処理速度への考慮を別とすれば、様々な機械の方法を実行するために別々の新しい機械を設計する必要はないという重要な含蓄を有する。』

計算機:正しくは「離散状態機械」と記述。これはある定まった状態から別の状態へと状態が移りながら処理をしていく計算機の事と整理。

 

重要な事はヘッドはシンプルな情報処理しかしない物理的にも極小のヘッドが無限のテープを動いていく事。テープに処理すべきデータも、計算式もすべて記録されている。ここをヘッドが1ステップづつ移動していく。ヘッドは何もしない。無限のテープがあればすべての計算ができる。

ガラケースマートフォンを使った万能コンピュータの比喩

ガラケーからスマートフォンへのシフトは固定的な機械からソフトウェア的なヘッドへのパラダイムシフトに例えられよう。スマートフォンは何もせず、データとプログラムがすべてを行う。

チューリングの限界=コンピュータの限界

直感で理解できるが無限のテープは存在しない。

直感では容易に理解できないが論理学=コンピュータには答のない問題が存在する。(感情では理解できる)

この2つがチューリングの、そして現在のコンピュータの持つ限界である。そしてチューリングはできない限界を考えたからできる事を定義できた。

 

この限界を我々は解決していない。コンピュータの性能の向上、具体的にはソフトウェアの記述効率の向上、ハードウェアの性能向上、で能力が上がっていると感じる。それは限界が影響しない範囲内の事に限られる。

蛇足

できない事を想定する事はできる事に気づく事。別表現、やりたくない事はやりたい事に気づく事。