かけ算の定義2

先日の「かけ算の定義」の続き。

2つの自然数の組を使うことで、整数の元が表現できる（参考： 整数(integer)）。自然数の組を使っているのだから、自然数の演算の有限回の適用で整数の演算もできることになる。また、逆元は組要素の入れ替えだけで求めることができる。

ちうことで、Schemeでプログラムにしてみる。自然数の定義および演算は先日のものを使用。

まず、与えられた任意の自然数 x∈N を正整数にする関数 int と、整数 x∈Z の逆元を求める関数 inverse。

(define (int x)
  (cons x e))

(define (inverse x)
  (cons (cdr x) (car x)))

負の数は正整数の逆元として定義する。

> (int three) ;; +3
(3 . 0)
> (inverse (int three)) ;; -3
(0 . 3)

そんで、加算、減算、乗算を定義。

(define (int-add x y)
  (cons (add (car x) (car y))
        (add (cdr x) (cdr y))))

(define (int-sub x y)
  (int-add x (inverse y)))

(define (int-mul x y)
  (cons (add (mul (car x) (car y))
             (mul (cdr x) (cdr y)))
        (add (mul (car y) (cdr x))
             (mul (car x) (cdr y)))))

ついでに、正規化元を求める関数 normalize

(define (normalize x)
  (if (or (eq? (car x) e)
          (eq? (cdr x) e))
    x (normalize (cons (pre (car x))
                       (pre (cdr x))))))

んでもって、1 * -1、-1 * -1 をやってみる

> (normalize (int-mul (int one) (inverse (int one))))
(0 . 1)
> (normalize (int-mul (inverse (int one)) (inverse (int one)))))
(1 . 0)

おけ。

自然数すごい

自然数が定義できると、整数も定義できることがわかる。コンピュータでは基本的に自然数しか議論しないし、ペアノの公理を改めて眺めてみてなんとなくBrainfuckに似ているなぁ・・・などということで、なんとなく感じていたが、どうやらペアノの公理はチューリング完全みたい（ペアノの公理は部分帰納関数で定義され、自然数は可算無限集合）。つまり、自然数の性質全般を扱える言語なり計算機械を作れば、チューリング機械が実現できるわけだ。逆に言えば、チューリング完全な系でないと自然数全般を扱えない。

自然数ってすげえ。

# はじめの議論とは違う方向になった。