データ領域 (A26)

RSS練習問題

※この記事は「記事26」

プログラムで扱うデータの集合について述べます。ひとつ前の記事は読んでいるものとします。

内容：

高々可算集合

有限集合または可算無限集合を高々可算集合〈at most countable set〉といいます。「可算集合」を「高々可算集合」の意味で使う人もいます（檜山も、口頭では「可算集合＝高々可算集合」です）。高々可算集合の基本的な性質：

  1. 有限集合は高々可算集合である。（定義より明らかだけど。）
  2. Nは高々可算集合である。（定義より明らかだけど。）
  3. A, B が高々可算集合のとき A×B（集合の直積）も高々可算集合である。
  4. A1, A2, ..., An が高々可算集合のとき A1×A2×...×An（集合の直積）も高々可算集合である。（すぐ上の一般化）
  5. Aが高々可算集合、B⊆A のとき、Bも高々可算集合である。

さらに次も言えます。

  1. A, B が高々可算集合のとき A + B（集合の直和）も高々可算集合である。
  2. A1, A2, ..., An が高々可算集合のとき A1 + A2 + ... + An（集合の直和）も高々可算集合である。
  3. A1, A2, ..., （無限列） のAiが高々可算集合のとき A1 + A2 + ... （無限和）も高々可算集合である。
  4. A1 ⊆ A2 ⊆ ..., （増加する無限列） のAiが高々可算集合のとき \bigcup_{i=1}^{\infty} A_i も高々可算集合である。

これらを精密化した結果を次節で述べます。

列挙子付き集合

n∈N に対して、次の定義をしておきます。

  • N[n] := {k∈N | k < n}

不等号にイコールがないことに注意してください。N[n]は、区間記法では [0, n) と書けますが、実数区間ではないので区間記法は使いません。

  • N[0] = {} = ∅ = 0
  • N[1] = {0} = 1
  • N[2] = {0, 1} = 2 = B （Bは「ブーリアン」から）
  • N[3] = {0, 1, 2}
  • ...

記号'∞' に対しては、

  • N[∞] := N

とします。

集合Xがあり、適当なn（n = ∞ も認める）に対する f:N[n]→X が全単射のとき、fをXの列挙子〈enumerator | iterator〉または列挙関数〈enumerating function〉と呼びます。全単射ではなくても、全射であれば十分ですが、議論が面倒になるので全単射を要求しておきます。全単射の要求がかえって邪魔になることもあります（一長一短）。集合の基数の定義から、列挙子を持つ集合は高々可算無限集合です。

集合Xとその列挙子fの組 (X, f) を列挙子付き集合〈set with enumerator〉と呼びます。列挙子付き集合から新しい列挙子付き集合を構成できます。以下に出てくる「述語」は、述語記号ではなくて、述語関数＝値が二値であるほんとの関数のことです。

  1. 有限集合は列挙子を持つ（列挙子を具体的に作れる）。
  2. Nは列挙子を持つ。id:N→N を標準的列挙子とする。
  3. (A, f), (B, g) が列挙子付き集合のとき A×B（集合の直積）は列挙子を持つ。
  4. (A1, f1), (A2, f2), ..., (An, fn) が列挙子付き算集合のとき A1×A2×...×An（集合の直積）も列挙子を持つ。
  5. (A, f) が列挙子付き集合、B⊆A かつ B を定義するA上の全域述語があるとき、Bは列挙子を持つ。

また：

  1. (A f), (B, g) が列挙子付き集合のとき A + B（集合の直和）も列挙子を持つ。
  2. (A1, f1), (A2, f2), ..., (An, fn) が列挙子付き集合のとき A1 + A2 + ... + An（集合の直和）も列挙子を持つ。
  3. (A1, f1), (A2, f2), ..., （無限列） のAiが列挙子付き集合のとき A1 + A2 + ... （無限和）も列挙子を持つ。
  4. A1 ⊆ A2 ⊆ ..., （増加する無限列） のAiが列挙子付き集合で、Aiを定義するAi+1上の全域述語があるとき、 \bigcup_{i=1}^{\infty} A_i も列挙子を持つ。

新しく作った集合に対する列挙子の作り方は一意的ではありませんが、「こう作る」と決めれば、集合の構成法ごとに、列挙子付き集合を具体的に構成することが出来ます。

