Re: help proving decidability of a set

i agree, but since that observation is true there must be a function
that returns "yes" or "no" depending on whether something is an element
of A. i am having trouble specifying this function, which is what i
attempted to do (unsuccessfully) in my first post.

Per Freem wrote:
hi all,

i am working through boolos and jeffrey's textbook and i have run into
a problem. i have made an attempt to prove the following, but i am
unsure of my proof: given a set A which is an infinite subset of the
natural numbers, suppose we have a "machine" M1 that can effectively
enumerate A (i.e. we have a computable function M1 whose domain is
natural numbers and range is A) and a "machine" M2 that can effectively
enumerate every natural number that is _not_ in A (similarly we have a
function M2). the problem is to show that A is decidable.

here's my attempt: it is a basic fact that if we have a function p
whose domain is natural numbers and whose range is a set A, and that p
is strictly increasing -- meaning if a < b => p(a) < p(b) -- then A is
decidable. my idea is to use M1 and M2 to build such a strictly
increasing function. so since we have M1 that enumerates A and M2 that
enumerates all the natural numbers not in A, we know that using both,
we can 'simulate' a strictly increasing order. our decision procedure
would then be:

D(i) = {1 if M1(m) = i for some m >= 0 and m <= i,
0 if M2(m) = i for some m >= 0 and m <= i}

since we are only checking finite subsets of the natural numbers in
each clause and M1 and M2 are guaranteed to be computable, we know that
D is decidable. is this correct? any hints or feedback would be
greatly appreciated.

thanks!

.

Relevant Pages

  • help proving decidability of a set
    ... given a set A which is an infinite subset of the ... enumerate A (i.e. we have a computable function M1 whose domain is ... we can 'simulate' a strictly increasing order. ...
    (comp.theory)
  • computability and logic; proving decidability
    ... given a set A which is an infinite subset of the ... enumerate A (i.e. we have a computable function M1 whose domain is ... we can 'simulate' a strictly increasing order. ...
    (sci.logic)