Logic

INFORMATION

• Every abacus-computable function is Turing-computable.
  • Register/Block Correspondence
  • Three Procedures
    • n+ nodes
    • n- / e nodes
    • 微調整

• 詳細（テストつき）

• TM(Turing Machine)
  • Wikipedia "Busy Beaver" And this
  • for "Turing's World" users

• 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 num	new rgt num
       rewrite 0	scan 0	e(r)=0	tpl(l,q,r)
       rewrite 0	scan 1	e(r)=1	tpl(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. レジスター・ボックスをＴＭのテープと対応づける。
2. S+をTMプログラムに対応させる
3. S-を
4. 微調整（スタート地点の設定とか）

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

• Busy beaver problem for Turing Machine
• Productivity＝１の列の長さ
• 後回し

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

1. 関数f(x1, x2)を計算したとき、tステップ目は一意→　g(x1, x2, t)
2. Gから停止したとき状態がわかる。１がいくつ並んでいるかデコードして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はどのように変化するか
   • スキャンしているブロックの記号を０から１に書き換えたとき→rが1増える
   • ヘッドを一マス動かしたとき→場合わけ
3. 計算開始時と終了時のleft number とright number
4. 計算終了時のright numberからf(x1, x2)をdecodeする関数
5. 自然数の組を１つの自然数でコード化するための関数

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