A cardinal register machine is like an ordinal register machine but with branching based on cardinal equality rather than ordinal equality. What is the complexity of the halting problem for cardinal register machines (with finite initial values in the registers)?
Is the complexity independent of whether
- at limits, the internal state is set to the initial state versus liminf (the registers always use liminf as ordinals)
- we can test for ordinal equality in addition to cardinal equality
- we have a copy instruction that allows copying register A into register B (without it, we may have to zero B first which affects liminf)?
Also, what if computations were restricted to countable length?
Ordinal register machines are a model of transfinite computation with a finite set of internal states and a finite set of registers that can store arbitrary ordinals. They are explored in "Computing the Recursive Truth Predicate on Ordinal Register Machines" by Peter Koepke and Ryan Siders.
For readers unfamiliar with ordinal register machines or wondering why we would want the restrictions above, the answer is that cardinal register machines have a natural definition that scarcely makes any use of set theory.
(Mostly) nontechnical definition:
A cardinal register machine is like a finite register machine:
* Finite internal state (i.e. finite set of internal states).
* Finite set of registers.
* The ability to
- halt
- zero a register
- increment: add a new element to a register
- test whether two registers have the same number of elements
but with a twist:
* The machine can run for a transfinite time. At limit steps,
- the internal state is set to the initial state
- each register keeps the elements added since the supremum of times it was zeroed.
Thus, each register stores a set of elements, with the ability to add a new element (elements are never repeated), remove all elements, and test whether two registers have the same (cardinal) number of elements. At every stage, an element is in a register iff it was added but not removed.
Now, if we label each increment with the ordinal stage when it occurred, then
- the order type of the set of increments in a register equals the ordinal for that register.
- adding an element increments that ordinal
- liminf behavior follows. Since we do not have a copy instruction, the only discontinuity is that if a register was zeroed cofinally often, it is zero in the limit.
This question is in Q/A format as I was able to solve it before posting (with countable length added later), but feel free to contribute additional answers. For example, an additional answer could have:
* More on bounded time computations.
* The minimum number of registers (and what happens with fewer registers).
* The spectrum of complexities of $Σ_1(\mathrm{Card})$ without the large cardinal assumption.