お掃除３

データはプログラムだ †

• △を描くプログラム再訪

  プログラムをデータとして書き、

  そのデータにしたがって動作するプログラムと組み合わせることで△が描ける

プログラムはデータだ †

• △を描くためのデータを生成するプログラム

再帰的なプログラム †

• コッホ曲線を描こう
• 実習: C曲線に挑戦しよう
• 実習: ドラゴン曲線に挑戦しよう
• 実習: さまざまな木を描いてみよう

コッホ曲線を描くための Scratch のプログラムを公開します。授業で作ったときはリストをふたつ利用しましたが、今度の例ではひとつしか使っていません。その分、プログラムは小さくなりましたが、同じリストが二役を果すので少し複雑かもしれません。

さらに改良を加えたプログラムでは、左命令、右命令を実行するときにすぐに直進するように変更すると命令列の変換の部分が単純化できました。さきほどの例でもそうでしたが、短いプログラムがわかりやすいかというと必ずしもそうとは限りません。

Scratch を用いた授業のまとめ（情報科学への招待） †

ハードウェア †

キーワード

チューリングマシン

論理学者の Alan Turing が提唱した仮想的な機械。テープの上を移動するプログラム可能な有限状態の機械。チューリングマシンは計算機の動作原理を説明するためのひとつのモデルです。チューリングマシンを利用することによって、問題の困難さの概念（専門用語では複雑性の概念）が定義されるなど、計算機科学における基礎として位置づけられています。

ソフトウェア †

チューリングマシンにおけるプログラミングは、テープの上の記号と現在の状態から、(1) テープに書き込むデータ、(2) 次の移動方向と(3) 次の状態を定めるだけの単純な仕組みです。計算機科学にはチューリング完全性という概念があります。これは、あるプログラムや問題の解決法をチューリングマシンのプログラムに翻訳できるか否かということにあたります。汎用プログラミング言語は一般に表現力が非常に高いため、チューリングマシンを簡単に記述することができます。興味深いことは一般のプログラミング言語を用いて記述された内容をろくな機能を提供していないチューリングマシンのプログラムに変換できることです。逆にチューリングマシンを用いて記述することができない問題は、コンピュータを用いても解決することができない問題とされています。このような問題は計算不能と呼ばれます。有名な計算不能問題としてプログラムの停止問題が挙げられます。この問題は、与えられたプログラムが停止するか否かを一般的に判定するプログラムは存在しないと解釈できます。

また、このような計算不能問題が存在することは論理学や数学基礎論における基本的な定理であるゲーデルの不完全性定理の別な解釈と見做すことができます。

ソフトウェアの万能性 †

チューリングマシンをうまくプログラムすることによって、チューリングマシンの動きをチューリングマシンを用いてプログラムすることができます。チューリングマシンは仕組みが単純な機械ですので、ハードウェアを用いて実装することができます。このハードウェアであるところのチューリングマシンをプログラムすることによって、チューリングマシンを模倣するチューリングマシンのプログラムを作成することができます。これはハードウェアでできたチューリングマシンの上で動作するソフトウェア版のチューリングマシンと見做すことができます。

このことと、チューリング等価性から、あるプログラミング言語を用いて、そのプログラミング言語を模倣するプログラムが作成することができることが分ります。この図式における「模倣するプログラム」を計算機科学ではインタプリタと呼びます。

キーワード

万能チューリングマシン

リフレクション、そして Matrix †

コンピュータを模倣するプログラムがどのような可能性を提供するのでしょう？コンピュータCの上でCを模倣するプログラム P があったとしたら、コンピュータCの上で動くプログラムPはコンピュータの模倣ですから、その上でプログラムPを動かすことができるはずです。言っている意味、わかりますか？

• C の上で動くプログラムP(= Cの模倣)、なので
• Cの上でプログラムPを動かし、その上でPを動かせる

ということです。ここで P はソフトウェアですので、これを少し変更することもできます。これを P’ としましょう。P’ に加える変更は、P を模倣しつつ P を修正することです。

普通のソフトウェアは予め定まったプログラムを実行します。しかし、ここで述べたような実行形式を利用することでプログラムの挙動を実行時に変化することができます。あまりに難しすぎるのでここでは解説しませんが、この考え方をさらに進めた先に、超循環翻訳機、自己反映計算などの興味深い概念があります。

理学セミナーにおいて千葉教授が映画 Matrix を引用して情報科学の本質を説明されたと思います。Matrix は3Dグラフィックス、プロット、ファッション、格闘シーン、撮影技法などさまざまな面で目を見張るものがあります。情報科学、数学基礎論、そしてその背景となるある種の哲学において知られている自己反映計算 (Reflection) という概念があるのですが、Matrix 全編を通じて自己反映の考え方が貫かれているのは興味深いです。

Matrix における世界は、Matrix のなかにおける思索とそれが具現化した仮想世界から構成されています。ふたつの世界は、Matrix から仮想世界に対してはMatrix の世界における思念によって、逆に仮想世界から Matrix の世界に対しては黒電話によって繋がれています。Matrix の DVD を借りてきて、三度目に見直すころにはこのふたつの世界の双対性について考えてみることをお薦めします。計算機科学における自己反映の概念を学ぶと、哲学的で難解な自己反映の概念が Matrix によって絶妙な映像化がなされたことがわかると思います。