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 computational complexity theory (and more precisely in computability theory), we classify functions or problems based on whether they can be computed or decided by algorithms, and if so, how efficiently.
Here's the terminology you're looking for:
1. A function/problem not in R:
- R is the class of recursive languages, i.e., decidable languages: those for which there exists a Turing machine that always halts and gives a correct yes/no answer.
- A function or language not in R is called undecidable.
✅ So, any function or decision problem not in R is referred to as undecidable.
2. A function/problem not in RE:
- RE (Recursively Enumerable) is the class of semi-decidable languages: there exists a Turing machine that halts and accepts inputs that are in the language, but may not halt on inputs not in the language.
- A problem not in RE cannot even be semi-decided by any Turing machine.
❌ There isn't a universally standard term like "undecidable" for this, but such problems are often described as:
- Not recursively enumerable
- Not semi-decidable
- Or informally, beyond semi-decidability
Sometimes people say a language not in RE is non-recursively enumerable.
Summary Table:
Class Name Informal Meaning R Recursive / Decidable Always solvable by an algorithm RE \ R Recursively Enumerable / Semi-decidable Can recognize "yes" answers, but might not halt on "no" Not in RE Non-RE / Not semi-decidable No algorithm can even semi-decide it
Example:
- The halting problem is in RE \ R — it's semi-decidable but undecidable.
- The complement of the halting problem is not in RE — it’s not even semi-decidable.
Let me know if you'd like examples or further clarification!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.