鍋あり谷あり

テーマを決めずに適当に書いています。

拡張切符問題

ここを読んでくださっているのか、有限手順の話が
http://pub.cozmixng.org/~the-rwiki/rw-cgi.rb?cmd=view;name=RHG%C6%C9%BD%F1%B2%F1%3A%3A%C5%EC%B5%FE+Sound+Stage
に追記された。ありがとうございます>誰?
遠慮なく引用すると:

有限手順の方法: a,b,c,dから四則演算でできるすべての式を列挙する。そのうちの4個の式を取ってきてそれらの式の値がそれぞれ1,2,3,4になったとすると4個の4元方程式がたてられる。その連立方程式の解(a,b,c,d)は有限個なのでそれらについて四則演算で1〜(51+1) をすべて作れるか確かめる。これをすべての連立4元方程式について試せばよい。

なるほど連立方程式か。
と。10分ほどは思っていたんだが、4個の4元方程式を連立させても整数解が無限個あることもある。
実際、1,2,3,4 をすべて作れる (a,b,c,d) は、無限個ある。例えば、(x,x+1,x+2,x+4) は、x の値によらず、1,2,3,4 を作ることができる。したがって、上記の方法では有限の手順にはならないと思う。

しかし。もっと大胆に

a,b,c,d から四則演算でできるすべての式を列挙する。そのうち 51 個の式を取り出し、それらの式の値が 1〜51 になったとすると、 51個の4元方程式が立てられる。その連立方程式に(a,b,c,d)=(1,2,5,8)以外の整数解があるかどうか調べればよい。

とすれば、有限の手順となる。方程式に無限個の解ができたとしても、それはそれで、否定的な結果を得ることができる。
現実的な時間内に終わる可能性が寸毫もないのが難点。
それと。ひとつの連立方程式を解くことそれ自体が有限の手順でできるのかどうかも不安である。一次方程式じゃないので、自明ではないと思う。