2005/12/14 志村先生

前回の話は、「自然数の有限列と自然数の対応」の話

	自然数の有限列と自然数を 1 対 1 に対応させる方法を考える
		# Godel の coding

	例
		2, 3, 0, 1 <-> 2^{2+1} 3^{3+1} 5^{0+1} 7^{1+1}
			# 1 を加えているのは 0 乗があると面倒なので..
				= ( 2, 3, 0, 1 )
					# 羃を書くのは大変なので、この表現にする

	# すると、この coding に関して、次のようなことが解る。

	x が有限列に対応する自然数かどうかを判定する原始帰納的関数が作れる
		Seq(x) : x が有限列に対応
	x が有限列に対応する自然数の時、
		lh(x) : 有限列の長さ
		(x)_i : 第 i 成分 ( ただし i < lh(x) )

	Seq(x), Seq(y) の時
		x * y : x が表す有限列に y が表す有限列をつなげて得られる有限列に対応する自然数
			# 自然数列に関する議論を全て、上の coding を利用して
			# 自然数の中だけで議論しようとするので、上記のような
			# 「もって、まわった」、表現になる。

		## この表現は面倒なので、以下では、省略して
		## 「有限列 x, y をつなげて得られる有限列を x*y とする」
		## などと表現することがある。

		[例]
			2, 0, 1       <-> x
			1, 3          <-> y
		の時
			2, 0, 1, 1, 3 <-> x * y = x \Pi_{i<lh(y)} pr(i+lh(x))^{(y)_i+1}

	Seq(x), Seq(y), i < lh(x) の時
		x が表す有限列の第 i 成分の所を y が表す有限数列で置き換える
		[例]
			2, 0, 1       <-> x
			1, 3          <-> y
			i = 1			# 自然数は 0 から始まることに注意
		の時
			2, 1, 3, 1
		# これも、実は、原始帰納的
		#	x の i 番目より前と、後の列を考え、その二つの間に y をつなげればよい。列の結合は、既に上でやっている。
		## i より前の列
		##	\Pi_{j<i} pr(j)^{(x)_j+1}
		##	\Pi_{i<j<lh(x)} pr(j-i)^{(x)_j+1}

	# 同様にして...

	自然数列に対応する自然な操作は、上記の coding を利用して、(色々と工夫は必要だが..)原始帰納的な関数をもちいて、自然数の操作で表現できる
		# 確かに、自然数上の操作で表現できるが直観的でないので、(できるならば..)可能な限り、自然数列の表現 ( こちらは、自然、直観的.. ) で行う
		## 自然数列と自然数を、上記の coding を利用して、「同一視」する

==

	自然数の有限列の有限列

		[例] ( 4 つの有限列からなる有限列 )
			1, 0, 3
			2, 1		<--> 2^{(1,0,3)+1} 3^{(2,1)+1 5^(3,0,0)+1 + 7^{(2)+1}
			3, 0, 0
			2

			# ここで、本当は、肩の数に 1 を加える必要はない ( なぜなら、自然数列を表す自然数は、0 より大きいので.. )

		この対応関係も、1 to 1 になっている

		# 対応関係をこのように考えたので、以前に利用した関数がそのまま利用できる

	x が有限列の有限列 <=> Seq(x) ∧ \forall i < lh(x) Seq((x)_i)

==

	自然数を葉に持つ有限木
		葉 i		<-> 2^{pr(i+1)}
					肩に素数がのるので、これ以上構造がない
					2 の羃が含まれないので、葉
		子 c_0, .., c_{n-1} <-> \Pi_{i<n} pr(i)^{c_0+1}

		# 対応が 1 to 1
		# 木に対する操作が、自然数上の原始帰納関数になる
		## この対応は、別にこれである必要はない。単に一つの例として挙げている。

==

	原始帰納的関数の定義を有限木で表す

	[原始帰納的関数の定義] は以下のようなものだった

		1. 初期関数
			z(x)=0
			s(x)=x'
			pr^n_i (x_1,..,x_n) = x_i

			# これは無限個ある

		2. 合成
			f(x_1,..,x_n) = h(g_1(x_1,..,x_n), .., g_k(x_1,..,x_n))

		3. 原始帰納法
			f(0,x_1,..,x_n)=g(x_1,..,x_n)
			f(x',x_1,..,x_n)=h(x,f(x_1,..,x_n),x_1,..,x_n)

			# 原始帰納法の定義は二種類あった、その内の一つを取る

	[対応]
		初期関数 z, s, pr^n_i にそれぞれ「適切」に自然数を対応させる
			# 対応関係は、実はどうでもよい
			## 「適切」というには、「以下の議論で変な事が起きないように..」ということ !!

			z <-> (0,0)
			s <-> (0,1)
			p^n_i <-> (0,n,i)

			# 0 を始めるのは、単に、「初期関数である」ことを示すためのタグ

			以下、右側の表現の詳細は本質的でないので、この右側の数を
				gn(z)
				gn(s)
				gn(p^n_i)
			などと表現する。

			# ここまでは、「記号」の表現方法
			## 次に、「関数の定義」をこの「木」を使って表現する

	[表現]

		定義 1 の表現
			初期関数が葉となる単独の木
				gn(z)
				gn(s)
				gn(p^n_i)
		定義 2 の表現
			gn(f) = 1, gn(h), gn(g_1),.., gn(g_k) を子とする木
		定義 3 の表現
			gn(f) = 2, gn(g), gn(h) を子とする木

			# 1 とか 2 は、これが、初期関数 ( 0 で始まった ) でないことを示すためのタグ

		# このようにすれば、これまで通り ( だが、はるかに大変ではあるが .. ) 次のような原始帰納的関数が作れる

		code(x)
			x は原始帰納的関数の定義を表す有限木に対応する自然数
		arity(x)
			x が原始帰納関数の定義の時、その関数の引数

	# ここで、次のような関数を考える。

		compute(x,y)
			# x が表す関数に y を適用してできる値
			code(x)
				x = gn(f) ( f は n 引数関数 )
			Seq(y)
				y = ( y_0, .., y_{n-1} )
			arity(x) = lh(y) ( = n )
		の時
			compute(x,y)=f( y_0, .., y_{n-1} )
		となる関数を 2 重帰納法を用いて定義できる

[定理]
	compute(x,y) は原始帰納的関数ではない
		proof)
			compute(x,y) が原始的帰納だとすると、
				n = gn( computer(x,x)+1 )
			となる n が存在する。
			定義により、
				compute(n,x)=compute(x,x)+1
			となる。
			ところが、ここで x は何でもよいので n を代入すると
				compute(n,n)=compute(n,n)+1
			となり、矛盾。

			# compute は原始帰納的関数における万能関数
			## この証明は、実は、対角線論法になっている

		# 元々、「原始帰納的」が狭いので、compute は食み出てしまった..
==

# この結果、拡張して、..

	より一般に、計算可能な関数に code を与えて、同様なことを考えるとどうなるか ?

	# 「計算できる」関数が十分に広いのに、そこから「食み出てしまう」ということは何がおきているのか ? を考えると...