無限集合と言語

ゲーデル数

ゲーデル数
k個の可算無限集合（有限集合を含んでもOK）の直積の要素(i1,i2,...ik)を素数P1,P2,...Pk（互いに異なりこの順で大きくなる素数列）を用いて表した値
例:３つの加算無限集合A,B,Cがあるとする
A={a_1,a_2,a_3,...}\\B={b_1,b_2,b_3,...}\\C={c_1,c_2,c_3,...}
素数列として、P_1=2,P_2=3,P_3=5を用いると、ABCの直積に現れる組は
(a_1,b_1,c_1)=2^{1}3^{1}5^{1}\\(a_2,b_1,c_1)=2^{2}3^{1}5^{1}\\{\vdots}\\(a_i,b_j,c_k)=2^{i}3^{j}5^{k}
ここで、2^{i}3^{j}5^{k}がゲーデル数

半自由群

{0,1}からなる言語で、空系列εを含む{ε,0,1,00,01,10,11,000,...}={ω1,ω2,ω3,ω4,ω5,...}を半自由群という。

単位元

単位元
ある演算を定義したときに、演算してもほかの要素を変化させない要素のこと。“演算に対して決まる”ので注意
例：掛け算では1は単位元だけど、足し算では０が単位元になる。

アルゴリズムと手続き

機械Mがある言語Lを受理するというのは次の場合

受理する
bold;">アルゴリズムを実現:Lに属す言語を入力したら受理して停止。Lに属さない言語の場合は非受理で停止。
受理する
bold;">手続きを実現:属すなら受理して停止。属さない場合は非受理で停止するか永久に停止しない。停止しない場合は非受理とみなす。

帰納的可算集合と帰納集合

帰納的可算集合
言語Lを受理する手続きを有限長で書けるときLは帰納的可算集合
帰納集合
言語Lを受理するアルゴリズムを有限長で書けるときLは帰納集合

明らかに"帰納的可算集合⊃帰納集合"

ある受理機械が受理する言語の生成法

アルゴリズムを実現する受理機械の場合
言語を入力すると有限時間内に結果が返ってくるので、半自由群を順に入力し、受理すれば出力し非受理なら出力しないようにすれば、受理アルゴリズムが売りする言語を生成できる。
手続きを実現する受理機械の場合
非受理の場合有限時間で止まらない可能性がある。そこで半自由群の要素ωjに対してkステップやってダメならとりあえず次に行く、ということをする。(j,k)は加算無限集合なので、順番に組み合わせて試みたいけばよい。重複して同じものが出力される場合もあるが、その時は一つのものとして考えればOK

生成法がある場合の受理法

言語Lを受理する手続きを実現するMを構成するには、ある入力ωを受けたらL生成器でどんどんLの要素を作っていく。ωがL生成器によって生成されれば受理。非受理の場合は永久に出力しないので、これは手続きとなる。
簡単な話がLに含まれる入力を受理する手続きを作っているだけ。