非専門的シンギュラリティー研究所

無限に動き続けるシステムを表す方法を AI なども使って考えていきます。

証明路開発支援システム(5)

操作方法

証明路の画面は「直進地点」または「分岐地点」が「通路」で連結されて表示されています。上下左右のキーで操作し、ゴールに到達すれば終了です。最も下に表示された「直進地点」または「分岐地点」を操作することができます。

「直進地点」の操作

「直進地点」では以下の操作ができます。

  • 「↓」キーで次に進みます。(次に進めるとき)
  • 「↑」キーで前に戻ります。(戻れるとき)
「分岐地点」の操作

「分岐地点」では以下の操作ができます。

  • 「←」キー・「→」キーで次に進む道を選択します。(選択肢が複数あるとき)
  • 「↓」キーで次(選択した道)に進みます。
  • 「↑」キーで前に戻ります。(戻れるとき)

表示の内容

最初は以下のように表示されています。これは「直進地点」です。

直進地点(スタート)

「↓」キーで以下の表示になります。最も下にあるのは「分岐地点」です。この「分岐地点」を操作することができます。

分岐地点(問題の選択)

「↓」キーを何回か入力すると、以下のような表示になります。最も下にあるのは「直進地点」です。この「直進地点」を操作することができます。最も下の「直進地点」は異なる色で表示されます。

直進地点

「↓」キーで以下の表示になります。最も下にあるのは「分岐地点」です。この「分岐地点」を操作することができます。最も下の「分岐地点」は異なる色で表示されます。

分岐地点

「↓」キーを何回か入力すると、以下のような表示になります。「p | a」が成立したので「p | a」を選択する地点に戻ります。「p | a」は異なる色で表示されます。

条件が成立したとき

「↓」キーを何回か入力すると、以下のような表示になります。すべての条件が成立するとゴールに行きます。

ゴール

証明路開発支援システム(4)

MazeState クラスを書き直します。

MazeState クラス

それまでたどってきた事象をつなげたものをパスと呼びます。画面にはパスが表示されます。

「前進モード」と「選択モード」という状態があり、選択肢の間を移動しているときは「選択モード」になっています。それ以外のときは「前進モード」です。初期値は「前進モード」です。

下位のノードが存在するノードを「分岐ノード」と呼びます。「分岐ノード」の下位のノードは選択肢となります。下位のノードが存在しないノードを「直進ノード」と呼びます。

private bool inBranchMode (= false)

現在選択モードかどうかを表します。

public void MoveBackward()

パスの要素が2個以上のとき、最後の要素を消去します。

public void MoveForeward()

前進モードのとき
  • 分岐ノードのとき
    • 下位の選択可能なノードがあるとき
      • 下位の最初の選択可能なノードをパスに追加
      • 選択モードにする
    • 下位の選択可能なノードがないとき
      • 何もしない
  • 直進ノードのとき
    • 次の兄弟ノードがあるとき
      • 次の兄弟ノードをパスに追加
    • 次の兄弟ノードがないとき
      • 何もしない
選択モードのとき

下位のノードに進むことしかできず、下位のノードに進むと前進モードに戻るとします。

  • 分岐ノードのとき
    • 下位の最初のノードをパスに追加
    • 前進モードにする
  • 直進ノードのとき
    • 何もしない

public void MoveLeft()

前進モードのとき
  • 何もしない
選択モードのとき
  • 前の選択可能な兄弟ノードがあるとき
    • 前の選択可能な兄弟ノードで、パスの最後の要素を置き換える(変更があれば)
  • 最後の選択可能な兄弟ノードがあるとき(現在のノードがあるので必ずある)
    • 最後の選択可能な兄弟ノードで、パスの最後の要素を置き換える(変更があれば)

public void MoveRight()

前進モードのとき
  • 何もしない
選択モードのとき
  • 次の選択可能な兄弟ノードがあるとき
    • 次の選択可能な兄弟ノードで、パスの最後の要素を置き換える(変更があれば)
  • 最初の選択可能な兄弟ノードがあるとき(現在のノードがあるので必ずある)
    • 最初の選択可能な兄弟ノードで、パスの最後の要素を置き換える(変更があれば)

証明路開発支援システム(3)

クラスに分割したときの仕様です。これはまだ変更する可能性があります。

Env クラス

変数の現在の状態を表すクラスです。

public bool IsSelectable(string expstr)

ノードが選択可能であるかどうかを返します。expstr (この名前はわかりにくいので変更する予定)はノードのテキストの全体です。

