Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b-no-thinking· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

In computational complexity theory how do you call a function not in R and a function…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o3-mini’s answer.
  1. User

    In computational complexity theory how do you call a function not in R and a function not in RE?

  2. Qwen 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:

    ClassNameInformal Meaning
    RRecursive / DecidableAlways solvable by an algorithm
    RE \ RRecursively Enumerable / Semi-decidableCan recognize "yes" answers, but might not halt on "no"
    Not in RENon-RE / Not semi-decidableNo 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!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.

Identical first prompt