Towards a Theory of Infinite Time Blum-Shub-Smale Machines

摘要

We introduce a generalization of Blum-Shub-Smale machines on the standard real numbers R that is allowed to run for a transfinite ordinal number of steps before terminating. At limit times, register contents are set to the ordinary limit of previous register contents in R. It is shown that each such machine halts before time ω~ω or diverges. We undertake first steps towards estimating the computational strength of these new machines.