

Subject:
computer
Category: Computers Asked by: joannehuangga List Price: $15.00 
Posted:
03 Oct 2002 23:02 PDT
Expires: 02 Nov 2002 22:02 PST Question ID: 72316 
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 }  
 


Subject:
Re: computer
Answered By: rbnnga on 05 Oct 2002 18:26 PDT Rated: 
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 homeworktype 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 wellformed. 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. 
joannehuangga
rated this answer:
very helpful 

Subject:
Re: computer
From: joannehuangga on 04 Oct 2002 10:16 PDT 
To rbnnga : 1)we don't need to define "Wi" 2)sure 
Subject:
Re: computer
From: rbnnga on 04 Oct 2002 11:02 PDT 
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. 
Subject:
Re: computer
From: joannehuangga on 04 Oct 2002 12:29 PDT 
you are right! I add one more question and I raise price to $15.00 
Subject:
Re: computer
From: rbnnga on 05 Oct 2002 01:57 PDT 
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 homeworktype 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 wellformed. 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. 
Subject:
Re: computer
From: joannehuangga on 05 Oct 2002 08:47 PDT 
To rbnnga: Thank you! Yes, you can repost it as an answer. 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 