授業展開＃１１ コンピュータは 何ができるか、できないか

コンピュータのモデル化 コンピュータは、記号的にアルゴリズムとして定義できる内容は、基本的に何でも実行することができる。 コンピュータを抽象的にモデル化し、計算ができる・処理ができるということはどういったことか、コンピュータは何ができるのかという課題について検討する。

処理 コンピュータでは、全ての情報、データ、プログラムも記号列で表している。情報処理はこの記号列に対しておこなう。この処理には２種類がある。 　　コンピュータでは、全ての情報、データ、プログラムも記号列で表している。情報処理はこの記号列に対しておこなう。この処理には２種類がある。 組み合わせ的処理 　入力が確定すると出力も確定する処理。 　　→　数学の関数計算 順序的処理 　過去の入力の順序に依存して出力が確定する関係を「順序」的という。 　　→　自動販売機の入金

記憶と内部状態 コンピュータは、全体として、内部状態としてメモリがあり、順序的な機械である。 メモリは有限であるため、状態数も有限である。 　コンピュータは、全体として、内部状態としてメモリがあり、順序的な機械である。 　メモリは有限であるため、状態数も有限である。 　入力によって「記憶」＝「状態」が変化するが、状態が変化することを「状態遷移」という。

オートマトン（automaton） オートマトン（automaton） 自動人形、自動機械、ロボット 　自動人形、自動機械、ロボット 　入力記号列の受理機能を備えた抽象的な機械のこと。 　複数形は、オートマタ（automata）。 　例：自動販売機 　　ジュース代金：１１０円 　　入力として許される（受理される）内容 　　　１００円、１０円 　　　　５０円、１０円、５０円 　　　　５０円、５０円、１０円 　　入力として許されない（受理されない）内容 　　　　１００円、１円 　　　　　５０円、１０円 　　　　　　１円、１００円

有限オートマトン 最も簡単なオートマトンの一つ。 構成 ・入力テープ 入力文字列が書き込まれたマス目からなる 　　・入力テープ　入力文字列が書き込まれたマス目からなる 　　・読み取りヘッド　入力テープを読み取り、有限状態部に送る 　　・有限状態部　初期状態から入力文字列に従い、内部状態を次の状態に遷移させる。状態には、受理状態（最終状態）と 　　非受理状態がある。 入力テープ 入力文字列を読み取り、状態遷移を繰り返し、入力情報が終了すると停止する。 終了したときの内部状態が最終状態になっていれば、受理したという。 状態と入力文字の組み合わせに、次の状態を対応させた表を動作表（状態遷移関数）という。 a b a b b 読み取りヘッド 有限状態部

動作表（状態遷移関数）の例 状態 入力 ０ １ ｑ０ ｑ１ ｑ２ － 状態ｑ０の時に入力０があると状態はｑ０になる。

状態遷移図 受理される言語は、「１つ以上のｂが続いた後、１つ以上のａが続く形の語」からなる言語 b Ａ a Ｂ 有限オートマトンの例 初期状態 最終状態 b a b a Ｓ１ Ｓ２ Ｓ３ 入力　bbaaa：受理される。 初期状態 最終状態 受理される言語は、「１つ以上のｂが続いた後、１つ以上のａが続く形の語」からなる言語

プッシュダウンオートマトン 有限オートマトンにプッシュダウンテープという外部記憶装置をつけたもの。 入力テープ 　有限オートマトンにプッシュダウンテープという外部記憶装置をつけたもの。 　プッシュダウンテープは、書き込みは一番上に追加し、読み出しは一番上から取り出す外部記憶装置。 　入力語＝文字列を読み終わったときに、プッシュダウンテープが空ならば入力語を受理する。 a b a b b 読み取りヘッド Ａ Ｂ Ｚ 有限状態部 プッシュダウンテープ 読み書きヘッド

チューリングマシン（Turing Machine） 有限オートマトンの入力テープの代わりに、入出力テープ（読み書きテープ）を付けて、それを補助の外部記憶としても使えるようにしたオートマトン ヘッドは左端から左へ出ない限り、右、左に１マス移動できる。 有限状態部の動作（次の状態、書き込む文字、左右どちらに動くか）は、そのときの内部状態とテープから読み取った文字の組み合わせから、決められる。 最終状態が定義されており、最終状態に遷移すると停止し、入力語を受理する。 読み書きテープ ０ １ １ ０ ０ １ b b b b b 読み書きヘッド b ： 空白記号 有限状態部

チューリングマシンの動作表の例 状態 テープ記号 ０ １ b q0 （ q0, b, R ） （ q1, b, R ） 動作は３つ組（Ａ，Ｂ，Ｃ）　　　Ａ：状態、　Ｂ：テープへの書き込み、　Ｃ：ヘッドの動作 状態：ｑ０、ｑ１、ｑｆ、　　ｑｆは最終状態 テープ記号：０、１、 b 、　bは空白記号 ヘッドの動き：Ｒ、Ｌ、Ｓ　　　Ｒ：右へ１マス、　Ｌ：左へ１マス、　Ｓ：動かない たとえば、状態ｑ０の時、ヘッド位置のテープ記号が１であると、動作は（ q1, b, R ）であるから、状態がｑ１に遷移し、テープのヘッド位置に空白（ b ）を書き込んで（１からbに書き換える）、ヘッドが右（Ｒ）に１マス動く。 状態 テープ記号 ０ １ b q0 （ q0, b, R ） （ q1, b, R ） （qf, 0, S ） q1 （ qf, 1, S ）

チューリングマシンとコンピュータ コンピュータは、データ（入力文字列）を受け取ると、プログラムの命令に従って、メモリ（状態）を書き換えたりしながら、最後に入力に対応した文字列を出力して停止する。 チューリングマシンの動作表はコンピュータのプログラムに相当し、状態はメモリに、有限状態部はコンピュータの本体（ＣＰＵ）に相当する。 コンピュータは何ができるかを抽象的な機械でもあるチューリングマシンを使って考える。

チューリングマシンの全域性と部分性 動作表の未定義動作による異常停止はしないと考える（異常停止状態も最終状態の一つとしておく）と、どんなチューリングマシンもある入力データに対して結果を出力して停止するか、停止しないかとなる。 　・任意の入力データに対して停止して結果を出力する動作表をもつチューリングマシンを全域的であるという。 　・全域的でないチューリングマシンは部分的であるという。（無限ループしたり、ハングアップしたりするチューリングマシン）

チューリングマシンとアルゴリズム チューリングマシンが全域的であれば任意の入力に対して停止して結果を出力する。部分的であれば、入力値によっては停止しないことになる。 全域的チューリングマシンが計算する関数は全域的であるという。部分的チューリングマシンが計算する関数は部分的であるという。

チューリングマシンとアルゴリズム 全域的関数 ｍ（ｘ，ｙ）＝ｘ×ｙ 任意の（ｘ，ｙ）に対して計算結果を与える。 部分的関数 　　ｍ（ｘ，ｙ）＝ｘ×ｙ 　　任意の（ｘ，ｙ）に対して計算結果を与える。 部分的関数 　　ｆ（ｘ）＝√ｘ：但し、ｆ（ｘ）もｘも0を含めた自然数 　　ｘ＝０、１、４、９、・・・の時以外は関数が存在せず未定義となる。 ある関数を計算するチューリングマシンが全域的であるとき、その計算手続きはアルゴリズムであるという。停止性が保障されている計算手続きがアルゴリズムである。

計算理論 チューリングマシン：自然数ｘを入力して、自然数ｙを出力する関数ｆ（ｘ）＝ｙを計算する機械とする。 チューリングマシンは何ができるか？ 　→　チューリングマシンはどのような関数を計算できるか。 コンピュータは何ができるか？ 　　→　計算できる関数とは何か。 このような立場から、アルゴリズム、計算手続きを検討する理論を計算理論という。

コンピュータとチューリングマシン 入力に対して出力を返す処理能力においてコンピュータとチューリングマシンは同等である。 チューリングマシンの動作表は、チューリングマシンの動作中、変化しない。チューリングマシンは、外部プログラム式コンピュータもしくは固定式プログラムコンピュータに相当する。 チューリン グマシン コンピュータ ＣＰＵ 入力装置 出力装置 入力データ 入力データ 出力 出力 動作表 固定プ ログラム 作業領域 作業領域 入出力テープ メモリ（主記憶）

処理不能について どのように構成しても処理できないことを証明できるか？ 構成方法、工夫は無限のため直接証明することは不可能である。 万能なチューリングマシンに不可能であることを示せばよい。

万能チューリングマシン 他のあらゆるチューリングマシンの動作を模倣できるチューリングマシン プログラム内蔵式コンピュータに相当する。 ＣＰＵ プログラム・入力データ 動作表・入力データ 入力装置 出力装置 出力 出力 動作表 アルゴリズム 作業領域 作業領域 入出力テープ メモリ（主記憶）

コンピュータによるコンピュータの模倣 コンピュータＡの上で、コンピュータＢのシミュレーションをすることができる。 新製品の開発など現在は不可欠な技術

コンピュータは何ができないか チューリングマシンの停止問題 　任意のチューリングマシンに任意のデータを入力したとき、それが停止するかどうか、事前に判断するアルゴリズムがあるか？。

停止問題の判定アルゴリズム ＜Ａｗ＞：チューリングマシンＡの動作表と入力データｗを記号化して一つにしたもの。 万能チューリングマシンをＴとする。 Ｔに＜Ａｗ＞を入力すると、ｗを入力されたＡを模倣する。 ＜Ａｗ＞に対してＴが停止するならば、０を出力して停止する。 ＜Ａｗ＞に対してＴが停止しない（暴走する）ならば、１を出力して停止するチューリングマシンＭを考える。 すなわち、Ｍは、 Ｔ＜Ａｗ＞→停止＝Ｍ→０ Ｔ＜Ａｗ＞→暴走＝Ｍ→１

Ｍは、 Ｔ＜Ａｗ＞→停止＝Ｍ→０ Ｔ＜Ａｗ＞→暴走＝Ｍ→１ Ａはｗに対して停止するかしないかどちらかであるから、＜Ａｗ＞に０か１を対応させる関数ｆは全域的である。従って、Ｍは全域的チューリングマシンである。 Ｍの代わりに、 ＜Ａｗ＞が停止するとき暴走し、＜Ａｗ＞が暴走するときに停止するチューリングマシンＭ１を考える。 Ｍ１は、 Ｔ＜Ａｗ＞→停止＝Ｍ１→暴走 Ｔ＜Ａｗ＞→暴走＝Ｍ１→停止

いま、＜Ａ＞を入力すると、＜ＡＡ＞を出力するチューリングマシンＣを構成しておく。Ｍ１の前にＣをくっつけて合成したチューリングマシンＭ２をつくる。 Ｍ２に＜Ａ＞を入力すると、Ｍ１に＜ＡＡ＞が入力される。＜ＡＡ＞を入力されたＴは、＜Ａ＞を入力されたＡの模倣をする。 Ａは、Ａ自身の動作表を入力データとするが、このときもＡは停止するかしないかどちらか。 Ｔ＜ＡＡ＞→停止＝Ｍ２＜Ａ＞→暴走 Ｔ＜ＡＡ＞→暴走＝Ｍ２＜Ａ＞→停止 Ａは任意のチューリングマシンだから、ＡとしてＭ２を代入する。

Ｔ＜ＡＡ＞→停止＝Ｍ２＜Ａ＞→暴走 Ｔ＜ＡＡ＞→暴走＝Ｍ２＜Ａ＞→停止 Ａは任意のチューリングマシンだから、ＡとしてＭ２を代入する。 Ｔ＜Ｍ２Ｍ２＞→停止＝Ｍ２＜Ｍ２＞→暴走 Ｔ＜Ｍ２Ｍ２＞→暴走＝Ｍ２＜Ｍ２＞→停止 これは、＜Ｍ２＞に対してＭ２が停止するならば、Ｍ２は＜Ｍ２＞に対して暴走する。＜Ｍ２＞に対してＭ２が暴走するならば、Ｍ２は＜Ｍ２＞に対して停止するを意味する。・・・・・・矛盾

矛盾の原因 Ｃは容易に構成できるから、Ｍ２はＭ１が構成できれば、問題ない。Ｍ１はＭから簡単につくれる。 すなわち、最初の仮定、Ｍが存在するということが矛盾の原因である。つまり、Ｍは存在しない。 Ｍが存在しないということは、Ａがｗに対して停止するときは、０を出力し、停止しないときは１を出力するというチューリングマシンは存在しないということになる。 チューリングマシンの停止問題をとくアルゴリズムは無い。

次週小テスト（12／18）　範囲：９－１１回目 電卓、筆記用具、直筆ノート