論文　訳（一部）

１９３６年発表
「計算可能数について−決定問題への応用」




「計算できる数」は簡単には実数として表現され得る。そしてそれは１０進数の表現が限定された手段で
計算できる。この論文の主題は表面上計算できる数であり、そして積分変数や実数や計算変数や計算でき
る属性などを明確化し、研究することは割合簡単である。しかしながら、基本的に問題は全ての場合にお
いて内在されている。そこで私は最小の煩わしさを包含する明白な推論法をして計算できる数を選んだの
だ。私は手短に算用数や算用数関数、その他のものの関係を述べたい。この論文は算用数に関して述べら
れた実数、変数の関数定理への発展を含んでいる。私の定義によると、もし１０進数が機械によって書く
ことができるならば一つの数は計算され得る。
　９・１０章において私は、算用数は通常計算され得ると思われている全ての数を含んでいるという幾つ
かの論点を述べる。とりわけある大きな階級の数字は計算できることを示す。それらは例えば全ての代数
の実数部分とか、ベッセル関数の０の定数部分とかπ・ｅなどの数を含む。しかし、計算できる数は全て
の定数を含んではいない。例えば計算できない定数は示されない。
　計算できる数の階級が巨大であり、そしていろんな点で実数の階級と似ていても言うまでもなく列挙す
ることができる。８章で私は反対論を検算するであろうある論点を吟味する。これらの論点の一つの正し
い適用により、私の結論はゴーデルの結論と表面的にはよく似たものとなった。これらの結果は価値ある
方向を持っている。
　特に１１章で示すようにヒルベルトの「決定問題」(Entscheidungsproblem)には解法がない。
アロンゾ・チャーチ(Alonzo・Church)の最近の論文によると、私の計算できる数に匹敵する
「効果的な解決法」の概念が導入されている。しかしそれは（私のものと）非常に異なって結論されている。
チャーチも又、あの「決定課題」について私と同様に結論を出している。計算能力を効果的計算法との等
価性の証明はこの論文の付録であらましを述べてある。


１．計算機


　我々は既に計算できる数は、その１０進数が限定された手段で計算されるものであると述べた。このこ
とはかなり明確な定義を必要とする。この定義を正当化するための正しい試みは我々が９章にたどり着く
までなされなかった。現在私は、この正当化は人間の記憶に必然的に限定されていると、そう、事実の中
に存在していると言うであろう。 我々は実数の計算の過程において人間と我々がｍ−配列と呼んでいる
q1、q2・・・・qnの条件の数だけを限定できる機械を比較することができる。機械はその中を走る「テープ」
（紙のアナログ）が支給され、そして区域（スクエアと呼ばれる）部分に分けられ、スクエアはいつでも
唯一のそれぞれの記号（シンボル）を持っている。それは「機械内部」にあるというＳ(r)を持ったｒ番目
と呼ばれている区域である。我々はこの区域を「スキャンスクエア」と呼ぶ。走査された区域の記号は走
査された記号と呼ぶ。走査された区域の記号はその機械の中で唯一の記号であり、言わば「直接に認知さ
れている」記号である。しかしながらそのｍ−配列を変更することによって機械は以前に走査されたと思
われる幾つかの記号は効果的に思い出すことができる。機械のある程度の性能はいつでもｍ−配列qnと走
査された記号Ｓ(r)によって決定されている。このqnとＳ(r)の一対は「配列」と呼ばれ、かくしてこの配
列が機械の能力を決定している。走査域が空白（即ち記号が欠落している）になっている配列状態の、あ
る幾つかでは機械がこの走査域に新しい記号を書き込む。又、ある配列状態では機械が記号を消去する。
機械は又、走査された区域を右や左に変移して移動することができる。これらの操作を加えることによっ
てｍ−配列も変えられる。書き下された記号の幾つかは、計算できる実数の１０進数の連続を形成する。
　他のもの、記録は補助するための大ざっぱな記号である。これは率直に大ざっぱな記号であり、容易に
抹消されてしまう。これらの操作が数の計算において、今まで用いられた全ての操作を含んでいるという
ことが私の論点である。機械の理論も読み手に通じているときには、この論点の弁明はより容易であろう。
それ故、次章で私はこの理論の発展を進め、更に「機械」「テープ」「被走査」などによって意味される
ことを理解されていると確信する。

　　　
２．定義

自動機械


　全ての場合において機械の動作が（第一章の意味で）配列によって完全決定されているならば、我々は
その機械を「自動機械」または（ａ−マシン）と呼ぶであろう。いろんな目的で我々はその動作が配列に
よって一部分だけ決定されている。（ここでは第一章におけるpossibleという語を用いる）機械（自動機
械またはコンピュータ機械）を使用するであろう。このような機械が不確かな配列に到達したときには、
外部操作者によってある仕事の選択がなされるまで機械は進行を止める。もし我々が機械を自明的システ
ムで表現して使用するならばこのような例が起り得るであろう。なお論文では私は自動機械のみ取り扱う
故に、しばしば（ａ−マシン）の接頭語のａを落とすことがある。


計算機　


　もし自動機械が２種類の記号を打ち出すならば、その最初の（図形と呼ばれる）種類は０と１とから構
成されており、もう一つは（第2種類の図形とも呼ばれるもの）であるが、その機械はコンピュータマシン
と呼ばれる。もし機械が孔空きテープが供給されており、正しい初期のｍ−配列からスタートして運転さ
れるならば、第１種の図形で印刷された結果は、機械によりコンピュータ化された連続と呼ばれる。
１０進数の観点によりあらかじめ連続性を得ている２進としての表現を持った実数は、機械によって計算
された数と呼ばれる。機械の動作のどのような段階においても走査された数字・テープ上の全ての記号の
完全な連続、そしてｍ−配列はその段階における完全な配列を描記するといわれている。連続する完全な
配列の間の機械やテープの変更は、機械の運動と呼ばれる。


循環式と非循環式機械


　コンピュータマシンがもし第１種の記号の限定された数字しか書かないならば、それは循環式と呼ばれる。
他のものは非循環式と呼ばれる。その機械が他に可能な動きのない配列に到着した場合や、また機械が運転
されていって、第２種の記号を印刷し、第１種の記号をもはや印刷できない場合は、その機械は循環式と呼
ばれる。「循環」という述語の重要性については第８章で述べる。


数列の機械

 
　もし連続が非循環式機械により計算され得るならば、連続は計算され得る。もし数字が非循環式機械に
より計算された数字、”整数”によって区別されるならば、その数字は計算され得る。我々は計算できる
数字よりも完全な連続についてしばしば語ることによって混乱を避けることができよう。


３．計算機の例


　I。ある機械は連続の０１０１０１・・・という配列を数えるように出来ている。この機械は
"b"，"c"，"e"，"f"という４つのｍ−配列を持っており、”０”と”１”を印刷することができる。
機械の行動は次の図に示されている。この中で"R"は機械が動いていって、「以前に走査された場所の上を
直ちに正確に走査する」ということを意味している。同様に"L"や"E"は「走査された記号が消去される」
ことを意味し、"P"は「印刷する」ことを意味する。この図表（そして同種の全ての連続図表）は最初の
２段において描かれた配列に続いて第３種の走査は連続的に実行され、そして機械の最後の段に描かれて
いるｍ−配列へと進行していく、ということを意味していると理解される。第２段が空であれば第３段、
第４段の行動はどんな記号も表していないということが理解される。機械は"b"という空のテープを伴った
ｍ−配列の中を進んでいく。
　　　　　　　　　　　　　　　　　　　　　　　（以降略）