2026年07月07日 第5回
チューリングマシンの構成と仕組みについて理解できなかったため、
演習課題の前に復習したいと思います。
計算量理論について、
入力サイズの増大に伴う実行時間の変化を漸近的に捉える重要性を理解しました。
不明なところは質問してください．
計算量については次回詳しくお話しします．
強いチャーチ・チューリングの提唱に関して、 乱数を用いて次の動作を確率で決めるということについて、 そもそも乱数とはどのような計算によって決められるのだろうと思いました。 また、 チューリングマシンが状態遷移を用いて処理を進めていくことが面白いなと思いました。
計算機の中なので，擬似乱数にはなりますね．
量子コンピュータは計算不能性そのものを覆すものではないが、 「強い」提唱を破りうると考えられている、 という整理は、 量子コンピュータの意義を正しく位置づける上で重要だと感じた。 量子コンピュータが優位性を持つとされる例はいずれも「特殊な構造を持つ問題」だという説明だったが、 逆にどのような問題であれば量子コンピュータでも優位性が出ないと分かっているのかが気になった。
そうですね．量子計算の重要性を示していると思います． 例えば，通常の四則演算，ソーティングなどは差が出ないですね．
本日の講義を聴き、 チューリングマシンが現代のコンピュータの基礎となる計算の概念を数学的にモデル化したものであることを学びました。 テープ、 ヘッド、 状態遷移という極めてシンプルな要素だけで、 理論上あらゆる計算が可能であるという点に、 計算の普遍性を感じました。
そうですね．チューリングマシンはそのようになるとおもいます．
本日の講義では、
チューリングマシンの具体的な動作原理から、
計算の限界を示す停止問題、
そして最新の量子コンピューティングにいたるまで、
計算論の系譜を体系的に学ぶことができました。
演習問題を通して、
実際にテープの書き換えや状態遷移（q1 ,q2など）の手順を追ったことで、
目に見えないアルゴリズムの動きを視覚的に理解することができました。
ヒルベルトの問いに対するチューリングの結論や、
決定不能問題の存在について学んだことで、
プログラムが「解ける問題」と「原理的に解けない問題」の境界線が明確になりました。
さらに、
古典コンピュータでは膨大な時間がかかるNP完全問題へのアプローチとして量子コンピュータが期待されている背景を知り、
今後の情報科学における新しい計算パラダイムへの興味がより一層高まりました。
理解することができましたか．
自分でも色々と調べてみるとよいですね．
今回の授業では、 問題を形式的に定義する方法や、 言語認識・判定問題について学びました。 これまでは「問題を解く」ということを漠然と考えていましたが、 入力と出力を明確に定義することで、 計算機が扱える問題として表現できることを理解しました。 また、 文字列がある言語に含まれるかどうかを判定する考え方や、 チューリングマシンの基本的な構成について学び、 計算理論の基礎となる内容であることが分かりました。 最初は抽象的で難しく感じましたが、 具体例やプログラムの例を見ることで少しずつ理解が深まりました。 今後はチューリングマシンがどのように計算を行うのかについても、 さらに理解を深めていきたいと思いました。
自分でも色々と調べてみるとよいですね．
言語と判定問題が等価と講義内で言っていたが、 判定問題として定義するだけでいいのに、 どうして計算論としての言語という概念が存在するのか気になった。
良いコメントですね．講義ではこれ以上触れませんが，
(次回簡単に触れますがが)
言語といっても実はいろいろとあって，
何で判定できるかによって差があります．
また，言語は集合なので，集合に対する演算などができるため
数学的に扱いやすいという側面もあると思います．
今回の講義では、
チューリングマシンについて学んだ。
最初は、
テープやヘッドを使う計算モデルが少し古い考え方のように感じたが、
説明を聞いていくと、
計算をとても単純な動作に分けて考えるためのモデルだと分かった。
チューリングマシンは、
現在の状態、
現在読んでいるテープの記号、
書き込み、
移動、
状態更新によって動くという点が特に印象に残った。
また、
2進数の加算の例では、
1011に1を足して1100にする過程を、
右へ移動したり、
1を0に書き換えたりしながら実現していた。
普段なら一瞬で計算してしまう内容でも、
チューリングマシンでは一つ一つの手順として表せることが分かり、
計算の仕組みをかなり基本的なところから考えているのだと思った。
理解してくれていますね．
自分でもやってみて理解がさらにすすんだようで，
よろしいと思います．
チューリングマシンが状態、 テープ上の記号、 ヘッドの移動によって計算を進める仕組みを理解できました。 2進数に1を加える処理では、 右端からビットを確認し、 繰り上がりを状態遷移で表している点が分かりました。
やはり自分でやってみると理解が進みますね．
本日の講義では、 主にチューリングマシンの要素や命令リストの読みかたを学べた。 演習課題などの問題で様々なテープに対してプログラムを適用して解き、 解き方をマスターしたいと思う。
いろいろと考えてみると良いと思います．
今日の講義では、
プログラムと入力をどちらも文字列として扱ってその挙動を判定するという、
問題を解くことの形式的な定義について理解が深まりました。
文字列がある言語に属するかどうかを判定する枠組みや、
チューリングマシンが状態やテープといったシンプルな要素と状態遷移表で機械的に動く仕組みもよく分かりました。
一方で、
計算可能や計算不能、
決定可能や決定不能という言葉の厳密な定義の違いや、
それぞれの境界線がまだ自分の中で整理しきれていません。
また、
チューリングマシンの動作表で状態q2から最終状態qhに変わる一連の動きが、
全体として具体的にどんな計算処理を意味しているのかが少しイメージしづらかったです。
疑問点として、
判定問題の正のインスタンスを集めるという操作が、
言語の定義やチューリングマシンの受理という概念にどう結びつくのかをもっと詳しく知りたいです。
また、
今回出てきたYesOnString問題などが、
プログラムの挙動を予言できないという停止性問題の証明にどう関わってくるのかも気になりました。
次回改めて説明をしますが，不明なところがあれば，質問してください．
チューリングマシンは決まったプログラムに従って動き、 とても明瞭なものだと感じた。 たしかに、 現代のコンピュータの内部計算よりも処理時間はかかるアルゴリズムかも知らないが、 プログラムが正しければ解を求めることができると思った。 時間があれば、 確率的なチューリングマシンについても教えて欲しいです。
決定論的なTMは，講義でも説明した通り，
現在の状態，テープの値とルールによって
動作は一意に定まります．
確率的なTMは，各の各ステップで，次の状態への遷移については，
確率的に選択するようになっています．
内部に乱数があると思ってくれたら良いと思います．
具体的な計算は，講義でもいいましたが，
素数判定のアルゴリズムなどがその例です．