列挙子付き集合の別な見方

集合Aが可算無限集合のときは、列挙子付き集合を別な形で定義できます。特定の要素 i∈A と、写像 s:A→(A＼{i}) が指定されていて、sが可逆なとき、(A, i, s) をサクセッサ付き集合〈set with successor〉と呼びます。sをサクセッサ、sの逆写像 p:(A＼{i})→A をプレデセッサ〈predecessor〉と呼びます。

Aが有限集合のときは、終端記号'$'を追加してサクセッサを定義できます。

  1. s:A∪{$}→A∪{$}
  2. s($) = $ （終端記号の次はないのでループ、エラーにする案もある）

プレデセッサは、p:(A＼{i})∪{$}→A です。終端記号がある分、可逆性が歪んで複雑化しますが、無限集合のときと同様にサクセッサ付き有限集合を定義できます。

i∈A を要求しているので、サクセッサ付き集合は空ではありません。高々可算集合Aが空でない場合は、Aの列挙子とAのサクセッサは1：1に対応します。別な言い方をすると、列挙子付き集合とサクセッサ付き集合は同じとみなしてかまいません。

データ領域

データ領域に関する多少立ち入った議論をします。面倒なら、飛ばし読みでもいいです（読み飛ばし≠飛ばし読み）。

人やコンピュータが計算の対象にできるモノ（＝データ）全体の集合を計算的データ領域〈computational data domain〉、あるいはより短くデータ領域、さらにもっと短く領域とも呼びます。データ領域の定義は、目的により、好みにより、人により色々ありますが、ここでは、列挙子とタプリング写像を持つ集合として定義します。列挙子は既に述べました。

データ領域を単に集合として定義するのは無理で、プログラミングシステムの組み込み関数〈基本関数〉と共に定義することになります。データ領域は、プログラミングシステムと共にあるのです*1。

実用性を持つデータ領域／組み込み関数をチャンと定義するのは面倒（相互再帰的定義が山のように登場）なので、詳細は割愛して大雑把に述べます。

Dをデータ領域とすると、B = (二値の集合) = {0, 1} ⊆ D であり、システムに組み込みの全域述語（Bに値を持つ全域関数）がいくつか準備されているとします。組み込み述語から、プログラミング言語の手続き定義機能を使って新しい述語を定義できます。定義した述語手続き（名前付きプログラム）は、実行環境の上で実行して述語関数（数学的なB値部分関数）を定義します。

Dは可算無限集合として*2、Dの部分集合Xが、全域計算可能述語関数pにより

  • X = {x∈D | p(x) = 1}

と定義できるとき、計算的に確定する〈決定可能な〉部分集合〈computationally fullly-decidable subset〉 -- 長いので確定的部分集合〈decidable subset〉と呼びます。ほとんどの関数が計算可能ではないのと同様に、ほとんどの部分集合は確定的部分集合ではありません。データ領域の確定的部分集合は、プログラミング言語の“型”の領域として使えます。

さて、データ領域の条件として、タプリング写像を持っていることを要求します。これにより、n引数（n = 0, 1, 2, ...）のプログラムを一律に1引数のプログラムとして扱えます。タプリング写像の具体例は、この節の最後にあります。

タプリング写像〈tupling map〉とは、

  • t0:D0→D
  • t1:D1→D
  • t1:D2→D
  • t1:D3→D
  • 以下同様

という写像の列 t0, t1, t2, t3, ... で：

  1. すべての tkは、当該のプログラミングシステムの計算可能関数である。
  2. すべての tk:Dk→D が単射である。
  3. すべての tkの像集合 tk(Dk) は確定的部分集合である。
  4. tk(Dk) 上で定義されたk個の計算可能関数 πk, 1, πk, 2, ..., πk, k で、タプルの成分を取り出すことができる。写像 πk, i は、タプリング写像に対する射影〈projection〉と呼びます。

tk と πk, 1, πk, 2, ..., πk, k の関係は：

  • πk,i(tk(x1, x2, ..., xk)) = xi

