The euclid abstract machine

• Autor(es): Mycka, Jerzy ; Costa, José Félix ; Coelho, Francisco
• Data: 2012
• Identificador Persistente: http://hdl.handle.net/10174/4078
• Origem: Repositório Científico da Universidade de Évora
• Assunto(s): Geometry; Computation
• Tipo de Documento: Artigo científico
• Idioma: Português

Descrição

Concrete non-computable functions are usually related to the halting function. Is it possible to present examples of non-computability, which are unrelated to the halting problem and its derivatives? We built an abstract machine based on the historic concept of compass and ruler constructions (a compass 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 purpose, the goal, and the meaning of computing beyond Turing.