1)Prove that a set is recursive if and only if it is finite or can be
enumerated in strictly increasing order.
2)Show that the following sets are not recursively enumerable.
a) { i | Wi = Ø }
b) { i | Wi = all integers }

---

Request for Question Clarification by rbnn-ga on 04 Oct 2002 00:03 PDT

Define "Wi".

---

Clarification of Question by joannehuang-ga on 04 Oct 2002 12:33 PDT

3)Are those set are recursive? Are they r.e.?
justify your conjectures
a){x|x is an even integer}
b){i| Mi halts for all inputs}
c){i| Mi halts only for prime integers}
d){i| Mi is not a Turing machine}

See my comment, here reposted.

Should you require additional clarification, please do not hesitate to ask:

In recursive function theory there are numerous very slightly 
different definitions of the same concepts, such as "recursive", 
"Turing Machine", "recursively enumerable" and so on. 
 
All the different definitions of a given concept are easily (or at any
rate eventually) proved to be equivalent, and once one is experienced 
in the field one can see the real meanings of the different concepts. 
 
However, particularly if this is homework-type questions, you may need
to actually go back to the exact definitions, to determine exactly how
something like Turing Machine, language acceptance, and so on was 
phrased. I don't have access to your exact level of required proof 
here, so I am going to give the answers in general terms that would be
acceptable to anyone familiar with recursive function theory; however,
this may not be what you are looking for. 
 
On the other hand, I do want to be as helpful as I can to you and to
at least try and provide what assistance I can.
 
For example, if you go back and read Godel's original proofs of the 
incompleteness theorems, you will be struck by how much detail and 
energy he puts into proving the exact encoding he uses. But now that 
hundreds or thousands of similar proofs of the incompleteness theorems
have obtained, people can prove it much more simply. 
 
Some of the questions you posted and the definitions are in the
lecture notes:
 
URL: http://cs.engr.uky.edu/~lewis/texts/theory/front/contents.pdf 
 
1) Suppose inputs are all restricted to be nonnegative integers. 
 
  Now suppose X is finite. Then X is clearly recursive, since a turing
machine can simply check whether its input argument is a member of the
set in question directly.
 
  Suppose X is infinite and enumerated by a machine M. Then a turing
machine M' can, given input x, continue to enumerate the elements of X
until either x is output, in which case x is in X, or until some y>x
is output, in which case x is not in X. Note that this only works
because X is infinite.
 
Hence, If X is finite or can be enumerated in strictly increasing
order, then X is recursive.
 
For the other direction, supposing X is recursive, and given a machine
M that recognizes X, simply make another machine M' that repeatedly
asks if 0 is in X, if 1 is in X, and so on; using M to determine
membership in X and outputtting only those nonnegative integers in X.
M enumerates the members of X in increasing order, and therefore the
other direction of the proof holds, and we are done.
 
However, if negative integers were allowed as input, then of course
the claim is false, as the set of all integers cannot be enumerated in
strictly increasing order, yet it is recursive.
 
2  These are all cases of Rice's theorem. For simplicity I will show
why they are true.
 
We define Wi as the language accepted by the Turing machine with
encoding i.
 
 a) Suppose U={i | Wi= {} } were r.e., and let M be a machine
accepting U. I claim we could solve the halting problem. I will create
a machine V that, given (the description of) a machine N and an input
x, decides if N halts on x.
 
V creates another machine N' that, given any input at all, ignores
that input and simulates N on x, accepting the input if and only if N
accepts x (i.e., halts on x).
 
Since then the code of N' is in U if and only if N does not halt on x.
 
V then runs M on N' and N on x in parallel. If M halts first, it knows
that N' is in U so N does not halt on x. If N halts first then it 
knows that N halts on x. So V solves the halting problem, and no such 
machine M can exist. 
 
 b) We use the same trick as in part a). Suppose that we have a 
 recursive enumeration of U={i | Wi=all integers } by a turing machine
 M, where by "all integers" we mean really "all nonnegative integers" 
 (see comment for question 1). I claim we can create a machine V that,
 given a description <N> of a machine N and an input x, decides 
 whether N halts on x.  
 