簡略化のために次の記号を使います。

  • t0() = t0(()) = <>,
    t0(D0) = D<0>
  • t1(x) = t1((x)) = <x>,
    t1(D1) = D<1>
  • t2(x1, x2) = t2((x1, x2)) = <x1, x2>,
    t2(D2) = D<2>
  • t3(x1, x2, x3) = t3((x1, x2, x3)) = <x1, x2, x3>,
    t3(D3) = D<3>
  • 以下同様
タプリング写像と成分取り出し〈射影〉写像の例

D = N で、tk:Nk→N を以下の箇条書きのように定義します。piはi番目の素数、p1 = 2, p2 = 3, ... などとします。nを素因数分解したときの pi の肩に乗る指数を γi(n) で表します。0, 1以外のnは、n = p1γ1(n)×p2γ2(n)×...×pkγk(n) （γk(n) > 0）のように書けます。nごとにkは確定します。

  • t0() = <> := 0
  • tk(n1, ..., nk) = <n1, ..., nk> := p1n1 + 1×p2n2 + 1×...×pknk + 1
  • i ≦ k ⇒ γi(n) > 0 である素因数分解を持つ整数nはタプリングの像となっている。タプルの長さkは、素因数分解に現れた素数の個数により与えられる。
  • πk, i(n) := γi(n) - 1

次の関係があります。

πk, i(<n1, ..., nk>) = ni

データの検索

データ領域の部分集合Xで次の条件を満たすものを型領域〈type domain〉と呼ぶことにします。「型領域」は一般的な言葉ではありませんが、プログラミング言語のデータ型に相当する集合です。

  1. Xは確定的部分集合である。つまり、計算可能な全域述語関数でXへの所属（'∈'の真偽）を確実に判断できる。
  2. Xは列挙子fを持っている。したがって、(X, f) は列挙子付き集合になる。

型領域の定義より：

  1. データ領域D（全体集合）は型領域である。
  2. 空集合は型領域である。

現実のプログラミングでは意外と使われてないのですが：

  1. X, Y が型領域なら、X∩Y は型領域である（型領域にできる）。
  2. X, Y が型領域なら、X∪Y は型領域である（型領域にできる）。

X, Y に対して、

  • X\otimesY := t2(X×Y)

とすると、X\otimesY⊆D。集合としては、X\otimesY \stackrel{\sim}{=} X×Y。X\otimesY への所属を判定する全域述語と、列挙子を構成可能なので、X\otimesY も型領域になります。X\otimesY と X×Y は、気持ちの上では同一視してもかまいません。

我々のプログラミング言語と実行環境に、次の機能を要求します。

  • 型領域X上では全域である述語関数pに対して、Xの要素xで p(x) = 1 となるものを探すことができる。

上記の検索を行う構文を

  • find 変数 in 型領域 st (変数に関する論理式、述語を表す式)

とします。

例えば、D = N として Even⊆N は偶数の集合とします。このとき例えば、

  • find n in Even st n2 = 144

は、偶数のなかで144の平方根を探すものです。次も同様です。

  • find n in Even st n2 = 225

このような検索を可能とするために、データ領域と型領域に列挙子（またはサクセッサ）の存在を要求したのです。

上記のfind構文のプログラムは、最初に見つかったデータを値として出力します。例えば、

  • E("find n in Even st n2 = 144", ()) = 12
  • E("find n in Even st n2 ≧ 50", ()) = 8

データが見つからない場合は、永久に探し続けて無限走行します。

  • E("find n in Even st n2 = 225", ()) = ⊥

データ検索をするfindは、演算の組み合わせを超える唯一のプログラミング機能です。findは、存在限量子を計算的に実現するメカニズムです。超越的な（普通の）数学では、存在命題の真偽は神様のレベルで決まっていますが、計算的にはみつかるまで探すしかないのです。これが、超越的（普通の）真偽判定と、計算的（システムで実行する）真偽判定の大きな違いです。

*1:データ領域を単体・単独で定義はできません。他の集合や写像と一緒に、関係性によって定義されます。「生成系を持つ圏のなかで計算万能性を持つ対象」がデータ領域のモダンな定義です。

*2:データ領域Dが有限集合では、まともなプログラミングは出来ません。

プログラミングシステム (A25)

RSS練習問題

※この記事は「記事25」

