Minimality considerations for ordinal computers modeling constructibility

Abstract: We describe a simple model of ordinal computation which can compute truth in the constructible universe. We try to use well-structured programs and direct limits of states at limit times whenever possible. This may make it easier to define a model of ordinal computation within other systems of hypercomputation, especially systems inspired by physical models. We write a program to compute truth in the constructible universe on an ordinal register machine. We prove that the number of registers in a well-structured universal ordinal register machine is always ≥4, greater than the minimum number of registers in a well-structured universal finite-time natural number-storing register machine, but that it can always be kept finite. We conjecture that this number is four. We compare the efficiency of our program which computes the constructible sets to that of a similar program for an ordinal Turing machine. [Copyright &y& Elsevier]