3
$\begingroup$

I'm trying to solve the following exercise from an old exam:

For a computable function $G: \mathbb{N} \to \mathbb{N} $, and a set of numbers $A$, we define $g^{-1}(A)=\{x|g(x) \in A\} $ and $g(A)=\{g(x)| x\in A\}$. If $A$ is a decidable group so.. here there were 4 options and I chose $g(A)$ is not necessarily decidable, and $g^{-1}$ is certainly decidable.

I chose this option since we are not sure that $g$ is a total computable function, and it might not stop on one of $x \in A$, but why does $g^{-1}(A)=\{x|g(x) \in A\} $ have to be decidable? we need to use $g$ to find out that $g(x) \in A$, no?

  • 2
    Please use the computability tag for questions about computability theory. The fact that they are about computability does not make them "computer science".2012-08-13
  • 0
    o.k, but it is still "computer science", isn't it?2012-08-13
  • 1
    No, not really. Computability theory of this sort is certainly *used* in computer science - but not very often, and many universities don't even include a class in it for an undergrad CS major. Only a tiny amount of computer science work is related to theoretical computability. Personally my research is in computability theory, but I am not a computer scientist.2012-08-13
  • 0
    @Carl, although computability theory focused courses have become less common, it is still common to teach basic computability theory in the introduction to computational complexity courses. (I agree with you that the [tag:computer-science] tag is not needed for computability theory questions.)2012-08-13

1 Answers 1

1

Your reasoning works out for $g(A)$, but $g^{-1}(A)$ needn't be decidable. Just take $A=\mathbb{N}$: then in particular $g^{-1}(A)$ decidable means the domain of every partial computable function is decidable. But the recursively enumerable sets are exactly the domains of computable functions, so we'd have every r.e. set recursive.

Thanks for sharing the specific choices that were offered you in your comment below. None of them hold for an arbitrary computable function (though see below for a total one,) and we can show this without taking $A$ to be anything fancier than $\mathbb{N}$ itself. First, $g(\mathbb{N})$ may be decidable, for instance, if it's finite. $g^{-1}(\mathbb{N})$ may be decidable. For instance, if $g$ is total, $g^{-1}(\mathbb{N})=\mathbb{N}$.

$g(\mathbb{N})$ may be undecidable: take $g$ to be identity on the diagonal set $D=\{n: f_n(n) \textrm{is defined} \}$, where $f_n$ is some Godel numbering of the computable functions, and $0$ elsewhere. $g^{-1}(\mathbb{N})$ may be undecidable: take $g$ again to be identity on $D$, but now undefined elsewhere. It's immediate that these last two sets are undecidable by the diagonalization argument that you've likely seen at some point-I'll elaborate if not.

As we've agreed below, the questioner must have intended $g$ to be total. Then we see something like the first diagonal function defined above has $g(\mathbb{N})$ undecidable, but $g^{-1}(\mathbb{N})$ is decidable for decidable $A$ by simply computing $g(n)$ and seeing whether it's in $A$.

  • 0
    needen't means what? must not be?2012-08-13
  • 0
    Only "may not be," or "doesn't need to be." It's certainly decidable sometimes-in particular if $g$ is total, it's decidable for every $A$.2012-08-13
  • 0
    O.k I got confused, there isn't option for both may be decidable. it's "a. both must be decidable", "b.g(A) not necessarily decidable, but g^-1(A) must be", "c.g(A) must be decidable, and g-1(a) not necessarily decidable", "d.one of them must not be decidable".2012-08-13
  • 0
    Hm. Something's wrong there. I've responded above.2012-08-13
  • 1
    The question says $g$ is a computable function from $\mathbb{N}$ to $\mathbb{N}$, so I think in particular it's assumed that it's total.2012-08-13
  • 0
    @HarryAltman-yes, I guess that's the only sensible interpretation. It's unfortunate phrasing, if we're to infer "total" from the $\mathbb{N}\rightarrow \mathbb{N}$ description.2012-08-13
  • 0
    Definition of total is that it stops for every $x \in \mathbb{N}$, right?2012-08-13
  • 0
    Jozef, practically that's what "total" means, though to be pedantic that's really how we describe a Turing machine that computes a total function. A total function is just one that's defined at every $x\in \mathbb{N}$-we can talk about them without bringing in a computational model.2012-08-13
  • 0
    So why do you assume that $g$ is a total one? I didn't get it..2012-08-13
  • 0
    It's very common in computability theory for "computable function" to mean "total computable function"; you have to say "partial" if you don't want to imply the function is total.2012-08-13
  • 0
    @CarlMummert, that's not how I learned it Russia-I'm used to being able to say the r.e. sets are exactly the domains or ranges of computable functions. So, it's good to know I can't count on this usage's universality.2012-08-13
  • 0
    @Kevin Carlson: yes, some people certainly use different terminology. The standard texts by Soare and Rogers both use "computable function" and "recursive function" to mean "total computable function" and explicitly say "partial" when necessary. That usage is, correspondingly, common in the research literature as well. But it's not universal. Unfortunately computability suffers more than other areas of mathematics from a fragmentation of terminology.2012-08-13