Logic


INFORMATION

  • Every Turing-computable function is recursive.
    1. Wang Coding:
    2. lo(x):an ad hoc decoding function folloewed by 1st step
    3. tpl(x,y,z):the famous coding function
    4. flow graph, a(), q().
    5. g(x1,x2,t)
      • Basis, g(x1,x2,0)=tpl(0,1,S(x1,x2))
      • Induction, the following table corresponding to the acts; e(r)=e(rgt(g(x1,x2,t))=1/0.
        act; a(c,e(r))new lft numnew rgt num
        rewrite 0scan 0e(r)=0tpl(l,q,r)
        rewrite 0scan 1e(r)=1tpl(l,q,r-1)
        ...
    6. when the machine halts at t;
      • t is the least y s.t. ctr(g(x1,x2,y+1)=0 i.e. Mn[h](x1,x2)=t
    7. f(x1,x2)=lo(rgt(g(x1,x2,Mn[h](x1,x2)))).

日本語版

すべての原始帰納関数がabacus computableであることの証明
Abacus Machine

  • Adder
  • Lossless Adder
  • Multiplier
  • Abacusが関数f(x1, …, xr)を計算するとは?

Abacus computableな関数がTM computableである。
証明手順

  1. レジスター・ボックスをTMのテープと対応づける。
  2. S+をTMプログラムに対応させる
  3. S-を
  4. 微調整(スタート地点の設定とか)

生産性関数の諸定理の証明

  • Busy beaver problem for Turing Machine
  • Productivity=1の列の長さ
  • 後回し

Turing Computable FunctionがRecursiveであることの証明(最後)
方針

  1. 関数f(x1, x2)を計算したとき、tステップ目は一意→ g(x1, x2, t)
  2. Gから停止したとき状態がわかる。1がいくつ並んでいるかデコードしてfも。
  3. 自然数の組(x1, x2)→g(x1, x2, 0)→g(x1, x2 the step where the machine halts)→f(x1, x2)と辿ることで、f(x1, x2,)が合成関数として与えられる。
  4. もしgが帰納的関数であり、二番めのdecodingの手続きも帰納的関数で再構成できれば、fは帰納的関数。

コード化(Wang Coding)

  1. コード化の方法としてのright numberとleft number ブランクに0をあてて、記号列をnumeralにして、二進法でnumberにする。
  2. 基本操作に応じてright numberとleft numberはどのように変化するか
    • スキャンしているブロックの記号を0から1に書き換えたとき→rが1増える
    • ヘッドを一マス動かしたとき→場合わけ
  3. 計算開始時と終了時のleft number とright number
  4. 計算終了時のright numberからf(x1, x2)をdecodeする関数
  5. 自然数の組を1つの自然数でコード化するための関数

ultrafilterの存在定理(固有フィルターからのと、有限交差性からの)
PostのFunctional Completeness Theoremの証明

最新の20件

2007-09-04 2007-07-16 2007-03-20 2007-01-31 2006-10-06 2006-10-01 2006-09-22 2006-09-20 2006-08-30 2006-08-25 2006-08-21
  • Logic
2006-08-13 2006-08-12 2006-08-11 2006-07-28 2006-07-17

  • counter: 218
  • today: 1
  • yesterday: 0
  • online: 1