計算量理論入門　メモ

問題と機械
問題とは課題であり、機械はそれを解く方法である。
問題とは、各入力に対して答えが〇か×か定めたもの。この答えは、これに限定されるものではない、なぜならそれを定められないものも出てくるため。
問題は一つの無限な入力を含んでいて、有限な方法で解明していく。
εの部分集合を言語という。だから、その記号に意義を持たせるため、言葉の中に言葉を内包することができる。
能動と受動の関係性により、論理立てられて操作される。
始状態数と受理状態数の投げかけと受け取りで現象は発生する。
問題を機械が認識するには、ある入力を与えた際に受理と不受理で判断される。
状態は有限個であるため、どんなに文字列を連関させても同じ状態に戻ってくる。
　

京都大学 数理解析研究所 第42回数学入門公開講座「計算量理論入門 —「複雑さ」をとらえる」河村 彰星（数理解析研究所 准教授）2021年8月2日 第1回（全4回）

https://www.youtube.com/watch?v=K3iH-ODshMQ&list=LL&index=4&t=2034s