実用的な（意味のある）演繹システムは、その一部としてプログラミングシステムを含んでいます。プログラミングシステムはプログラミング言語を持ちます。プログラミング言語には、完全に抽象的・概念的な数学的形式言語（例：ラムダ計算の言語）から、現実に使われている実在プログラミング言語、その中間にある疑似プログラミング言語など様々です。

内容：

データ領域とプログラム

プログラミング言語で扱うすべてのデータの集合をデータ領域〈data domain〉といいます。データ領域は、単なる集合ではなく、色々な条件を満たす必要がありますが、とりあえずは集合としましょう。データ領域の簡単な、そして理論的な話で一番よく使われる例は N = {0, 1, 2, ...} です。一般的な話では、D と表すことにします。

「プログラム」という言葉も解釈が多様で、多義語・曖昧語ですが、ここでは： プログラム〈program〉とは、特定のプログラミング言語〈programming language〉で書かれたテキスト（よく「コード」という）で、数学的な関数を表現するものだとします。（通常の曖昧な用法に比べて、「プログラム」をとても限定的に定義しているので注意。）

プログラムで表現される関数は、次の形をしています。

  • f:X1×...×Xn⊇→Y
  • X1, ..., Xn, Y ⊆ D

ここで、'⊇→' は、関数が部分関数〈partial function〉であることを示します。部分関数は、関数値が未定義であることを許す関数です。計算科学で「関数」と言ったら（デフォルトで）部分関数のことだと思ってください。通常の数学的な関数を意味したいときは、全域関数〈total function〉と呼びます。

プログラムがエラー・例外・無限走行などで値を出さない〈結果を返さない／戻さない〉とき、値は⊥〈ボトム〉だとみなすと、部分関数を排除できます。⊥を使えば、プログラムで表現される関数は、次の形をしています。

  • f:X1×...×Xn→Y∪{⊥} （全域関数）
  • X1, ..., Xn, Y ⊆ D

次の2つのやり方は一長一短があり、選択は趣味的です。檜山は両方使います。

  1. 部分関数を使う。
  2. 異常値を表す⊥〈ボトム〉を使う。

Pがプログラム（プログラミング言語で書かれたテキスト〈コード〉）だとすれば、それは関数（部分関数、同じことだが値に⊥を許す関数）を表すので、その関数を 〚P〛 と書きます。プログラムPと関数〚P〛を区別しましょう。絶対に区別しましょう。何があっても区別しましょう。

〚P〛:X1×...×Xn→Y∪{⊥} のとき、X1をPの第1引数領域〈first argument domain〉、…、XnをPの第n引数領域〈n-th arugument domain〉、Yを戻り値領域〈rturn-value domain〉と呼びます。「引数」「戻り値」はプログラマ達の方言〈ジャーゴン〉です。

任意の関数 f:X1×...×Xn→Y∪{⊥} が、対応するプログラムを持つわけではありません。むしろ、ほとんどの関数はプログラムを持ちません。そのことは、集合の基数に関する議論から分かります。Dが可算無限なら、D→D の関数の全体は非可算無限になります。プログラム（コード）は可算無限個しかないので、すべての関数を表現するのは無理です。

P \mapsto 〚P〛 は一意対応ですが、関数fに対して、それを表すプログラム（があるとして、それ）はたくさんあります。次の状況を考えれば明らかでしょう。

  • 優秀な（正しいプログラムを書く）10人のプログラマが、正確な仕様を与えられてプログラムを書きました。それらを、P1, P2, ..., P10 とします。これらのプログラムは（字面として）同じでしょうか？

「プログラム（のコード） → 関数」という対応も関数〈写像〉ですが：

  1. 全射ではない。プログラムで表現できない関数がある。めちゃくちゃイッパイある。
  2. 単射ではない。関数を表現するプログラムはひとつとは限らない。

別な言い方をすると：

  1. どんな関数でもプログラムで表現できると思うな！
  2. 関数を表現するプログラムがひとつだと思うな！

実行環境と走行

プログラム（のコード）に名前を付けたものを、ここでは手続き〈procedure〉と呼びます。普通は、これも「関数」と呼びますが、数学的な関数と区別するため「手続き」にします。

手続きの集合（有限集合）をライブラリ〈library〉と呼びます。ただし、同じ名前が2個以上現れてはいけません。メカニズムをプログラマの言葉で言えば、手続き名をキーにしてプログラムを引ける辞書〈ディクショナリ | ハッシュマップ〉がライブラリです。

