0934132人目の素数さん垢版 | 大砲2017/11/09(木) 23:51:14.73ID:ZwpuOVPe チューリング完全だけどBBの2倍の状態を使う計算モデルを使った巨大数関数はΣ(n/2)になる。 つまりBBより増加が遅い。 入力 n に対して、なぜかΣ(n)-n^2個の無駄な状態を経ないと正しい値を出してくれない恣意的な計算モデルを使った巨大数関数はn^2になる。 でも計算モデルとしてはチューリング完全。 つまりいくらでも増加は遅くなるので >>932 は偽、かな。