In computational complexity theory how do you call a function not in R and a function…
- User
In computational complexity theory how do you call a function not in R and a function not in RE?
- Assistant
In computability theory the classes (R) and (RE) are usually thought of as follows:
-
(R) (Recursive): These are the decidable (or total computable) functions/languages. A language (or decision problem) in (R) has an algorithm (a Turing machine) that always terminates and correctly decides membership.
-
(RE) (Recursively Enumerable): These are the semi-decidable (or partially computable) functions/languages. A language in (RE) has an algorithm that will correctly list (or “recognize”) the positive instances, although it may run forever on negative instances.
Thus, when we talk about functions (or languages) not in these classes:
-
A function not in (R):
Such a function (or language) is called undecidable or non‐recursive. There is no algorithm which, given any input, will always correctly decide membership in a finite amount of time. -
A function not in (RE):
Such a function (or language) is called non‐recursively enumerable or sometimes unrecognizable. This means there is no algorithm that can even semi-decide membership (i.e., recognize positive instances) even if it were allowed to run forever on some inputs.
In summary:
- A function not in (R) is undecidable (or non-computable).
- A function not in (RE) is non-recursively enumerable (or unrecognizable).
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.