is there any hierarchy for many-one complete languages of re (re-complete languages)? how can we propose a categorization for these languages? depending on what measures?
how can we categorize m-complete languages of RE (recursive enumerable, re-complete)?
0
$\begingroup$
computability
-
0using a weaker reduction. – 2012-02-13
1 Answers
1
Under many-one reductions by arbitrary total computable functions, HALT is the prototypical re-complete problem. A common technique for showing that some problem is undecidable (though not usually expressed in these terms) is to show that it is re-hard by reduction from HALT.
Using a weaker class of allowed reductions may lead to fewer problems being complete, but HALT is still re-complete even under linear-time many-one reductions.
For some reason, this terminology is much less used (to the point of not being used at all) in computability than in complexity.