ヒルベルト第１０問題について

質問

この証明とは、

例えば、
ある２変数(x,y)方程式に対して
x,y≧100としたら計算が永遠に続き
解を有限回で判定出来ないから
否定的に証明された。

という事ですか？

それならば、
ある関数をフィボナッチや指数関数などにする必要性はあるのでしょうか？

回答No.2

stomachman · ベストアンサー

ANo1に付けられたコメントについてです。
「アピール」だの「指数関数」だの「フィボナッチ」とおっしゃるのが一体何のことだかよく分からないのは、おそらくお使いの用語が不正確だからでしょう。言葉（すなわち概念の区別）の正確さがことに重要な分野ですので、ご注意あれ。

お礼

何度か読んでやっと理解出来ました。

マニアックな質問なのに答えて頂き、本当にありがとうございました。

とても助かりました^^

回答No.1

stomachman

(1) 自然数の集合Xが枚挙可能（つまり、Xの要素をどんどんアウトプットするプログラムであって、Xのどの要素もいつかはアウトプットされる、そのようなプログラムが作れる）ならば、そのXに対して
「x∈X 　⇔ 　方程式P(x, y1,y2,...,yn)=0の整数解(y1,y2,...,yn)が存在する」
ということが成り立つような、整数係数の多項式P(x, y1,y2,...,yn)が構成できる。

(2) Xは枚挙可能であるがXの補集合c(X)は枚挙可能でないような、そういうXが存在する。

　以上を認めますと、(2)から、Xは枚挙可能でc(X)は枚挙可能でないようなXについて、x∈Xを判定するプログラムは作れない。（もし作れたら、c(X)も枚挙可能になるから。）
　すると、(1)により、そのようなXに対応するP(x,y1,....,yn)を考えると、各自然数xについてP(x, y1,....,yn)=0が整数解を持つかどうかを判定するプログラムは作れない。（もし作れたら、それはx∈Xを判定するプログラムであるから。）
　以上から、「あらゆる整数係数の多項式Pについて、P=0が整数解を持つかどうかを判定する」ということができるプログラムは作れない。かくて第１０問題は否定的に解決された。

というわけで、(1)と(2)を証明すればよろしい、というのが「普通の証明」のスジかと思います。（(2)は不完全性定理から出ます。）

　指数関数については、おそらくこういう話かと：
　整数係数の多項式は、指数の部分は定数でなくてはなりません。しかし、指数も変数であるような任意の方程式Q=0について「整数係数の多項式Pであって、方程式P=0は方程式Q=0と同じ整数解の集合を持つ」というPを構成する方法が分かっている。なので、たとえば
Q(n, x, y, z) = x^n+y^n-z^n
とすると、フェルマーの最終定理を「Q=0にn≧3の整数解はあるか」という問題に帰着させ、さらにこれをディオファントス方程式P=0に焼き直すことができる。つまり、フェルマーの最終定理をいきなりディオファントス方程式で表すのは大変だけど、（指数も変数であるような）Q(n, x, y, z)=0の形に表すのなら簡単で、そしてQををPに変換することは機械的にできる、という仕掛け。

補足

回答本当にありがとうございます！
とても助かっております。

これは、つまり
指数関数やフィボナッチもディオファントス方程式だよ
というアピールであって、
１０番目の否定的証明だけなら
指数関数を用いなくてもよかったという事でしょうか？