ITTM

An infinite time Turing machine (abbreviated "ITTM") is a generalization of a Turing machine to infinite computation times, first described by Joel David Hamkins and Andy Lewis. They are based on infinite ordinals.

Ordinals

An ordinal number, as the name implies, is tied to the idea of order, in that there is always a "next" ordinal. For example, the smallest ordinal is 0, and the next ordinal is 1, then 2, etc. However, we are not limited to talking about the smallest ordinal bigger than one ordinal, but we can also talk about the smallest ordinal bigger than any ordinal in any set of ordinals (e.g. the set of natural numbers is a set of ordinals, thus there is a minimal ordinal bigger than every natural number - the smallest infinite/transfinite ordinal). The smallest infinite ordinal is denoted $\omega$. Ordinal variables are also typically denoted with Greek letters.

Ordinal arithmetic operates similarly but differently to regular arithmetic. For natural numbers, addition, multiplication, and exponentiation are defined as normal, and they act nearly the same for infinite ordinals. However, they don't always act the same; for example, addition and multiplication are non-communative, meaning $\alpha +\beta =\beta +\alpha$ and Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha \beta =\beta \alpha } aren't always true, as seen in $1+\omega =\omega \neq \omega +1$ and Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2\omega =\omega \neq \omega 2} . However, addition and multiplication are still associative as usual, and there is one-sided distributivity of multiplication over addition.

The proper class of all ordinals is typically denoted as Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\text{On}}} , ${\text{Ord}}$, or Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\text{ON}}} . Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\text{On}}} is not a set of ordinals, as if it were, there would be an ordinal greater than all ordinals, which is contradictary.

Definition

The original model by Hamkins and Lewis has three one-sided, two-color countably infinite tapes, called input, scratch and output tapes, and a single read-write head which reads one cell from each tape. (Models with one tape have been considered as well — surprisingly, they have been shown to be weaker. To our knowledge, tapes with more than two colors have not been explored.) The transition table takes into account (but not necessarily behaves in the same way) all three tapes simultaneously, and writes three at once. The scratch and output tapes are blank initially, and the input tape contains the input to the machine.

ITTMs have a particular state marked as the limit state. At each step, the ITTM proceeds normally with a timer Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t} starting at zero and incrementing at each step. If it does not halt for any $t<\omega$, at $t=\omega$ each cell on each tape is set to the supremum of that cell's symbol for steps Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t=0,1,2,\ldots } . In addition, the head is set to the leftmost position and the state is set to limit. The ITTM continues as before, and if it continues to Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t=\omega 2} without halting, the same thing happens with the supremum of the tapes for Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t=\omega ,\omega +1,\omega +2,\ldots } . In general, if the ITTM reaches a countable limit ordinal $\alpha$ without halting, at time Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t=\alpha } , it is set to the limit superior of the tapes at $t=\beta$ for all Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \beta <\alpha } . That is, a cell is set to 1 iff for all Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \beta <\alpha } , there is some step $\beta <\gamma <\alpha$ such that the cell was set to 1 at step Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t=\gamma } .

If the ITTM halts, the contents of the output tape at halting time are the output of the machine. If the ITTM does not halt, but after some point the output tape never changes, the output tape after that point is the eventual output of the machine. For both halting and non-halting cases, all of the configurations of the three tapes over the lifetime of the ITTM are the accidental outputs of the machine. It should be noted that outputs and eventual outputs are unique if they exist, but accidental outputs are not.

Formal definition

Formally, a two-color ITTM is a 5-tuple Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M=(Q,\delta ,q_{0},q_{H},q_{L})} with the following components:

• $Q$ is a finite, non-empty set of states.
• $q_{0}\in Q$ is the initial state.
• $q_{H}\in Q$ is the halting state.
• $q_{L}\in Q$ is the limit state.
• $\delta :(Q\backslash \{q_{H}\})\times \{0,1\}^{3}\rightarrow Q\times \{0,1\}^{3}\times \{L,R\}$ is the transition table. Each production has a non-halting state and three colors mapping to a state, three colors, and a movement.

Most definitions of the standard TM have a symbol designated as "blank," which is the only symbol that can appear infinitely many times on tape. ITTMs have no such restriction, since ITTM inputs and outputs can be infinitely large.

Configurations

This section defines configurations of the machine and how state transitions work. The semantics defined in this section are identical to those of an ordinary machine (albeit with three tapes).

A configuration of $M$ is a 3-tuple Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (p,\tau ,m)} where Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\in Q} is the current state of the machine, Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau :(\mathbb {N} \times \{0,1,2\})\rightarrow \{0,1\}} are the contents of tapes, and Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m\in \mathbb {N} } is the positions of the head. We use $C(M)$ to denote the set of configurations. We define $\to$ (a single computation step) as a binary relation over $C(M)$ as follows. We say that Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (p,\tau ,m)\to (p',\tau ',m')} iff the following are true:

• Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (p,(\tau (m,0),\tau (m,1),\tau (m,2)))=(p',(c_{0},c_{1},c_{2}),\Delta m)}
• For all $n\in \mathbb {N} ,i\in \{0,1,2\}$, Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau '(n,i)=\left\{{\begin{array}{lr}c_{i}&:n=m\\\tau (n,i)&{\text{otherwise}}\end{array}}\right.}
• $m'=\left\{{\begin{array}{lr}m+1&:\Delta m=R\\\max\{m-1,0\}&:\Delta m=L\end{array}}\right.$

It can be seen that $\to$ is a function; i.e., $(p',\tau ',m')$ is unique.

Input, output, and evolution

An input to an ITTM is simply a function Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle I:\mathbb {N} \rightarrow \{0,1\}} (meant to be the content of the first tape), and an initial contents for that input is Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau _{0}:\mathbb {N} \times \{0,1,2\}\rightarrow \{0,1\}} such that Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau _{0}(n,0)=I(n),\tau _{0}(n,1)=\tau _{0}(n,2)=0} . A computation of $M$ on an input $I$ is a function $U:\mu \rightarrow C(M)$ (where $\mu$ is a successor ordinal, or the class ${\text{On}}$) that satisfies the following properties:

• Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle U(0)=(q_{0},\tau _{0},0)}
• For all Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha +1\in \mu } , $U(\alpha )\to U(\alpha +1)$.
• For all limit ordinals Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha \in \mu } , Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle U(\alpha )=(q_{L},\tau _{\alpha },0)} where for all Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i\in \mathbb {N} \times \{0,1,2\}} , $\tau _{\alpha }(i)={\text{lim sup}}_{\beta <\alpha }\tau _{\beta }(i)$ where $U(\beta )=(\bullet ,\tau _{\beta },\bullet )$.
• If $\mu \neq {\text{On}}$, Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle U(\mu -1)=(q_{H},\bullet ,\bullet )} .

Halting, writing, and ITTM-computability

If $\mu \neq {\text{On}}$, then the machine is halting for $\tau _{0}$, and we call $\mu$ the halting time. Define the output of the computation as the function $H:\mathbb {N} \rightarrow \{0,1\}$, defined as Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle H(n)=\tau _{\mu -1}(n,2)} . It is not hard to show that this output must be unique.

If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mu ={\text{On}}} , then the machine is nonhalting for $\tau _{0}$. If there is some $H:\mathbb {N} \rightarrow \{0,1\}$ such that for all sufficiently large $\alpha$, $\forall n:\tau _{\alpha }(n,2)=H(n)$, then we say that the machine eventually writes Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle H} . It is not hard to show that eventual output is also unique if it exists.

For all $H:\mathbb {N} \rightarrow \{0,1\}$, if there is an Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha \in \mu ,i\in \{0,1,2\}} such that Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \forall n:\tau _{\alpha }(n,i)=H(n)} , we say that the machine accidentally writes Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle H} for the input. Accidental outputs are not unique.

The uniqueness of outputs and eventual outputs allows us to define the partial ITTM-computable functions and partial eventually-computable functions. A partial function Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} } is ITTM-computable iff there exists an ITTM $M$ such that $f(n)=m$ iff $M$ produces output $m$ with input $n$ (using an encoding scheme for natural numbers such as $\underbrace {11...1} _{n}00...$). A partial function Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} } is eventually computable iff there exists an ITTM $M$ such that $f(n)=m$ iff $M$ produces eventual output $m$ with input $n$.

ITTM ordinals

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 empty input (all zeros) has $\alpha$ as its output.
• An ordinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} is clockable iff an ITTM with empty input halts at time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} .
• An ordinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} is eventually writable iff an ITTM with empty input has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} as its eventual output.
• An ordinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} is accidentally writable iff an ITTM with empty input has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} as an accidental output.

(The first and last two 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):

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda} , the supremum of all writable ordinals
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma} , the supremum of all clockable ordinals
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \zeta} , the supremum of all eventually writable ordinals
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma} , the supremum of all accidentally writable ordinals

It has been shown that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \omega_1^{CK} \ll \lambda = \gamma < \zeta < \Sigma} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \omega_1^{CK}} is the Church-Kleene ordinal.

Encoding ordinals in bitstrings

To be able to read and write ITTM ordinals, we must specify an encoding scheme to represent ordinals with countably infinite bitstrings. Here is one such scheme:

• "1000..." encodes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0} .
• If string S encodes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha} , then the string "0" + S (where + denotes string concatenation) encodes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha + 1} .
• If strings Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_0,S_1,S_2,\ldots} encode Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha_0,\alpha_1,\alpha_2,\ldots} , then we interleave the strings into a new bitstring Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} according to the following scheme:
  • Start with every bit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} labeled "empty".
  • Write the bits of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_0} in every second bit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} .
  • Write the bits of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1} in every second remaining empty bit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} .
  • Write the bits of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_2} in every second remaining empty bit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} .
  • Repeat for all of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_i} .
  • Write "1" in the first bit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} .
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T} encodes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sup\{\alpha_i\}} .

Using this encoding, "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{01000...}} " represents 1, "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{001000...}} " represents 2, "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{green}{0001000...}} " represents 3 and so on.

Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{1}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{green}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{1}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{green}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{green}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{blue}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \color{red}{0}} Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \color {blue}{0}} Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \color {red}{0}} $\color {green}{1}$ Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \color {red}{0}} Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \color {blue}{0}} Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \color {red}{0}} Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 0} $\ldots$ represents $\omega$.

This is of course one of many possible encoding schemes, and within this scheme multiple bitstrings represent a single ordinal.