アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

5.4

 汎用機械

157

これらの課題は、ある決まった範囲の文字を使って、シミュレートする機械のテープ内容をエンコー

ドするスキームを考案することで、解決することができます。エンコードのスキームに特定の文字しか

使われないのであれば、UTM はそれ以外の文字を特別な目的で安全に使うことができます。そして、

そのスキームがシミュレートするどんな状態と文字にも適応できるなら、シミュレートする機械の大き

さや複雑さを気にする必要はありません。

この目的にかなう限り、エンコードするスキームの詳細はさほど重要ではありません。可能なスキー

ムの1 つの例は、1 進

†

表現を使うことです。さまざまな値を単一の文字（たとえば

1

）を繰り返した長

さの違う文字列としてエンコードするのです。シミュレートする機械が文字a、

b

、

c

を使っていると

き、それぞれ

1

、

11

、

111

と1進でエンコードできます。そして別の文字（たとえば

0

）を、1進の値を

区切るマーカーとして使うことができます。すると、文字列

acbc

は

101110110111

と表現できま

す。これはあまり空間効率の良くないスキームですが、

1

の文字列をどんどん長くすることで、エン

コードする文字をいくらでも増やすことができます。

個々の文字をエンコードする方法が決まると、今度はシミュレートするチューリングマシンの規則を

表現する方法が必要になります。これは規則の各パーツ（状態、文字、次の状態、書くべき文字、動

かす方向）をエンコードし、必要なところにセパレータ文字を入れながら、テ