四則演算

2

この章の冒頭において、チューリング・マシーンはコンピュータで計算可能な問題は全て表現可

3

能と述べました。よって、たとえば正整数の四則演算もチューリング・マシーンを用いて実行可能

4

なのですが、ではどのような仕組みで演算を実現すればよいのでしょうか。

5

前節で見たように、チューリング・マシーンの構造は非常に単純です。そのため、四則演算を実

6

現するには少し工夫が必要です。

7

まず、正整数nをチューリング・マシーンに表現せねばなりません。ここではテープ上に記号

8

1を n個並べて表すと約束します⁵。

9

5つまり、1進法による数の表現を用いる訳です

&

1 B B ˙˙˙

B B B ˙˙˙

1 1 1 1

1 1 1 1 1

ࣃֈभઆ

އࢄभઆ

図15.3: チューリング・マシーンによる3 + 2 = 5の計算

そして、mとnの加算のための入力記号列を、左からm個の1、区切り記号の&、n個の1を

1

並べて表すと約束します。となれば、加算の実行後には、左からm+n個の1が並ぶようにチュー

2

リング・マシーンが動作すればよいのです。図15.3に、3 + 2 = 5 に対応するチューリング・マ

3

シーンの初期状態と最終状態を示します。

4

考察 図15.3のような加算を行うチューリング・マシーンを設計しなさい。

5

減算も同様です。これには、前節の言語{a^mbⁿ|m > n}を受理する例題が参考になるでしょう。

6

乗算m×nでは、mを n 回加えるように設計します。これには加算を行うチューリング・マ

7

シーンの動作を利用します。

8

除算m/nでは、mからnを引いた回数をテープ上にメモしておけばよいでしょう。これには

9

減算を行うチューリング・マシーンの動作を利用します。

10

数の表現形式が私たちの通常の感覚からすれば単純過ぎるため違和感があるかもしれませんが、

11

チューリング・マシーンで四則演算を実現することができます。四則演算ができるならば、それを

12

組み合わせることで指数や平方根の計算も可能です。さらに複雑な計算も可能であり、結果として

13

チューリング・マシーンを用いて任意の算術計算を実行可能です。

14

15.3.2 万能チューリング・マシーン

15

チューリング・マシーンでは多種多様な処理を記述することができます。それぞれの処理をそれ

16

ぞれチューリング・マシーンとして設計し、実行した場合、そのチューリング・マシーンはその処

17

理のための

専用

^{コンピュータ（}special-purpose computer）として働きます。おもしろい

18

ことに、チューリング・マシーンの中にはそのような様々な専用チューリング・マシーンをシミュ

19

レートできるものが存在し、特に任意のチューリング・マシーンをシミュレートできるチューリン

20

グ・マシーンは

万能

チューリング・マシーン（universal Turing machine）と呼ばれてい

21

22 ます。

今、専用コンピュータであるチューリング・マシーンを処理内容に応じ、番号を付けてTM1、

23

TM2、...と区別することにします。次に、その中のひとつのマシーンTMi への入力記号列を S

24

S B B

˙˙˙

TMi

S B B

˙˙˙

TMU

P[TMi] B

(a) 専用マシーンによる実行 TMi(S)

(a) 万能マシーンによる実行 TMU(P[TMi],S)

図15.4: 専用チューリング・マシーンと万能チューリング・マシーン

とします。このとき、S を入力とするTMiの実行をTMi(S)と表します。図15.4 (a)がそれに対

1

応します。

2

次に、万能チューリング・マシーンをTMU と表します。その入力は、TMi の設計図—これ をP[TMi]と表します—とそのTMiへの入力 S です。設計図であるP[TMi]は入力ですから、

テープの上に記号列として載っていなければなりません。たとえば、この章の最初のチューリン グ・マシーンには

δ(q0, a) = (q1, x, R), δ(q1, a) = (q1, a, R), δ(q2, a) = (q3, a, L), ...

という状態遷移が定義されていました。これらを記号列として表すには、たとえばテープ上の各セ

3

4 ルに

0 a 1 x R 1 a 1 a R 2 a 3 a L ...

5

と配置すればよいでしょう。ただし、0,1,2,3, a, x, R, L∈Σと仮定します。図15.4 (b)は、記号

6

列 P[TMi] と S を空白記号 B を挟んでテープ上に初期配置し、そのテープ上をテープ・ヘッド

7

が左右に動きながら動作する万能チューリング・マシーン TMU を図式化しました。この実行を

8

TMU(P[TMi], S)と表現しましょう。この実行では、TMU は、S の上の記号をひとつ読み込ん

9

だ後にP[TMi]の中から次の状態遷移にマッチする規則を検索し、その規則に則った遷移を行い、

10

S 上の該当箇所の記号を書き換え、さらに S の上の次の記号を読み込み ... と動作を行ないま

11

す。専用マシーンの実行 TMi(S)をひとつひとつシミュレートしていくため、万能マシーンの実

12

行TMU(P[TMi], S)は TMi(S)に比べ、非常に手間の掛かる動作になりますが、等価な動作が可

13

能です（機械が停止したときのテープの状態はTMU(P[TMi], S)とTMi(S)で厳密に等しくなり

14

ます）。逆に言えば、任意の TMi、S についてTMi(S)と等価な動作が可能なチューリング・マ

15

シーンを万能チューリング・マシーンと呼びます。

