Many important achievements of formal logic have been concerned with the discovery of incomputability—and thus firmly rooted in the undecidability of the halting problem and its complement. Also, the latter produce influental examples of $\Sigma^0_1$- and $\Pi^0_1$-complete sets, in modern terminology. Changing the focus from modelling computations to measuring complexity of theories, the paper describes how to obtain $\Sigma^0_1$- and $\Pi^0_1$-completeness results for a wide range of fragments of theories in a very uniform way, and the reasoning will employ the following concepts. Let $\sigma$ be a first-order signature and ${Val}_{\sigma}$ the collection of all valid $\sigma$-sentences. For $\mathrm{C} \in \left\{ \Pi^0_1, \Sigma^0_1 \right\}$, call a set $\Gamma$ of $\sigma$-sentences hereditarily $\mathrm{C}$-complete iff for any $\mathrm{C}$-set $\Delta$, whenever ${Val}_{\sigma} \cap \Gamma \subseteq \Delta \subseteq \Gamma$, then $\Delta$ is $\mathrm{C}$-complete. Both notions are closely connected with that of being hereditarily undecidable, but unlike their common predecessor, serve the purpose of getting computational complexity results, via employing the two most fundamental levels of the arithmetical hierarchy. This paper presents major tools and main examples in the study of hereditary $\Pi^0_1$- and $\Sigma^0_1$-completeness, with a discussion of various applications.