Let's denote a total increasing computable function $f: \mathbb{N} \rightarrow \mathbb{N}$. How to prove that the plot of $f$ is a decidable subset of $ \mathbb{N} \times \mathbb{N}$?

My solution: 1) First of all, we consider a plot as a $X \times Y = \{ (x, y) | x, y \in X, Y \} \subset \mathbb{N} \times \mathbb{N} $. We know, if the function in monotone and total, it's actually bijective. So, my algorithm looks like this: we receive a pair $(a, b)$ and we want to check, if it belongs to $X \times Y$. So, we just calculate $f(a)$: if $f(a)=b$, we print 1, else we print 0.

Could someone tell me, for what purpose the condition of the function's monotonicity was added?

  • 2
    $\begingroup$ If the "plot of the function" really is just the set of pairs $\{(x,f(x))\mid x\in\mathbb{N}\}$ then yes, your solution is correct and the function needs to be neither total nor monotone. And your answer doesn't actually require bijectivity. (By the way, you mean "monotone": "monotonous" means "boring".) $\endgroup$ – David Richerby Dec 8 '14 at 20:42
  • $\begingroup$ @DavidRicherby For example, if the function isn't total, the algorithm will not stop in a finite time, will it? For instance: if we recieve $(a, b)$ and $f$ is not defined at $a$, so we can't check, if the $f(a)=b$ just because we can't calculate it in a finite time. $\endgroup$ – hyperkahler Dec 8 '14 at 21:54
  • $\begingroup$ If the function is computable but not total, you can decide whether $f(a)$ is defined. If it is defined, you accept the pair $(a,f(a))$ and reject all pairs $(a,b)$ where $b\neq f(a)$. If $f(a)$ is undefined, you reject all pairs $(a,b)$. $\endgroup$ – David Richerby Dec 8 '14 at 22:03
  • $\begingroup$ @David Richerby Yes, i understood you. But the thing is that we can't actually establish, if $a \in dom(f)$ or not, just because there is no even a word about decidability of the $dom(f)$. We only know that it's an enumerable sets (it follows straight from the defenition of computable functions), but it can't help us, unless $dom(f)$ is finite set (this way, we can just enumerate all the elements from the domain). $\endgroup$ – hyperkahler Dec 8 '14 at 22:20
  • 1
    $\begingroup$ The function is computable. "Computable" and "decidable" mean exactly the same thing. It doesn't make sense to claim that a partial function is computable if its domain isn't decidable. $\endgroup$ – David Richerby Dec 8 '14 at 22:57

Your Answer

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

Browse other questions tagged or ask your own question.