Ordinal computers

arXivmath/9804076MaRDI QIDQ6500874FDOQ6500874

Authors: Ryan Bissell-Siders 

Abstract: Can a computer which runs for time $omeg{a}^2$ compute more than one which runs for time $omega$? No. Not, at least, for the infinite computer we describe. Our computer gets more powerful when the set of its steps gets larger. We prove that they theory of second order arithmetic cannot be decided by computers running to countable time.

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

This page was built for publication: Ordinal computers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6500874)