Indeed, V acts as follows. Frist, V creates a machine N' from N that,
accepts input i if and only if N does not halt on input x in less than
or equal to i steps.
 
Then N' accepts all integers if and only if N does not halt on x.  
 
Now V runs in parallel M on input N' and also N on input x. V outputs
"N halts on x" if the second simulation halts; otherwise, the first
simulation must halt, and V outputs "N does not halt on x" in this
case.
 
So, V always halts and determines whether N halts on x, which is
impossible, as it would solve the halting problem.
 
3a) This set is clearly recursive (and thus also recursively
enumerable). It is recursive by, e.g. Church's thesis. The exact state
definition depends on exactly how we define our Turing machines but
basically, if the input is in unary, we can simply have two states
that toggle one to the other depending on the number of 1s we have
seen in the input; we accept if and only if, on end of input, we have
seen an even number of ones.
 
3b) Presumably here Mi is the turing machine with index i. This set is
neither recursive nor recursively enumerable by the argument of 2a).
 
3c) We interpret this to mean the set of all i such that the set of 
inputs for which Mi halts is a subset of the prime 
integers. Equivalently, Mi fails to halt on all composite integers.
The English phrasing is a little bit ambiguous; one could
interpret "only for prime integers" to mean "Mi halts on all prime
integers" which set would also not be r.e.
 
Anyway, we can use the same kind of argument as before. If we could
enumerate the set of such i, then we could solve the halting problem
by a machine V that, given a machine N and an input x, constructs a
machine N' that never halts except on input 4, when it runs N on x.
Let j be the integer such that Mj=N'. Then if the set in question were
r.e., V could enumerate the elements of the set until j were reached,
and in parallel run N on x. Whichever halted first determines whether
N halts on x.
 
3d) This set is recursive, since to determine whether Mi is a Turing
machine just requires a finite set of rules making sure the definition
for Mi is well-formed. The details, unless you rely on Church's
thesis, depend on the encoding.
 
Anyway, if you are happy with this kind of answer, I can repost as an
answer, or some other Google researcher can tell you what you are
looking for a little bit better.

very helpful

To  rbnn-ga :
1)we don't need to define "Wi"
2)sure

Well, "recursive" and "recursively enumerable" are standard terms in
the field, but I believe that W used in this way is specific to the
source of the problem. From context I am guessing Wi is the language
accepted by the Turing machine with index i, but it's best to be sure.

you are right!
I add one more question and I raise price to $15.00

Hi there,

I am taking the unusual step here of posting my work as a comment. The
reason for this is as follows.

In recursive function theory there are numerous very slightly
different definitions of the same concepts, such as "recursive",
"Turing Machine", "recursively enumerable" and so on.

All the different definitions of a given concept are easily (or at any
rate eventually) proved to be equivalent, and once one is experienced
in the field one can see the real meanings of the different concepts.

However, particularly if this is homework-type questions, you may need
to actually go back to the exact definitions, to determine exactly how
something like Turing Machine, language acceptance, and so on was
phrased. I don't have access to your exact level of required proof
here, so I am going to give the answers in general terms that would be
acceptable to anyone familiar with recursive function theory; however,
this may not be what you are looking for.

On the other hand, I do want to be as helpful as I can to you and to
at least try and provide what assistance I can.

For example, if you go back and read Godel's original proofs of the
incompleteness theorems, you will be struck by how much detail and
energy he puts into proving the exact encoding he uses. But now that
hundreds or thousands of similar proofs of the incompleteness theorems
have obtained, people can prove it much more simply.

Some of the questions you posted and the definitions are in the
lecture notes:

URL: http://cs.engr.uky.edu/~lewis/texts/theory/front/contents.pdf

1) Suppose inputs are all restricted to be nonnegative integers.

  Now suppose X is finite. Then X is clearly recursive, since a turing
machine can simply check whether its input argument is a member of the
set in question directly.

  Suppose X is infinite and enumerated by a machine M. Then a turing
