n, f(n), ff(n), fff(n), ...

がいつかは1に到達するとき、便宜上「fは停止する」ということにしよう。 たとえば有名なコラッツの未解決問題は、f(2n) = n、 f(2n+1) = 6n+4 としたときfは停止するか？と述べることができる （ただし本講義ではこの問題には立ち入らない）。

停止性に関わる問題はコンピュータサイエンスの成立と発展の原動力となってきた。 たとえばコンピュータサイエンスの一番の基本定理は次のように述べることができる： 任意のfが与えられたとき、それが停止するかどうかは決定不能である（チューリング） 。

また、停止性は数学基礎論の観点からも重要である。たとえばペアノ算術の 無矛盾性を示すことは、ある種の操作fについて停止性を示すことに帰着する。 このときfは実際に停止する（ペアノ算術の無矛盾性）のだが、 fの停止性はペアノ算術の中では証明できない（第二不完全性）。つまり 「fは停止する」という命題は真なのに証明できない（第一不完全性の具体例）。

本講義ではこのあたりの事情について概観することにより、コンピュータサイエンスと 数学基礎論への導入としたい。