public void SetNumber(string expstr)

変数に値を設定します。expstr (この名前はわかりにくいので変更する予定)はノードのテキストの全体です。

MazeState クラス

private bool inBranchMode (= false)

現在選択モードかどうかを表します。

public void MoveBackward()

前進モードのとき
  • 前の兄弟ノードがあるとき
    • 前の兄弟ノードに移動
    • 現在の表示とその上の道の表示を消す
  • 前の兄弟ノードがないとき
    • 何もしない
選択モードのとき
  • 上位のノードがあるとき
    • 上位のノードに移動
    • 現在の表示とその上の道の表示を消す
    • 前進モードに戻す
  • 上位のノードがないとき
    • 何もしない

public void MoveForeward()

前進モードのとき
  • 下位の選択可能なノードがあるとき
    • 下位の最初の選択可能なノードに移動
    • 現在の表示はそのまま
    • その下に道とテキストを表示
    • 前進モードに戻す
  • 下位の選択可能なノードがないとき
    • 何もしない
選択モードのとき
  • 選択ノード(下位のノードから選択するノード)のとき
    • 下位の選択可能なノードがあるとき
      • 下位の最初の選択可能なノードに移動
      • 現在の表示はそのまま
      • その下に道と選択候補テキストを表示
      • 選択モードにする
    • 下位の選択可能なノードがないとき
      • 何もしない
  • 選択ノード(下位のノードから選択するノード)ではないとき
    • 次の兄弟ノードがあるとき
      • 次の兄弟ノードに移動
      • 現在の表示はそのまま
      • その下に道とテキストを表示
    • 次の兄弟ノードがないとき
      • 何もしない

public void MoveLeft()

前進モードのとき
  • 何もしない
選択モードのとき
  • 前の選択可能な兄弟ノードがあるとき
    • 前の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 最後の選択可能な兄弟ノードがあるとき
    • 最後の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 前の選択可能な兄弟ノードも最後の選択可能な兄弟ノードもないとき
    • 何もしない

public void MoveRight()

前進モードのとき
  • 何もしない
選択モードのとき
  • 次の選択可能な兄弟ノードがあるとき
    • 次の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 最初の選択可能な兄弟ノードがあるとき
    • 最初の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 次の選択可能な兄弟ノードも最初の選択可能な兄弟ノードもないとき
    • 何もしない

class TreeData

public TreeData(string name)

コンストラクターです。ノードのテキストを設定します。name は名前が適切ではないので変更する予定です。

public void AddNode(TreeData node)

ノードを追加します。

public TreeData? GetNextSibling()

次の兄弟ノードを取得します。次の兄弟ノードがないときは null を返します。

public bool HasNextSibling()

次の兄弟ノードがあるかどうかを調べます。

public TreeData? GetPrevSibling()

前の兄弟ノードを取得します。前の兄弟ノードがないときは null を返します。

public bool HasPrevSibling()

前の兄弟ノードがあるかどうかを調べます。

public TreeData GetFirstChild()

下位の最初のノードを取得します。

public TreeData GetLastChild()

下位の最後のノードを取得します。

public bool HasChild()

下位のノードがあるかどうかを調べます。

public bool IsBranch()

「選択ノード」(下位のノードのどれかを選択するノード)かどうかを調べます。

public bool IsGoal()

ゴールかどうかを調べます。

public bool IsNumbered()

数値を設定するノードかどうかを調べます。

public bool IsSelectable(Env env)

選択可能な選択肢のノードかどうかを調べます。

証明路開発支援システム(2)

操作方法の仕様は以下のようになります。

操作方法

上下左右のキーで操作します。「前進モード」と「選択モード」があります。初期値は「前進モード」です。この操作で進んでゴールに到達すれば終了です。

前進モードのとき

下キー
  • 選択ノード(下位のノードから選択するノード)のとき
    • 下位の選択可能なノードがあるとき
      • 下位の最初の選択可能なノードに移動
      • 現在の表示はそのまま
      • その下に道と選択候補テキストを表示
      • 選択モードにする
    • 下位の選択可能なノードがないとき
      • 何もしない
  • 選択ノード(下位のノードから選択するノード)ではないとき
    • 次の兄弟ノードがあるとき
      • 次の兄弟ノードに移動
      • 現在の表示はそのまま
      • その下に道とテキストを表示
    • 次の兄弟ノードがないとき
      • 何もしない
上キー
  • 前の兄弟ノードがあるとき
    • 前の兄弟ノードに移動
    • 現在の表示とその上の道の表示を消す
  • 前の兄弟ノードがないとき
    • 何もしない