プログラミング言語はライブラリにより機能拡張できます。組み込み手続き以外に、ライブラリで定義された手続きを使ったプログラミングができます。プログラムPがライブラリLを前提に書かれているとき、PはL上のプログラム〈program over L〉といいます。モジュール、パッケージなどは、ライブラリを組織化するときの単位を意味します（今は組織化は不要）。

書かれたプログラム〈テキスト | コード〉は、そのままでは単なる文書（特殊な言葉で書かれた読み物）に過ぎません。プログラムを実行する装置を、ランタイムシステム〈runtime system〉、エグゼキュータ〈executor〉、マシン〈machine〉、エンジン〈engine〉などと呼びます。ここでは、実行機械と呼びます。プログラムの実行〈execution〉は、走行〈run〉とも呼ばれます。

実行機械と走行の数学的な定式化（数学的なモデル）は：

  • E:ProgPL×D*→D∪{⊥} という写像〈関数〉
  • ProgPL は、プログラミング言語PLで書かれたプログラムの集合
  • D* = D0 + D1 + D2 + D3 + ...

D*とは、データのタプルの集合です。

  • D0は、何でもいいから単一要素の集合。単一要素に長さ0のタプル () をとることが多い。
  • D1は、長さ1のタプル (x) の集合。だが、D1はDと同一視して、D0 = D とする。
  • D2は、長さ2のタプル、つまりペア (x1, x2) の集合。
  • D3は、長さ3のタプル、つまりトリプル (x1, x2, x3) の集合。
  • 以下同様。
  • 足し算記号'+'は集合の直和を表す。とりあえずは、'∪'と同じだと思ってよい。

注意：DとD1を区別しないのは、通常のタプルに対する通常の数学の態度です。区別してもかまいません。また、後で出る（予定の）計算的タプリングでは、D1に相当する集合（D1そのものではないので、D<1>と書く）はまったく異なることになります。

n引数〈n-argument〉のプログラムPが関数fを表現していることは：

  • (∀)(x1, ..., xn)∈Dn.( E(P, (x1, ..., xn)) = f(x1, ..., xn) )

プログラムに対するスコットブラケットを使えば：

  • (∀)(x1, ..., xn)∈Dn.( E(P, (x1, ..., xn)) = 〚P〛(x1, ..., xn) )

プログラムおよび関数に対する引数型・戻り値型の指定である X1×...×Xn→Y をプロファイル〈profile〉と呼びます。実在のプログラミング言語の多くは、プログラム／手続きにプロファイルを指定できます。タチの良いプログラミング言語では、実行の前に、プロファイル違反（引数型違反、戻り値型違反）を構文的に判断できます。

実行前に引数プロファイル違反を検出できない場合も想定して、次を仮定します。

  • (￢)( (x1, ..., xn)∈X1×...×Xn ) (⇒) 〚P〛(x1, ..., xn) = ⊥

つまり、実行時・引数型検査が働きます。また、実行後の戻り値型検査を実行することにより、次も保証できます。

  • (x1, ..., xn)∈X1×...×Xn (⇒) (〚P〛(x1, ..., xn) ∈ Y) (∨) (〚P〛(x1, ..., xn) = ⊥)

プログラミング言語と実行機械は、ライブラリにより拡張できます。PがライブラリL上のプログラムのとき、裸の実行機械EにライブラリLをロード〈load〉した状態の実行機械を E(+L) とします。「ロード」はプログラマ方言です。プログラムP内でライブラリLに入っている手続きを呼び出し〈call〉たとき、呼び出された手続きも問題なく実行可能だというだけです。「呼び出し」もプログラマ方言で、手続きを実行することを擬人化した表現です。

裸の実行機械に、次の機能を加えた（抽象的な）装置を、プログラムの実行環境〈runtime environment〉と呼びます。

  1. 構文的または実行時の引数型検査
  2. 構文的または実行時の戻り値型検査
  3. ライブラリによる拡張（ライブラリを階層化して、いくらでも拡張できる）

