Turing-recognizable

Imagine a bouncer who lets in every member of a club correctly, but who, faced with a non-member, sometimes just stares at their ID forever and never says no. He never wrongly admits anyone and never wrongly turns a member away, but he can hang indefinitely on outsiders. A Turing-recognizable language is one some machine handles like that bouncer: it accepts every string that belongs, but on a string that does not belong it may either reject or simply loop forever.

Formally, a language L is Turing-recognizable if there is a Turing machine M such that M accepts (halts in q_accept) exactly the strings in L, and on every string not in L the machine either rejects or runs forever. The one promise is about members: every member is eventually accepted. The non-promise is about non-members: the machine is allowed never to give a definite no. So if you run M on a string and it accepts, you have learned the string is in L; but if it has not yet accepted, you cannot conclude it is not in L, because it might still accept later, or loop forever.

Turing-recognizable is the broadest natural class in this part of the theory, and it is strictly bigger than the decidable class: some languages are recognizable but not decidable, the universal language A_TM being the standard example. The older name is recursively enumerable (r.e.), because such a language is exactly one that some machine can list out, string by string, though not necessarily in order and not necessarily ever finishing. The honest punchline: recognizable is genuinely weaker than decidable precisely because of the permitted looping; semi-deciding a problem is real but limited progress.