左右キー
  • 何もしない

選択モードのとき

下キー
  • 下位の選択可能なノードがあるとき
    • 下位の最初の選択可能なノードに移動
    • 現在の表示はそのまま
    • その下に道とテキストを表示
    • 前進モードに戻す
  • 下位の選択可能なノードがないとき
    • 何もしない
上キー
  • 上位のノードがあるとき
    • 上位のノードに移動
    • 現在の表示とその上の道の表示を消す
    • 前進モードに戻す
  • 上位のノードがないとき
    • 何もしない
右キー
  • 次の選択可能な兄弟ノードがあるとき
    • 次の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 最初の選択可能な兄弟ノードがあるとき
    • 最初の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 次の選択可能な兄弟ノードも最初の選択可能な兄弟ノードもないとき
    • 何もしない
左キー
  • 前の選択可能な兄弟ノードがあるとき
    • 前の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 最後の選択可能な兄弟ノードがあるとき
    • 最後の選択可能な兄弟ノードに移動
    • 現在の表示を消す
    • 選択候補テキストを表示
  • 前の選択可能な兄弟ノードも最後の選択可能な兄弟ノードもないとき
    • 何もしない

「証明路」ツリーの例

「証明路」ツリーは以下のようになります(これは動作が確認されたものではありません)。スペース1個のインデントで階層を表しています。

                 ◆問題を選択
                  整域で素元ならば既約元
                   ◆p は素元
                    ★既約元の定義
                     ◆p = ab とおく
                      ★素元の定義
                       素元の定義の仮定(p | ab)が成立
                       ◆<p | a>a1 または <p | b>a2 が成立
                        ▼a1p | a
                         ◆p | a
                          ★p | a の定義
                           a = pc と書ける
                           ◆p = ab = (pc)b = p(cb)
                            ★整域の定義
                             ◆両辺を 0 以外で割ることができる
                              ★素元の定義
                               p は 0 ではない
                            ★素元の定義
                             ◆p は 0 ではない
                              ★整域の定義
                               両辺を 0 以外で割ることができる
                           両辺を p で割ることができる
                           1 = cb
                           b は単元
                           =a1a が単元または b が単元
                        ▼a2p | b
                         ◆p | b
                          ★p | b の定義
                           b = pd と書ける
                           ◆p = ab = a(pd) = p(ad)
                            ★整域の定義
                             ◆両辺を 0 以外で割ることができる
                              ★素元の定義
                               p は 0 ではない
                            ★素元の定義
                             ◆p は 0 ではない
                              ★整域の定義
                               両辺を 0 以外で割ることができる
                           両辺を p で割ることができる
                           1 = ad
                           a は単元
                           =a2a が単元または b が単元
                        ▲a3ゴールへ
                         ■ゴール
                  UFDで既約元ならば素元
                   ◆p は既約元
                    ★素元の定義
                     ◆p | ab とおく
                      ★p | ab の定義
                       ◆pc = ab と書ける
                        ★UFDの定義(分解可能)
                         a=a_1…a_m、b=b_1…b_n、c=c_1…c_k と既約元の積に分解できる
                         ◆p・c_1…c_k = a_1…a_m・b_1…b_n
                          ★UFDの定義(一意性)
                           p は a_1,…, a_m, b_1,…, b_n のどれかと同伴
                           ◆p は <a_1,…, a_m のどれかと同伴>b1 または <b_1,…, b_n のどれかと同伴>b2
                            ▼b1p は a_1,…, a_m のどれかと同伴
                             p は a_1,…, a_m のどれかと同伴
                             p | a
                             =b1p | a または p | b
                            ▼b2p は b_1,…, b_n のどれかと同伴
                             p は b_1,…, b_n のどれかと同伴
                             p | b
                             =b2p | a または p | b
                            ▲b3ゴールへ
                             ■ゴール

証明路開発支援システム(1)

ゲーム・プログラミング(5) - 非専門的シンギュラリティー研究所」で証明を迷路のようにしたものを生成AIで作ってもらいましたが、迷路にはなっていないのですが改造すれば使えそうなものができたので、これを改造して使うことにしました。迷路とは言えないので「証明路」と呼ぶことにします。将来的にはテキストを入れ替えることによっていろいろな証明に対応できるようにしますが、今は

  • 整域において素元は既約元である
  • UFDにおいて既約元は素元である

ということの証明をたどることができるものになっています。

