The euclid abstract machine: Trisection of the angle and the halting problem - Coelho, Francisco (2012)
Concrete non-computable functions are usually re- lated to the halting function. Is it possible to present examples of non-computability, which are unrelated to the halting prob- lem and its derivatives? We built an abstract machine based on the historic concept of compass and ruler constructions (a com- pass construction would suffice) which reveals the existence of non-computable functions not related with the halting problem. These natural, and the same time, non-computable functions can help to understand the nature of the uncomputable and the pur- pose, the goal, and the meaning of computing beyond Turing.