- Turing機械も、よく見るけど、あまりよく知らない言葉。
- あるTuring機械Mが受理する文字列の集りをMの言語という。またはMが認識する言語という。逆にその言語のことを、Turing認識可能とよぶ。別名として「帰納的列挙な言語」がある。
- ある文字列を認識するとは、受理状態にいたるConfiguration列が存在することである。
- このとき、認識されない文字列とは、拒否状態に入るか、ループするなどにより決して停止状態に辿りつかない場合の二つのあり様がある。
- 停止状態に辿りつかない、ということが発生せず、常に「受理状態に入るか、拒否状態に入るか」という2択しかおこりえないTuring機械を、判定装置(decider)という。
- ある言語がTuring機械MによってTuring認識可能なとき、その機械Mが判定装置ならば、それはTuring判定可能であるという。またそのときその言語を、Turing判定可能であるとよぶ。別名として「帰納的な言語」がある。
- 定義の変形に対するモデルの不変性を頑健性(robustness)とよぶ。
- Turing機械は驚くべき頑健性をもつ。
- 複数テープTuring機械、非決定性Turing機械、列挙装置らはTuring機械でシミュレーションできる。
- 量に関して制限のないメモリへの使い方に関して制限のないアクセス機能をもつすべてのモデルは、能力の点で等価である。互いにシミュレートできるので。
- 「この等価現象は重要な哲学的結論をもたらす。たとえ多くの異なる計算のモデルを想像できたとしても、それらが記述するアルゴリズムのクラスは同じものに留まるだろう。」
- アルゴリズムとは何だ?
- 「ある課題を処理するための単純な命令の集りである」
- 「毎日の生活におけるありふれた出来事では、手続き(procedure)や処方(recipe)と呼ばれることもある」
- procedure: (事を運ぶ)手順、順序、やり方、方法
- recipe: 調理法、作り方、方法、秘訣
- 直感的には、アルゴリズムというのはわかるが、ではその厳密な定義は?
- それがChurch-Turingの提唱
- 「アルゴリズムの直感的概念 等価 Turing機械のアルゴリズム」
- とあるんだけど、これ右側にアルゴリズムという言葉があると、曖昧なのでは。。。
- たぶん、
- 直感的概念におけるアルゴリズムというのは、Turing機械の構成と等価である。すなわち、ある課題においてアルゴリズムがある、ということは、その課題を解決するTuring機械を実装できるということであると考える。
- ここで言語と計算について再考。算術計算をするTuring機械のサンプルについて。これはi * j = kという関係を認識する。すなわち、Turing機械では、計算する、というのは、それを述語として、その述語をみたすものの集まりを正しく判定できるということであり、言語は、その述語をみたすものの集合である。なので、計算ということを集合論的に静的に考えているように思える。
- Turing機械を記述する際の言葉には3つのレベルがある。
- 正式な記述(formal description)
- 実装の記述(implementation description)
- 高レベルの記述(high-level description)
- 高レベルの記述につかう用語を定める。
- Turing機械への入力は常に文字列である。
- 入力として文字列以外のものをあたえたいならば、最初にそれを文字列として表現する。
- Turing機械は、与えられた表現(文字列)が我々の意図したとおりに解釈されるようにその表現を複合されるようプログラムする。
- この、モノの符号化にはいろいろな方法があるだろう。しかし、Turing機械は、つねに一つの符号化を他のものに翻訳できるので、どの符号化を選ぶかは重要ではない。
- モノOを文字列として表現した符号を<O>と書く。モノは英語でObjectという。
- これらを用語として、アルゴリズムは日本語で普通に記述する。
- Turing機械への入力は常に文字列である。
さあ、演習だ！
0 件のコメント:
コメントを投稿