Finitary Reducibility on Equivalence Relations

• Main Authors: Miller, Russell, Ng, Keng Meng
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2016
• Subjects: Computable reducibility; Computability
• Online Access: https://hdl.handle.net/10356/84705; http://hdl.handle.net/10220/41955
• Institution: Nanyang Technological University

We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be Π_(n+2)^0-complete under comp...