556 ページ

## 定義 編集

ITTMs are capable of producing far more outputs than ordinary TMs, including ordinals. This leads to several classes of ordinals:

• An ordinal $$\alpha$$ is writable iff an ITTM with trivial input can write $$\alpha$$ and immediately halt.
• An ordinal $$\alpha$$ is clockable iff an ITTM with trivial input halts at time $$\alpha$$.
• An ordinal $$\alpha$$ is eventually writable iff the output tape of an ITTM with trivial input ultimately converges to $$\alpha$$.
• An ordinal $$\alpha$$ is accidentally writable iff an ITTM with trivial input writes $$\alpha$$ at any step.

(The first three definitions can apply to many mathematical objects other than ordinals.) These definitions give rise to several large countable ordinals (the infinite time Turing machine ordinals):

• $$\lambda$$, the supremum of all writable ordinals
• $$\gamma$$, the supremum of all clockable ordinals
• $$\zeta$$, the supremum of all eventually writable ordinals
• $$\Sigma$$, the supremum of all accidentally writable ordinals

It has been shown that $$\omega_1^\text{CK} \ll \lambda = \gamma < \zeta < \Sigma$$[1].

## Fundamental sequences 編集

Fundamental sequences for these ordinals are reasonably simple to define, allowing use in FGH:

• $$\lambda[n]$$ is the supremum of all ordinals writable with ITTMs with at most $$n$$ states. The function $$f(n) = \lambda[n]$$ is in direct analogy with the busy beaver function.
• $$\gamma[n]$$ is the supremum of all ordinals clockable with ITTMs with at most $$n$$ states.
• $$\zeta[n]$$ is the supremum of all ordinals eventually writable with ITTMs with at most $$n$$ states.

It may seem that "the supremum of all ordinals accidentally writable with ITTMs with at most $$n$$ states" would produce a fundamental sequence for $$\Sigma$$. However, there exist "universal" ITTMs capable of accidentally writing all accidentally writable ordinals, so this definition has $$\Sigma[N] = \Sigma$$ for some finite $$N$$, which is clearly wrong.

## Encoding ordinals in bitstrings 編集

Here is a simple way to encode an ordinal in a countably infinite bitstring (read: output tape of a two-color ITTM):

• "1000..." encodes $$0$$.
• If string S encodes $$\alpha$$, then the string "0" + S encodes $$\alpha + 1$$.
• If strings $$S_0,S_1,S_2,\ldots$$ encode $$\alpha_0,\alpha_1,\alpha_2,\ldots$$, let $$T$$ be the string "0010120123012340123450123456...". Replace the instances of "0" in $$T$$ with successive characters of $$S_0$$, replace the instances of "1" with successive characters of $$S_1$$, and so forth, producing $$T'$$. The string "1" + $$T'$$, then, encodes $$\sup\{\alpha_i\}$$.

Note that the sequence "001012012301234..." is sufficient but not necessary. Any sequence consisting of infinite copies of every nonnegative integer will work. A computationally simpler alternative (albeit harder to understand) uses the fingerprint "0102010301020104010201030102010...", the ruler sequence.

## 値編集

### 単テープマシン編集

$$\gamma[1] = \omega^2$$

$$\gamma[2] ≥ \omega^3$$

$$\gamma[3] ≥ \omega^4$$

$$\gamma[4] ≥ \omega^5$$

...

$$\gamma[7] ≥ \omega^\omega$$

$$\gamma[22] ≥ \omega^{\omega2}$$

### 最高出力マシン編集

$$\gamma[1] ≥ \omega^4$$

$$\gamma[4] ≥ \omega^\omega$$

## 出典編集

1. http://www.maths.bris.ac.uk/~mapdw/pdw4.ps