Hypercomputation and Non-computable Functions

Ahmet Çevik
548 140


Hypercomputation is an infinite computation performed in finitely many steps. In this paper we review with a personal perspective, transfinite computability, also known as hypercomputation, non-computable functions, and hypercomputing models following two main approaches: Ordinal computation and relativistic physics. For this we consider infinite time Turing machines as a model of ordinal computability. We give some of the well known results regarding infinite time Turing machines and give a personal perspective on the notion of computability based on ordinal numbers. 

Full Text: