Fandom

巨大数研究 Wiki

コメント0

非万能チューリングマシン

万能でないチューリングマシンは任意の計算可能なシステムの物差しとなります、なかなか分かりづらいものさしですが。扱える状態や記号が多ければ多いほどより強力なシステムと同じ強さをもつようになります。

2-記号に固定し、その非万能チューリングマシンの強さを証明論で評価すれば可算順序数の、ZFC+巨大基数公理で評価すれば巨大基数のビジービーバー関数なるものが出来上がります。

非万能チューリングマシンで検索しても目当ての記事が出てこないのでここで自分なりに何とかします。別の名前で研究されてるのやも知らんが。

1-状態2-記号

停止するプログラムはどれも対称形になったり停止する位置が2マスずれたりするだけで全部同じ。

  • 型レベルでの自然数の定義;マシンが型を本格的に扱えるわけではない。
  • 加法;入力された一つの足し算を一度だけ。1+1=2 とかするだけ。
  • (最大値の設定;コンパイラの助けを必要とする。)

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


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

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

Fandomでも見てみる

おまかせWikia