07/09/19 20:09:17
>>434
f>gを示すために、h=f-gとして、すべての整数b>aに対して
h(b)>0となることを示すアルゴリズムを考える。
b>aが成り立つb1,b2,...を順番に代入する「代入アルゴリズム」
では、有限の計算において常にmax(b1,b2,...,bn)=Bが存在する。
したがって、すべてのd>cに対してh(d)<0であるようなc>Bが
存在する、すなわちf<gである可能性がある。また、B以上で
h(x)が正負を無限に振動するため、fとgの大小関係を決定でき
ない可能性もある。このように、代入アルゴリズムではf>gを
有限時間内に決定できない。
では、代入アルゴリズム以外であれば決定できるのか？
f>gを有限時間内に決定できる一般的なアルゴリズムは存在
しない様に思いますがいかがでしょう。