FANDOM

KurohaKafka

こと 黒羽カフカ

ビューロクラット アドミン
  • 居住地 Japan
  • KurohaKafka

    順序数の整理

    2017年9月11日 by KurohaKafka

    C(C(Ω_2*2,0),0)=ψ_Ω(ψ_I(0))

    C(C(Ω_2*2+1,0),0)=ψ_Ω(ψ_I(ω)) C(C(Ω_2*2+C(Ω_2+C(Ω_2*2,0),0),0),0)=ψ_Ω(ψ_I(ψ_I(0))) C(C(Ω_2*2+C(Ω_2+C(Ω_2*2,0),0)+1,0),0)=ψ_Ω(ψ_I(ψ_I(0)*ω)) C(C(Ω_2*2+C(Ω_2*2,C(Ω_2+C(Ω_2*2,0),0)),0),0)=ψ_Ω(ψ_I(ψ_I(1))) 全文を読む >
  • KurohaKafka

    3次元

    高さn+1の行列は高さnの行列の行がどれだけ長いかを支配する高さ2の最初の行がω行目、つづいてω+1行目、ω+2行目、・・・高さ3の最初の行がω*2行目、・・・となる。

    (0,1(2)0,1)→(0,1(1)0,1(1)...(1)0,1)

    (0,1,1(2)0,1,1)→(0,1,1,2,...,n,n+1(2)0,1,0,1,...,0,1)

    全文を読む >
  • KurohaKafka

    ブーフホルツあまり関係ないけどまぁいいだろう。

    バシク行列の2次元の表現を、1次元の数列と入れ子構造、すなわち数列でラベルがつけられたヒドラツリーで表現する。

    バシク行列をそのままツリーに置き換えるやり方

    1行目の値でツリーをつくる。

    2行目以降の値はそれぞれの1行目の値が担う頂点に数列のラベルとして付け加える。

    2行でωを使わないブーフホルツのヒドラと同じ強さになる。

    (0,0)(1,1)=+(0(1))

    (0,0)(1,1)(2,1)=+(0(1(1)))

    (0,0)(1,1)(2,1)(1,1)=+(0(1(1))(1))

    (0,0,0)(1,1,1)=+(0,0(1,1))

    多次元空間上のツリー

    1行目の値で2次元上に広がるツリーを作る。

    n行目の値で、1行目の値が担う頂点をその値だけn+1番目の次元の方向に上げる。

    全文を読む >
  • KurohaKafka

    昔バシク行列の強さと計算可能性を計ろうとして失敗したシステム。


    情報とは、0と1の数列や物体の配列など、手段や媒体は何でもいいが、可算無限の意味を表すことができる表現である。

    任意の意味AとBにつき、AをBへ移す写像fが存在する。

    任意の意味Aにつき、Aを含むクラスが存在する。

    定義域Aの要素を値域Bの要素へ移す写像fはAとBどちらにも含まれない。

    任意の写像fにつきfについて閉じているクラスが存在する。

    以上のすべての意味を記述できる言語はいかなる関数も記述できるが、そのような言語は存在しない。

    (関数型言語はすべてを関数として表現する。関数にあちこち写される情報のあり方やデータ構造を重視するのがオブジェクト指向、たぶん)

    用意するもの

    環境 \(Γ\);

    すべての自然数とその型 \(0:M(0),1:M(0),2:M(0),\cdots\)

    ここではすべての自然数からなる集合をM(0)とする。

    後者関数とその型 \(m(1)::=λn.f(nfx):N→N\)

    多相関数 \(λx.nx:*→*\)

    ここで自然数 n がすでに多相的な扱いをされている。

    再帰 \(f(f)\)

    型推論

    \(\displaystyle \frac{Γ|-f:∀α.α→α\quadΓ|-x:A}{Γ|-f(x):A}\)

    m(n)変換

    \(m(n)\in M(n)\)

    \(M(n+1)::=M(n)→M(n)\)

    αが極限順序数のとき、

    \(M(α)::=\cup_{n0 として、

    \(m(α+n+1)::=λm.nm:M(α+n)→M(α+n)\)

    \(m(ω+2)m(ω+1)m(ω)(x)=f_{ε_0}(x)\)

    以上で m(ω^ω) つまり f[φ(ω,0)] まで計算可能

    m(n) 変換では多相化の範囲が有界であるため、λx.n ……


    全文を読む >
  • KurohaKafka

    入力を読み取るコンピュータそのものの仕組み、コンピュータに与えられる特定のプログラム、この両方からチューリング完全を解釈する。


    厳密で形式的に定義すると・・・

    計算可能とは、定義域内の0と1の有限の数列で表現可能な任意の入力に対して、1ステップずつ、あらかじめ定めた、字母集合となる有限の集合から選ばれる文字によって、有限の文字数で記述可能な規則=プログラムに則りながら、入力と同じく0と1の有限の数列で表現可能な部分的な結果を導き出し、最終的に有限時間内に全体の結果を導き出す(そして終了状態に入る)ことをいう。定義域が有限であれば、あらかじめすべての入力とそれに対応する出力を用意しておけばいいだけなのでただそれだけで計算可能である。

    反対に計算不可能とは、プログラムの長さ、または計算時間のいづれかがどうしても無限に長くなってしまうことをいう。


    メモリの座標、値、状態、遷移関数

    メタな視点からみて、関数を計算するためには、定義域と値域の要素すべてをそのプログラムを記述する言語で、それぞれ区別がつくように表さなければならない。

    例 自然数をあらわす原始的な方法

    まず、どんなプログラムにどんなコードでもかまいませんが、0にあたるコードを入力します。それで出力されたコードが1になります。0と同じコードになってしまったり計算が終了しなかったりする場合は、別のコードを0として入力しなおすなりプログラムを書きなおすなりします。
    1のコードを入力して出力されたコードが2のコードとなります。0または1とかぶってしまう場合や計算が終了しない場合は0のときと同じように対応します。
    2のコードを入力して出力されたコードが3となります。以下同様。

    例の例 チャーチ数

    プログラム λx.(λg.(λy.g(xgy)))
    λ ……


    全文を読む >

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。