machine M' can, given input x, continue to enumerate the elements of X
until either x is output, in which case x is in X, or until some y>x
is output, in which case x is not in X. Note that this only works
because X is infinite.

Hence, If X is finite or can be enumerated in strictly increasing
order, then X is recursive.

For the other direction, supposing X is recursive, and given a machine
M that recognizes X, simply make another machine M' that repeatedly
asks if 0 is in X, if 1 is in X, and so on; using M to determine
membership in X and outputtting only those nonnegative integers in X.
M enumerates the members of X in increasing order, and therefore the
other direction of the proof holds, and we are done.

However, if negative integers were allowed as input, then of course
the claim is false, as the set of all integers cannot be enumerated in
strictly increasing order, yet it is recursive.

2  These are all cases of Rice's theorem. For simplicity I will show
why they are true.

We define Wi as the language accepted by the Turing machine with
encoding i.

 a) Suppose U={i | Wi= {} } were r.e., and let M be a machine
accepting U. I claim we could solve the halting problem. I will create
a machine V that, given (the description of) a machine N and an input
x, decides if N halts on x.

V creates another machine N' that, given any input at all, ignores
that input and simulates N on x, accepting the input if and only if N
accepts x (i.e., halts on x).

Since then the code of N' is in U if and only if N does not halt on x.

V then runs M on N' and N on x in parallel. If M halts first, it knows
that N' is in U so N does not halt on x. If N halts first then it
knows that N halts on x. So V solves the halting problem, and no such
machine M can exist.

 b) We use the same trick as in part a). Suppose that we have a
 recursive enumeration of U={i | Wi=all integers } by a turing machine
 M, where by "all integers" we mean really "all nonnegative integers"
 (see comment for question 1). I claim we can create a machine V that,
 given a description <N> of a machine N and an input x, decides
 whether N halts on x. 

Indeed, V acts as follows. Frist, V creates a machine N' from N that,
accepts input i if and only if N does not halt on input x in less than
or equal to i steps.

Then N' accepts all integers if and only if N does not halt on x. 

Now V runs in parallel M on input N' and also N on input x. V outputs
"N halts on x" if the second simulation halts; otherwise, the first
simulation must halt, and V outputs "N does not halt on x" in this
case.

So, V always halts and determines whether N halts on x, which is
impossible, as it would solve the halting problem.

3a) This set is clearly recursive (and thus also recursively
enumerable). It is recursive by, e.g. Church's thesis. The exact state
definition depends on exactly how we define our Turing machines but
basically, if the input is in unary, we can simply have two states
that toggle one to the other depending on the number of 1s we have
seen in the input; we accept if and only if, on end of input, we have
seen an even number of ones.

3b) Presumably here Mi is the turing machine with index i. This set is
neither recursive nor recursively enumerable by the argument of 2a).

3c) We interpret this to mean the set of all i such that the set of
inputs for which Mi halts is a subset of the prime
integers. Equivalently, Mi fails to halt on all composite integers.
The English phrasing is a little bit ambiguous; one could
interpret "only for prime integers" to mean "Mi halts on all prime
integers" which set would also not be r.e.

Anyway, we can use the same kind of argument as before. If we could
enumerate the set of such i, then we could solve the halting problem
by a machine V that, given a machine N and an input x, constructs a
machine N' that never halts except on input 4, when it runs N on x.
Let j be the integer such that Mj=N'. Then if the set in question were
r.e., V could enumerate the elements of the set until j were reached,
and in parallel run N on x. Whichever halted first determines whether
N halts on x.

3d) This set is recursive, since to determine whether Mi is a Turing
machine just requires a finite set of rules making sure the definition
for Mi is well-formed. The details, unless you rely on Church's
thesis, depend on the encoding.

Anyway, if you are happy with this kind of answer, I can repost as an
answer, or some other Google researcher can tell you what you are
looking for a little bit better.

To rbnn-ga:
Thank you! Yes, you can repost it as an answer.