Skip to content
TheChatArchiveThe Chat Archive
o3-mini· OpenAIHugging 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 Qwenqwen3-235b-a22b-no-thinking’s answer.
  1. User

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

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

    1. 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.

    2. 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).

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