計算可能関数
計算可能性理論は主に形式言語を扱う。アルファベットは任意の集合である。単語はアルファベットに含まれる文字(記号=集合の元)を有限個並べたものである。同じ文字が複数回使われてもよい。例えば、2進数の文字列はアルファベット { 0 , 1 } {\displaystyle \{0,1\}} における単語である。言語は、あるアルファベットにおける全単語の集合の部分集合である。例えば、2進数表記のうち 1 を必ず3個含むものの集合はバイナリのアルファベットにおける言語である。
形式言語の重要な特性として、ある単語がある言語に属するかどうかの判定の難しさのレベルがある。ある言語に属する単語を入力として受け付ける計算可能関数を定義するには何らかの符号体系を構築しなければならない。ある言語が計算可能であるとは、あるアルファベットにおける単語 w についての計算可能関数 f {\displaystyle f} があり、その単語がその言語に属する場合は f ( w ) ↓= 1 {\displaystyle f(w)\downarrow =1} 、その単語がその言語に属さない場合は f ( w ) ↓= 0 {\displaystyle f(w)\downarrow =0} となることをいう。つまり、ある言語が計算可能であるとは、任意の単語がその言語に属するかどうかを正しく判定できる手続きがある場合をいう。
ある言語が計算可枚挙であるとは、計算可能関数 f があり、単語 w がその言語に属するときだけ f ( w ) {\displaystyle f(w)} が定義されていることをいう。enumerable という用語の語源は自然数の計算可枚挙な集合の場合と同じである。