「証明路」は以下のようにツリーの形式に変更しました。このため、主要な部分は全面的に書き直しました。

「証明路」ツリーのテキストの形式

テキストの先頭に以下のような文字があるときは、ノードの種類を表します。先頭に何もないときは下位のノードは上から順に進むことを表します。

変数名、数値は1文字の文字列です。

選択

形式: ◆テキスト
下位のノードの一つを選択することを表します。

定義の引用

形式: ★テキスト
定義を引用することを表します。

ゴール

形式: ■テキスト
ゴールであることを表します。

変数の値の設定

形式: =vnテキスト
v: 変数名
n: 数値
v と n のビットごとの論理積を v に設定します。v に何も設定されていないときの値は 0 です。

選択可能条件(論理積)

形式: ▲vnテキスト
v: 変数名
n: 数値
v と n のビットごとの論理積が 0 ではないときこの選択肢は選択可能であることを表します。

選択可能条件(論理積の否定)

形式: ▼vnテキスト
v: 変数名
n: 数値
v と n のビットごとの論理積が 0 のときこの選択肢は選択可能であることを表します。

テキスト内部のハイライト

これはテキストの先頭ではなく任意の部分に書くことができます。
形式: <ハイライトテキスト>vn
v: 変数名
n: 数値
テキストにこの文字列を埋め込むと

  • v と n のビットごとの論理積が 0 ではないときハイライトされて表示されます。
  • v と n のビットごとの論理積が 0 のときはそのまま表示されます。

整数論パズル開発支援システム(1)

「フェルマーの小定理」を証明するプログラムを作るシステムについて以下の記事で考察してきました。

ビジュアルプログラミング(29) - 非専門的シンギュラリティー研究所」では以下のプログラムの説明をしています。

  • 環の演算
  • 自然数の演算
  • ユークリッドの互除法・素因数分解・連立1次方程式

これらを改造して以下の機能を持つシステムを作ります。

  • 有理式と階乗計算機能(「多項式計算機能」を含む)
    • 「ユークリッドの互除法・素因数分解・連立1次方程式」のシステムを改造して階乗の計算に対応できるようにします。
  • 帰納法機能
    • 「自然数の演算」のシステムを改造します。
  • 環の演算機能
    • 「環の演算」のシステムを改造します。
  • 素数約数判定機能
    • これは今までのものには含まれていません。「エラトステネスのふるい」のシステムの判定方法と同様なので今後作成していきます。

「フェルマーの小定理」の別の証明では

  • 有限集合の元の個数を比較する機能
  • 群の逆元を求める機能

が必要になります。群論に関する機能を取り入れるかどうかは検討します。できればこれらの機能も取り入れていきます。

数学ゲーム(34)

フェルマーの小定理パズル(11)

数学ゲーム(24) - 非専門的シンギュラリティー研究所」、「数学ゲーム(25) - 非専門的シンギュラリティー研究所」で考察した証明の残りの部分を見ていきます。

「素数約数判定システム」、「帰納法システム」があるとします。

フェルマーの小定理の二項定理を使った帰納法による証明

素数に関して以下のことが成り立ちます。

  • (1) 素数  p で割り切れる  1 以上の整数  a a \ge p
  • (2)  a, b 1 以上の整数で  ab が素数  p で割り切れるならば  a p で割り切れるか、または  b p で割り切れる

二項定理より  p が素数、 k = 1, 2, \cdots, p-1 のとき
 \displaystyle c = \frac{p!}{k! \ (p-k)!}
は整数となります。 p \cdot (p-1)! = k! \cdot (p-k)! \cdot c となりますが、 k! \cdot (p-k)! p より小さい整数の積なので(1)、(2)より  k! \cdot (p-k)! p で割り切れません。よって(2)より  c p で割り切れます。

「素数約数判定システム」はこのようにある整数がある素数で割り切れるかどうかを判定することができるとします。

よって二項定理より任意の整数  n に対して
 (n + 1)^{p} \equiv n^p + 1 \pmod p
が成り立ちます。

  •  0^{p} \equiv 0 \pmod p が成り立ちます。
  •  n^{p} \equiv n \pmod p が成り立つならば、 (n (+ 1))^{p} \equiv n^p (+ 1) \equiv n (+ 1) \pmod p が成り立ちます。

「帰納法システム」により

  •  (0 (+ \forall n))^{p} \equiv 0 (+ \forall n) \pmod p が成り立ちます。

よって任意の自然数  n に対して  n^{p} \equiv n \pmod p が成り立ちます。