機械の種類と実行時間

現実機械、理想機械、超越機械がある。現実機械は無視、理想機械と超越機械の実行時間を考える。

• 命題Pに対して、超越機械による実行時間τ(P)は、τ(P) = 0

超越機械＝神 なので、あらゆる命題を瞬時に確定的に判断する。

理想機械は、次の特徴を持つ。

1. メモリー使い放題：メモリの上限値はない。
2. CPU使い放題：同時に幾つのCPUを動かしてもよい。
3. ターボブースト（オフィシャル・オーバークロック）し放題：任意の正整数nに対して、クロック周波数をn倍にできる。

理想機械上でのプログラミングは超富豪プログラミングになる。しかし、

1. 無限のメモリを一時に使い切る操作はできない。例：実数を正確に表現する能力はない。
2. 無限個のCPUを同時に動かすことはできない。例：すべての素数を一度に求めることはできない。
3. 無限倍のブーストはできない。有限時間かかる操作を0にはできない。無限時間かかる操作を有限にはできない。

上記の制限があるので、理想機械の能力は結局は現実機械とほぼ同じで、超越機械とは全く比較にならない。

理想機械の実行時間τは次のように計算する。τの値はN_∞ = N∪{∞}

1. τ(P∧Q) = max(τ(P), τ(Q)) （2CPU）
2. τ(P∨Q) ≦ max(τ(P), τ(Q)) （下限は min(τ(P), τ(Q))
3. τ(¬P) = τ(P)
4. τ(P⇒Q) = τ(¬P∨Q) ≦ max(τ(P), τ(Q)) （下限は min(τ(P), τ(Q))
5. τ(∀x∈X.P) = Σ(x∈E | τ(P(x))) （1CPU）
6. τ(∃x∈X.P) ≦ Σ(x∈E | τ(P(x))) （1CPU）

f(x)の計算時間をτ(f(x))とする（実際はfのオブジェクトコードをφとして、τ(φ)）と：

• f(x)↓ ⇔ τ(f(x)) ＜ ∞
• f(x)↑ ⇔ τ(f(x)) ＝ ∞

オールドドグマ（古い思い込み）とは次のことである。

• 理想機械は、超越機械と同じ能力を持つはずだ。（否定された）
• 人間は、理想機械以下の能力しか持たない。（保留）

事実としては、

• 現実機械は、理想機械以下の能力しか持たない。