Ordinal computers

MaRDI QIDQ6500874arXivFDO

Authors Ryan Bissell-Siders

Mathematics Subject Classification ID

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

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.

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)