これらの機能が内部的にどうやって実現されているかは、まったくのブラックボックスでかまいません。プログラマは実行環境の内部メカニズムを知る必要はありません。重要なのは、次の事実です。PはライブラリL上のプログラムで、プロファイルは X1×...×Xn→Y だとして：

  1. E(+L)(P, (x1, ..., xn)) = 〚P〛(x1, ..., xn) ←これ、超重要。
  2. (x1, ..., xn) ∈ X1×...×Xn ではないときは、どうせ正常終了しないので、考える必要はない。
  3. 正常終了して、E(+L)(P, (x1, ..., xn)) ∈ Y ではないことは起こらないので、考える必要はない。

プログラミング言語、データ領域、実行環境の全体をプログラミングシステム〈programming system〉と呼びます。歴史的経緯から、演繹システムの一部になっているプログラミングシステムを算術システム〈arithmetic system〉、または単に算術〈arithmetic〉と呼びます。ゲーデルをはじめ多くの人が使ったプログラミングシステムがホントの「算術」だったからです。

  • データ領域は、N = {0, 1, 2, ...}
  • プログラミング言語は、自然数論（≒算数）を形式化した形式言語〈人工言語〉
  • 実行環境は、自然数の計算が出来る抽象機械（概念的電卓）

本来の算術プログラミングシステムは低機能なので、プログラミングの難易度は高く、大規模なプログラムを書くのは大変です。実際に具体的に書き下す代わりに、理論的な結果（存在定理）を適宜使っても、それでも大変です。現存するプログラミング言語のような“高級言語”を使えば、ゲーデルが実装した算術ソフトウェアをもっと楽に実装できます。

プログラムと計算可能関数

プログラムPがライブラリL上で定義されていれば、ライブラリをロードした（ライブラリで拡張した）実行機械 E(+L) で実行できます。E(+L) をひとつの実行機械と考えて、E' = E(+L) と置けば、プログラムPは新しい実行機械E'で実行できる、と言えます。このため、ライブラリによる拡張にはイチイチ言及しないことにします。必要があれば、ライブラリを追加して実行環境をリッチにする、と考えます。現実のプログラミングシステムもそうなっています。プログラマは日常的に、自分のプログラミングシステムをライブラリ（モジュール、パッケージ）で拡張しています。

fをプログラムにより定義されている関数とします。つまり、

  • プロファイルが X1×...×Xn→Y であるプログラムPがある。（Pがひとつだけではないが、どれか選ぶ。）
  • (x1, ..., xn)∈Dn に対して、(x1, ..., xn)∈X1×...×Xn ならば、f(x1, ..., xn) = E(P, (x1, ..., xn))

このような関数を（当該のプログラミングシステムにおける）計算可能関数〈computable function〉と呼びます。

  1. fは、X1×...×Xnの外では定義されてない。X1×...×Xnに入らないデータを考える必要はない。
  2. (x1, ..., xn)∈X1×...×Xn であっても、f(x1, ..., xn) が未定義（値が⊥）なことはある。
  3. f(x1, ..., xn) ≠ ⊥ ならば、f(x1, ..., xn)∈Y は保証される。
  4. 数学の普通の関数との大きな違いは、引数領域に入っている「正しいデータ」を入力しても、正常な出力が得られない（エラー・例外、無限走行する）ことがあること。
  5. 計算可能関数 f(x1, ..., xXn) が値を持つ (⇔) プログラムPが、引数 (x1, ..., xXn) に対して停止〈正常終了 | terminate〉する。
  6. 計算可能関数 f(x1, ..., xXn) が値を持たない (⇔) プログラムPが、引数 (x1, ..., xXn) に対して停止しない。

ここで、「停止しない」は停止＝正常終了の否定を意味するテクニカルタームなので、国語辞書的に停止するプログラムが「停止しない」ことはあります。エラーで停止、例外で停止などの場合です*1。

計算可能関数の概念は、選んだプログラミングシステム（プログラミング言語／データ領域と実行環境）に依存します。が、経験上、ある程度の機能性を持つプログラミングシステムならば、計算可能関数のクラスは一致してしまうことが知られています。この事実を、（メタに）証明可能な命題として定式化することは出来てないので、現状では経験則です（予想でさえない）。（チャーチ／チューリングの提唱として3月に話した。）

