00:00
今回のエピソードでは、画面を対応しています。
ポッドキャストでお聞きの方は、状況が分かりづらいところが多々あるかと思いますので、ご注意ください。
お手数ですが、概要欄に貼ってある動画版で見ることをお勧めします。
こんにちは。もっさんです。
テトリスで汎用的なコンピューティングを行うという理論を紹介するこのシリーズ。
前回は導入編として、計算機とは何かという話をしました。
今回は具体的にテトリスでどうやって汎用的なコンピューティングを行うかという話をしたいと思います。
前回の内容をまだ見ていらっしゃらない場合は、先に見てから今回の内容を見ることをお勧めします。
まず具体的な理論の内容に入る前に、今回紹介するサイトの概要を紹介したいと思います。
今回のテトリスで汎用的な計算を行うという理論を掲載しているサイトですが、
ミートファイターというブログでして、普段はゲームの改造などの投稿を行っているサイトです。
古くは2006年からで、今回のテトリスの内容は最新の投稿にあたります。
今回紹介するテトリスの記事ですが、現代はテトリス is capable of universal computation というものです。
日本語に訳すとこれまで見た通りテトリスは普遍的な計算が可能ですという内容になります。
このコンテンツの中では、まず前回話したように計算機の一番原始的な要素である
一般的な半導体で言えばトランジスタにあたる部分をテトリスでどうやって表現するかという内容が序章で語られます。
続いてそのテトリスによる回路表現を用いて、具体的な論理芸能を作成していきます。
さらに拡張していき、それぞれの命令にあたるシフト演算や試速演算や統合不統合など、
そういった各命令の回路をどうやって実装しているかというところが続けて書かれています。
またロジック回路部分だけでなく、テトリスを使ってメモリーを表現するということもやっているらしいです。
ちょっと私はまだこちらの方を読んでないので、今回のシリーズではこのメモリーやそれ以降の内容については詳しくは紹介はしません。
ただメモリーであったりだとか、具体的にコンピューターをどう作り上げていくかというところをちゃんと説明されていて、
さらにはこのテトリスによるコンピューターをシミュレーションするためのシミュレーターであったりだとか、
アセンブリ現場など実際にプログラムを組むことができるようになっています。
こちらのシミュレーターはJavaベースで提供されています。
このシミュレーターに関しては別途紹介したいと思います。
最後にアプリケーションの例などが書かれており、本当にテトリスからパソコンを作り上げるというかなり壮大なコンテンツとなっております。
03:05
ちなみにこのサイトの権利はクリエイティブコモンズに準拠していまして、
しかもクリエイティブコモンズのかなり緩い方でして、
素材をコピーしてまたそのまま再配布を可能でありますという風になっていますので、
今回の動画、このサイトの画像をそのまま動画として録画させていただき、使わせていただきたいと思っております。
では全体の内容を俯瞰したところで一番重要なアイデアであります。
テトリスでどうやってトランジスター的な回路に相当するものを実現するかという理論の内容に入っていきたいと思います。
テトリスで回路設計を行うわけですが、回路を行う場所として一般的なテトリスのゲームプレイと同じような、
マス目で区切られたフィールドが回路の設計対象の場所となります。
この図を見ていただくと分かる通り、横側と縦側それぞれにおいて番号が振られています。
これがこのフィールド上の座標にあたります。
このフィールドに対してテトリスの一個一個のピースであるテトリノミーを配置していきます。
テトリノミーはプログラムしやすいようにこの図の通り左側からTJZOSLIという名前が付けられています。
このアルファベットは実際のテトリノミーの形に即した名前となっております。
実際、テトリノミーを使ってどうやって回路を組んでいくんだという話なんですが、
その例をこちらに示します。
パッと見わけが分からないかと思いますが、
こちら、前回計算機の概要を示したときと同じように、
下側にインプット、真ん中にロジック、そして上側にアウトプットというようにデータの流れができています。
このインプットとアウトプットの場所はちょっと分かりづらいのですが、
このインプットの部分は、この場合だと下側の白い部分がインプットだと思ってください。
この場合だと、1、2、3、4、5、6、7、8と8ビットのインプットデータになります。
真ん中にロジックがごちゃごちゃと存在しています。
これはいずれもテトリノミーの配置で実現されています。
一番上側がアウトプットの端子でして、
今回の場合ですと紫色のテトリノミーの真ん中の列の部分が相当します。
具体的には一番上から2行分を使って0か1かを判定しています。
これを使って、1、2、3、4、5、6、7、8、
入力と同様に8ビットの出力を表現しています。
ちょっと分かりづらいので、今見た入力と出力の部分についてもう少し詳しく説明します。
先ほど白い部分が入力だと言いましたが、具体的には縦2行、連続する2行を使って0か1かというものを表現します。
06:09
基本的なところなので詳しくは話しませんが、
我々が扱う計算機はデジタルの計算機になります。
デジタルとはすなわち0と1を使って情報を表現します。
1ビットであれば0か1で2種類の情報が表せますし、
複数ビットを用いればよりたくさんの情報を表すことができます。
今回紹介するテトリスによる回路では、
この0と1の表現を連続する2行のフィールドを使って表しています。
この白い部分がテトリナミが存在するところになりまして、
この連続する2行の上側の行にテトリナミが存在しないときは値として0を表します。
上側の行にテトリナミが存在する場合は1を表します。
このように上側が埋まっているか埋まっていないかによって0と1を表現します。
先ほど見ていた回路を改めてみると分かりますが、
回ビットから見て1、1、0、1、1、0、1、1、0、0、0という風にやっていて、
確かにその1の部分は白いテトリナミが2行存在していて、
0のところに関しては白いテトリナミが1行しか存在していません。
このようにすることで0と1を表現しています。
こうやって入力のデータを0か1という形で表現することによって、
1のときはこの上側に存在するテトリナミを1行分だけ押し出すということを行っているわけです。
この押し出されたテトリナミがどんどんどんどん伝搬していって上側に到達します。
アウトプット側ですが、入力と同様に2行の領域に対して上側が埋まっていれば1、
埋まっていなければ0というような形で表現をしています。
つまりこの下側から押し出されてきて、それが伝搬して、
出力の領域に対して上側が埋まるか埋まらないかで0、1を表すわけです。
こうすることで入力の0、1の情報がこのロジックの部分で伝搬していって、
アウトプットが確定するというものになります。
ここまで見てきた入力、ロジック、出力を使って簡単な論理ゲートを作ってみましょう。
まずはオアゲートを作りましょう。
このコードの部分は無視して下さい。下側の図だけを見てください。
オアエンザンは複数ビットの入力に対して1ビットを出力します。
今回の場合だと2ビット入力で1ビットを出力するというものになります。
09:00
入力は1列で2行、出力は2行×2列という形になっています。
ロジック部分には2×2のテトリノミーを配置します。
こうすると入力が0と0の時はロジックのテトリノミーは上側に行かないので、
出力の部分の一番上の行が埋まらないので出力は0になります。
つまり0×0入力の時は0。
入力のどちらかが1になるとロジックである2×2のテトリノミーは上に上がるので、
出力の最上位の行が埋まり出力は1になります。
両方上がった時は同様に出力が1になります。
このようにすることでオアゲートを実現することができます。
このように入力、ロジック、出力をテトリノミーで表現することによって様々な回路ができます。
いくつか回路を紹介していきたいと思います。
まずは1ビットから複数ビットに拡張するような回路です。
この場合入力が1ビットで入ってきたものを横に広げて8ビット出力として出しています。
逆に複数ビット入力で1ビットに出す場合にはこのように横長のものから1ビットの出力に連搬するように作ることができます。
ここまでで基本的な内容をわかったかと思いますが、最後にノアゲートを見てみようと思います。
するとパッと見謎の挙動が起こっています。
ロジック部分で使われている2×2のテトリノミーが入力の値によって横の位置がずれています。
ゼロゼロの時は右側、それ以外の時が左側という風になっています。
なぜこのような現象が起きているのでしょうか。
これがこの理論がちゃんとテトリスで回路設計を行っているという証でもあります。
この理由については次回説明します。
