計算論入門「停止問題」
この記事では計算論の基礎として、アラン・チューリングが否定的に解決した「停止問題」について解説しています。記事の流れは、概要説明から始まり、自然数表記や部分関数の簡単な説明、プログラムの概念の導入を行った後、計算可能性の定義について解説するというものです。
プログラムの概念の導入は補助的なものであり、「プログラム」と呼んでいるものの正体はC言語風のレジスタ機械です。ですので、疑似コードを読める方は、この部分を読み飛ばしてかまいません。
数理論理学・計算理論とは計算論は数理論