machine)は、概念上の計算機械です。モデル)重さや形のある現実の計算機とは異なります。計算するという概念の本質を探るための数学的なモデルです。その定義は、むしろ電子計算機より算盤(そろばん)にたとえた方がずっとわかりやすいです。チューリング機械の模式図としては、良く以下のような描き方がされます。何らかの問題を解き解答を得るという作業は、結局は人間が事前に定めたルールに従って、問題を変形させた結果に他ならないのではないか、ともいえます。ある数式を因数分解せよといわれたら、結局はその式に対して可能な変形を順次適用して因数分解の結果を得るわけです。厳密にルールに従って変形するだけでしょう。数学と言う分野に存在する、全てのルールを書物にまとめることが出来れば、近い将来には、数学と言う分野が不要になってしまうかもしれないともいえます。いうのは、順次ルールを適用すると言う作業は、その数式の意味を理解する必要が全く無いからです。ある数学の問題を記述でき、解等を読み上げる能力があればどのような困難な問題も解けてしまうでしょう。そのような機械的手続きのルール集は作れるか?という問いかけが数学者ヒルベルトによってなされました。これには、ゲーデルが否定的に結論を見つけてしまったわけですが。機械もそのような機械的計算手続きの考察から生まれたものに違いありません。人間にあたり、ヘッドは人間の手にあたります。テープは算盤本体にあたります。算盤は無限に続いていると考えます。人間は有限な数で表せる状態を持ち、算盤上の数と自分の状態だけから次の行動を全て決めなくてはいけません。人間に許されるのは、算盤上の手を左右に移動することと、算盤をはじくことだけです。人間は途中で方針を変えることなく、算盤の数字に従って定義どおり動きつづけなければなりません。今の若い人は算盤を知らなかったりして。世界最古の計算器でしょう。チューリング機械などという概念をいったい何に使うのでしょうか?その機能は以下のようなものだと思います。ある問題が計算できることを証明する。ある問題が計算できないことを証明する。ある問題が短時間で計算できることを証明する。ある問題が短時間では計算できないことを証明する。人間が機械に質問するときは、テープに記号列で問題を書き、チューリング機械はその問題を読み取りながらテープを書き換え(算盤をはじき)つつ答えを出力します。ある問題が本質的に計算不能であることを示すときは、その問題を解くチューリング機械が存在しないことを証明します。(参照→チャーチの定立)一言で言うと、「人間や計算機にできる計算はすべてチューリング機械で計算できる。人間が数学や哲学などの何らかの表現方法によって解けるはずの問題は必ず解くチューリング機械が存在し、解くチューリング機械が存在しない問題は、誰にも解けない。(参照→言語)これは学者の直感であります。計算可能とか現実的計算可能という言葉もチューリング機械で定義します。(参照→計算可能性)ある問題が計算できる(=問題を解くチューリング機械が存在する)ことが自明でも、その問題が簡単に計算できるかどうかがより重要なこともあります。計算が困難であることを示したい場合は、その問題を解く効率の良い(決定性)チューリング機械が存在しないことを証明します。利用して何秒かかるか測るという手段も考えられるでしょう。この場合は、計算機の細かなアーキテクチャやプログラムの実装の稚拙さが結果に反映されるので、「問題が本質的に持っている複雑さ」は見えにくくなります。チューリング機械は、細かなアーキテクチャを表面から隠しコンピュータの普遍的で基本的な性質だけで作り出された理想の機械であり、問題の計算不可能性や計算困難性を表現するために時代を問わず利用できる重要な概念です。機械の定義がシンプルなのは、本質以外の部分が取り除かれているからです。http://www.triplefalcon.com/定義まず決定性チューリング機械の定義を与えます。アルファベットと呼びます。与えるとき使う文字です。書き込まれていると考えます。空白はアルファベットに数えません。Γは機械が扱う文字全体をあらわし、テープアルファベットと呼びます。空白はテープアルファベットに含まれます。)テープは、メモリを概念として扱ったものと考えてください。a∈Γを読み取って動作します。