[Solved]: Where am I wrong?: “countability” and “recursive enumerability”

ignougroup
Problem Detail: I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i have made? Countability (C=Countable): A set $X$ is C when a bijection exists between the set of natural numbers and the set $X$ Recursive Enumerability (RE= Recursively Enumerable): Say set $S’$ is a subset of another set $S$. When there exists a turing machine with alphabet $A$ (where $S$ is a subset of $A^*$) which halts if the input to it belongs to the set $S’$ and does not halt if the input belongs to $S-S’$ then I say that the set $S’$ is recursively enumerable (given the fact that inputs comes only from the set $S$ and not from $A^*-S$ hence the latter will not concern us.) I have referred to the book “Elements of the theory of Computation” by Papadimitrou for this definition, though the introduction of an alphabet A is my own addition to make things more firm Now I will prove 2 statements:

  1. if a set $X$ is RE then it is C
  2. if a set $X$ is C then it is RE

Hence proving 3. RE iff C I will prove 2 first. I can write a Turing Machine $M$ which when asked to check if an element $x$ belongs to $X$ or not will follow the algorithm: There exists a mapping from the set of natural numbers to $X$ call it $f$. $M$ can search for $x$ (like a linear search algorithm running on $X$) starting from $f(1)$ going to $f(2)$… and it keeps going till it finds $x$. By this method, $M$ terminates iff $x$ belongs to $X$. The behaviour above proves that $X$ is RE Now I prove 1- Given a Turing Machine $M$ exists which halts iff $x$ belongs to $X$ I can construct a bijective map from the set of naturals to $X$ as follows: To map $x$ (given it belongs to $X$) , we run it as input against $M$. I take the concatenation of all configurations (Configuration=tape head position+tape content+state) of $M$ which it goes through from the starting of a computation to the end and decode that string as a natural number. It will be unique. Hence 1. is proven and so is 3. But then I find certain resources on the internet which tell me that enumerability and recursive enumerability are different things. How is it possible? Furthermore- We know that the power set of a countably infinite set is uncountably infinite. If $X$ was countably infinite, it would be RE (see 2.). Now we know that the subset of a set which is C is also C. Hence all subsets of $X$ would be C hence they would be RE. Now there would be an uncountable number of RE sets. Now for each RE set, we can write a turing machine (with appropriate halting behaviour) which can be encoded as a natural number implying that the “set of all RE sets” must be C. This contradicts the conclusion of the previous paragraph. Where exactly am I wrong? Thankyou in advance!

Asked By : swanar

Answered By : Yuval Filmus

Your algorithm for recursively enumerating any given set doesn’t work since the bijection between a countable set $X$ and the natural numbers can be arbitrarily complicated. For example, consider the following set $X$: $$ X = { P : text{the program coded by $P$ doesn’t halt on the empty string as input} }. $$ The set $X$ is countable: there are only countably many programs. However, there is no computable bijection between $X$ and the natural numbers, since otherwise RE=coRE (as your argument shows; $X$ is coRE-complete). Here is a more tangible example of a countable set for which there is no computable bijection: $$ Y = { 2P : text{program $P$ halts on the empty string} } cup { 2P+1 : text{program $P$ doesn’t halt on the empty string} }. $$ If there was a computable bijection between $Y$ and the natural numbers, then you could solve the halting problem (how?).
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12664

Leave a Reply