余談： 計算可能関数の概念は、プログラミングシステムがなければ定義できません。しかし、定義のために選んだプログラミングシステムに依らないのです。計算可能関数は（プログラミングシステムに対して）相対的な概念ではなくて、絶対的・普遍的な概念なのです。これは、（檜山には）非常に不思議な現象で、「なんでそうなのか？」知りたいのですが、よく分かりません。漠然と、計算可能な関数を射とする圏（チューリング圏と呼んでいる人がいる）を公理化して、「すべてのチューリング圏は圏同値である」という命題を証明すればいいのかな、と思ってます。興味があれば、http://m-hiyama.hatenablog.com/entry/20181004/1538625265 も参照。

fが計算可能関数のとき：

  1. fが (x1, ..., xn) で、⊥でない値yを持つことを f(x1, ..., xn)↓= y と書く。
  2. fが (x1, ..., xn) で、⊥でない何らかの値を持つことを f(x1, ..., xn)↓ と書く。
  3. fが (x1, ..., xn) で、値が⊥であることを f(x1, ..., xn)↑ と書く。

記号「↓」は、「地に足が着いている」という意味（コジツケ）だそうです。「↑」は値が空に向かって飛んじゃうので発散＝停止しない、と。

fを表現するプログラムPを使って書けば：

  1. f(x1, ..., xn)↓= y (⇔) E(P, (x1, ..., xn)) = y かつ y ≠ ⊥
  2. f(x1, ..., xn)↓ (⇔) E(P, (x1, ..., xn)) ≠ ⊥
  3. f(x1, ..., xn)↑ (⇔) E(P, (x1, ..., xn)) = ⊥

あるいは：

  1. f(x1, ..., xn)↓= y (⇔) Pは (x1, ..., xn) に対して停止して、正常値yを返す。
  2. f(x1, ..., xn)↓ (⇔) Pは (x1, ..., xn) に対して停止する。
  3. f(x1, ..., xn)↑ (⇔) Pは (x1, ..., xn) に対して停止しない。

プログラムに関する形容詞「停止する／しない」を、対応する計算可能関数にも使って、次のようにも言います。

  1. f(x1, ..., xn)↓= y (⇔) fは (x1, ..., xn) に対して停止して、正常値yを返す。
  2. f(x1, ..., xn)↓ (⇔) fは (x1, ..., xn) に対して停止する。
  3. f(x1, ..., xn)↑ (⇔) fは (x1, ..., xn) に対して停止しない。

プログラムとそれが定義する関数を区別せよ！というモットーからすると好ましくない言葉使いですが、よく使われます。関数そのものではなく、関数の背後のプログラム実行に言及していることをお忘れなく！ テクニカルタームの解釈は、国語辞書的にボンヤリ・ナントナク考えるのではなく、定義に基づき解釈することが大事です。

*1:停止する「停止しないプログラム」という分かりにくい表現を避けるため、エラーや例外が発生したらすぐに無限ループに入る、と約束することができます。これなら、異常事態発生はすべて無限走行になります。

続・このブログについて

はてなブログ

ひとつ前の記事にて：

このブログは、「はてなドメイン」内で運用すると思います。とりあえず当面は、「ゲーデルの不完全性定理」ゼミの、補足説明、予習・復習用問題などを公開するために使います。よろしくお願いします。

となると、(保存用) 檜山正幸のキマイラ飼育記 メモ編 にある「ゲーデルの不完全性定理」ゼミ関連過去記事もこのブログに持って来たいところです。現時点でも、ブログからのエクスポート（Movable Type形式）が動くので、いったエクスポートして、必要な分だけこのブログにインポートすればいいでしょう。

が、そうすると重複コンテンツが生じます。このブログへのクロールを避けるために <meta name="robots" content="noindex" /> の設定はできるようですが、<link rel="canonical" href="XXXX" /> のほうが好ましいようです。でも、はてなブログの設定では記事ごとに異なるmetaタグは付けられません。

次の記事に、JavaScriptで無理やりmetaタグを後付けする方法があります。

本文内にscriptタグを埋め込む危なっかしい方法ですが、案の定、現在では使えません。今は、本文内のscriptタグはエスケープされてしまい実行はできません。

というわけで、インポートはあきらめます。まー、次のリンクでも十分でしょう。