16

もし万能マシーンを用意できたならば、任意の専用マシーンと等価な動作ができる訳ですから、

17

いちいち特定用途の専用マシーンを作る必要はありません。実行時間は専用マシーンに比べて掛か

18

りますが、万能マシーン１台で任意の計算ができるのです。

19

今日、私たちがコンピュータと呼んでいるものは、万能チューリング・マシーンTMU に相当

1

します。コンピュータのメモリあるいはハードディスクなどの記憶装置は、チューリング・マシー

2

ンのテープに相当します。そして、私たちがプログラム（あるいはソフトウェア）と呼んでいるも

3

のは、 P[TMi] に相当します。入力データは、S に相当します。コンピュータ上で入力データを

4

与えてプログラムを実行することは、TMU(P[TMi], S) に相当します。現在のコンピュータは万

5

能チューリング・マシーンを数学的基礎とするものです。この方式の特徴は、プログラムをメモ

6

リ上にデータと記憶しておく点です。それゆえ、メモリ上のプログラムを書き換えるだけで、様々

7

な計算を実行できます。この方式は

プログラム内蔵方式

^（stored

8

program method）と呼ばれ、コンピュータの重要な基本原理のひとつとなっています。

9

1943年に世界で最初に開発された電子式コンピュータ ENIAC では、プログラムとデータは

10

峻別されていました。入力データはメモリに格納されたものの、プログラムは多数のスイッチの

11

ON/OFFと部品間のケーブルの接続によって実現されていました。そのため、プログラムを入れ

12

替えるにはスイッチの切り替えとケーブルの張り替えが必要とされ、１回のプログラムの入れ替え

13

に数日を要したようです（出展: Wikipedia）。プログラム内蔵方式は、ENIACの次の世代のコン

14

ピュータEDVACによって実装されました。その開発においてドイツ系ユダヤ人研究者フォン・ノ

15

イマンがプログラム内蔵方式を提案したとされ、それに由来して、プログラム内蔵方式の今日のコ

16

ンピュータをしばしばノイマン型コンピュータと呼んでいます。

17

15.3.3 チューリング完全

18

チューリング・マシーンは有限状態オートマトン、プッシュダウン・オートマトンよりも高い記

19

述力を有し、多種多様な処理を記述することができますが、チューリング・マシーンよりもさらに

20

大きな記述力、表現力を持つ機械は存在するのでしょうか。

21

20世紀前半に多くの数学者によって様々な機械、数学体系が提案され、その表現力が研究され

22

ました。代表的なものとして以下のようなものがあります⁶。

23

チューリング・マシーン ... 本章の主題です。

24

帰納的関数 ... 自然数の上の関数に対して、いくつかの計算上の仕組みを導入し、関数の表現力を

25

論じるものです。

26

ラムダ計算 ... ラムダ式（λ式）と呼ばれる表現形式に対して、いくつかの変形操作を定義し、様々

27

な式の変形に関する性質を論じるものです。

28

タグシステム ... 文脈自由文法の生成規則に類似した規則を用いて記号列の変形を繰り返し、変形

29

の性質を論じるものです。

30

6個々について詳細な述べませんので、興味を持った人は自身で調べてみてください。

興味深いことに、それぞれは独立して提案されたにも関わらず、これらはいずれも等価な記述力を

1

持つことが分かっています。このことは、どのような手順や操作を用いようとも、機械的な手順や

2

操作で記述できる内容⁷には共通の限界が存在することを示唆しています。ここで言う「記述力」

3

は計算能力、計算可能性（computability）と等価です。そこで、

4

計算可能である ＝ チューリング・マシーンで計算できる

5

と見なそうという提案がなされました。この提案を、上記の等価性の研究に貢献した研究者の名前

6

を冠してチャーチ＝チューリングの提唱（Church-Turing thesis）またはチャーチの提唱（Church’s

7

thesis）と呼んでいます。なお、この提案は定理ではありませんから証明できません。「計算可能で

8

ある」ことの定義を与えている（そう考えようと提案しているに過ぎない）ことに注意してくだ

9

10 さい。

チャーチ＝チューリングの提唱は、任意の計算可能な内容を実際に記述し、実行するにはチューリン

11

グ・マシーンを用いればよい、あるいはチューリング・マシーンと等価なシステムを用いればよいことを

12

意味しています。そのような等価なシステムのことを

チューリング完全

13

（Turing complete）⁸であると言います。

14

前節で述べたように、私たちが日頃使用しているノートPC（のハードウェアとそれを動かす機

15

械語）はチューリング完全です。プログラミング言語も計算を記述できるシステムと見なすこと

16

ができます。まず、C/C++/Java/Rubyなどのプログラミング言語はチューリング完全です。何

17

故ならば、C++でチューリング・マシーン（たとえばこの章で取り上げたチューリング・マシー

18

ン）をシミュレートするプログラムを作ることはできるからです。その意味でC++はチューリン

19

グ完全です。世の中に知られているプログラミング言語のほとんどはチューリング完全であり、一

20

般にはチューリング完全でないものはプログラミング言語と呼びません。反例として、Web文書

21

作成用のHTML（HyperText Markup Language）やデータベース言語SQL（Structured Query

22

Languageが語源とされています）は 一見するとプログラミング言語に似た構造を持っています

23

が、チューリング完全ではありません。

24

ドキュメント内 _auto (ページ 114-118)