I'm not sure how I am supposed to know this, I have never used notation like this in my previous school. Is this notation logic or is it something I should have learned in math class? What I am confused about are the arrows.

$$\Phi(x) \downarrow, \Phi(x) \uparrow, \operatorname{dom}{(\Phi)} = \{x : \Phi(x) \downarrow\}$$

  • 3
    $\begingroup$ If you're reading a text, it is likely defined in the text. If you're taking a course, ask your professor/TA. That's what they're there for. If the texts you're reading aren't defining their terms, then either you are not their target audience (yet), e.g. research papers, or they're garbage. Mathematics and computer science are both extremely good about having high-quality, freely available content (e.g. textbooks). There's generally no need to piece together standard background from random lecture notes and blog posts, if that's what you're doing. $\endgroup$ – Derek Elkins left SE Mar 19 '19 at 7:39

In computability theory, the first one means that function $\Phi(x)$ is defined for input $x$ while the second one means that function $\Phi(x)$ is undefined for input $x$.

Thus, $\text {dom}(\Phi)$ will be the set of input values of function $\Phi$, meaning the set of values such that the function is defined, i.e. $\{ x \mid \Phi(x) ↓ \}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.