このブログ「2nd飼育記」のデザイン・テーマは Block Memo を選んでみました。本編のデザイン・テーマは今んところ Report です。他では、Epic も良さそう。デザイン・テーマは気分で変えるかも知れません。デザイン・カスタマイズはサイドバーのリンクの削除だけ、スタイルシートの調整などはいずれボチボチ。[追記]何もしないときのデザイン・テーマは Life というやつらしい。[/追記]

本編「キマイラ飼育記」の「はてなダイアリー」からのインポート状況ですが：

インポートが進行中です。しばらくお待ちください。
なお、この画面を閉じてもインポートは進行します。
ただいまインポートが集中しており、記事の件数によっては完了するまでに数日以上かかる場合があります。

実際、プログレスバーで見ると（どうせ当てにならないだろうが）1/3程度。まだしばらくはかかりそうです。

インポート中でも新規記事の追加は問題ないようですが、気分的に落ち着かない感じがするので、新規はこの2nd飼育記に書くかも知れません（暫定的に）。

「(2nd) 檜山正幸のキマイラ飼育記」について

はてなブログ

長年使ってきたブログサービス「はてなダイアリー」が新サービス「はてなブログ」に統合される（＝「はてなダイアリー」は終了する）ことになったので、複数ブログの編成を変えて、はてなダイアリーに移行することにしました。

今まで2つのブログを運用してきて、その使い分けは：

  1. 檜山正幸のキマイラ飼育記 ： 一般（不特定多数）の読者を想定して書く。
  2. 檜山正幸のキマイラ飼育記 メモ編 ： 自分自身（檜山）のための覚え書きとして利用。一般読者は想定しない。

これら2つの旧ブログは、次の3つの新ブログになります。

  1. 檜山正幸のキマイラ飼育記 (はてなBlog) ： 旧「檜山正幸のキマイラ飼育記」の過去記事をすべてインポートする。そして、今までどおりに継続する。
  2. (保存用) 檜山正幸のキマイラ飼育記 メモ編 ： 旧「檜山正幸のキマイラ飼育記 メモ編」の過去記事をすべてインポートする。が、今後更新はせずに、原則として凍結。
  3. (新) 檜山正幸のキマイラ飼育記 メモ編 ： 新規にゼロからスタトート。だが、「メモ編」としての方針は変わらず、自分自身のための覚え書き。

メモ編を2つに分けた（分けざるを得なかった）のは、アカウントとブログの結び付きが昔とは変化したためです。その事情の説明は省略します。

URLに関しては、現状（2018年1月22日）「はてなドメイン」内ですが、インポートが完了した時点で別ドメイン（おそらくchimaira.org）に変更するかもしれません。

URLの変化に注目すると：

  1. 檜山正幸のキマイラ飼育記 ： http://d.hatena.ne.jp/m-hiyama/ ---(move to)→
    （http://m-hiyama.hatenablog.com/ または http://m-hiyama.chimaira.org/）
  2. 檜山正幸のキマイラ飼育記 メモ編 ： http://d.hatena.ne.jp/m-hiyama-memo/ ---(move to)→
    https://m-hiyama-memo.hatenablog.jp/（過去） ＋ （http://m-hiyama-memo.hatenablog.com/ または http://m-hiyama-memo.chimairag.org/）（今後）

以前は、本編とメモ編を別アカウント（m-hiyamaとm-hiyama-memo）にしてました（そうせざるを得なかったのです）が、今後は単一のアカウントm-hiyamaですべてのブログを運用します。その結果、メモ編にも有料オプション「はてなブログPro」の恩恵がいき渡ります（以前は、メモ編は無料サービス）。

さて、上記のごとくに2つのブログを使い分けてきて、今後も同様な使い分けをするつもりですが、最近になって中間的な用途も必要だと感じました。そこで第三のブログ＝このブログも新規に開設しました。

  • (2nd) 檜山正幸のキマイラ飼育記

このブログの用途は：

  • 本編＝メインブログ「檜山正幸のキマイラ飼育記」に入れるのはふさわしくないが、檜山個人のメモでもない内容を書く。
  • ブログ移行期間内の、臨時の公開場所として使う。

このブログは、「はてなドメイン」内で運用すると思います。とりあえず当面は、「ゲーデルの不完全性定理」ゼミの、補足説明、予習・復習用問題などを公開するために使います。よろしくお願いします。