Anzeige
Erschienen in:
2022 | OriginalPaper | Buchkapitel
6. Semi-Recursiveness
verfasst von : George Tourlakis
Erschienen in: Computability
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This chapter introduces the semi-recursive relations \(Q(\vec x)\). These play a central role in computability. As the name suggests these are kind of “half” recursive. Indeed, we can program a URM M to verify membership in such a Q, but if an input is not in Q, then our verifier will not tell us so; it will loop for ever. That is, M verifies membership but does not decide it in a yes/no manner, that is, by halting and “printing” the appropriate 0 (yes) or 1 (no).
Can’t we tweak M into an M′ that is a decider of such a Q? No, not in general! For example, our halting set K has a verifier but (provably) has no decider! This much we know: having a decider for K means \(K\in \mathcal {R}_{*}\), and we know that this is not the case.
Since the “yes” of a verifier M is signaled by halting but the “no” is signaled by looping forever, the definition below does not require the verifier to print 0 for “yes”. In this case “yes” equals “halting”.
The chapter introduces a general reduction technique to prove that relations are not recursive or not semi-recursive according to the case. We prove the closure properties of the set of all semi-recursive relations and also the important graph theorem. We prove the projection theorem and also give a characterisation of semi-recursive sets as images of recursive functions. The startling theorem of Rice is included: all sets of the form \(A=\{x:\phi _{x}\in {\mathcal {C}}\subseteq {\mathcal {P}}\}\) are not recursive, unless A = ∅ or \(A={\mathbb {N}}\).