2013-05-20
Q#4 Section-1 ... Practice Final.
Originally Posted By: ezekiel2
Corollary. Some languages are not recursive enumerable.
The set of all languages is uncountable since we see that the set of infinite sequences over {0,1} is uncountable. To show this we let f:A→P(A) be a supposed bijection. Since A is countable, we have some function a(k) to list out its elements a(0),a(1),a(2),.... An element X={a(2),a(5),...}∈P(A) can be view as an binary sequence (0,0,1,0,0,1,...) where we have a 1 if a(i) is in X and a 0 otherwise. So f satisfies the Diagonalization theorem. A complement of the diagonal for f will still be in P(A) but not mapped to by f. By letting N be the natural numbers, then P(N) is uncountable.
On the other hand, The set of all TM is countable. To show this,we observe that the set of all strings S* is countable for any alphabet S. With only finitely many strings of each length, we may form a list of S* by writing down all strings of length 0, length 1, length 2, and so on. The set of all Turing machines is countable because each Turing machine M
has an encoding into a string .
Let L be the set of all languages over alphabet S. We show that L is uncountable by giving a bijection with B, thus showing that the two sets are the same size. Let S* = {s1, s2, s3, . . .}. Each language A in L has a unique sequence in B. The function f : L−> B, where f(A) equals the characteristic sequence of A, is one-to-one and onto, and hence is a bijection. Therefore, as B is uncountable, L is uncountable as well. Thus we have shown that the set of all languages cannot be put into a bijection with the set of all Turing Machines. We conclude that some languages
are not recognized by any Turing machine.
Group Members: Charles Long , Minh Duong, Ezekiel Calubaquib
The set of all languages is uncountable since we see that the set of infinite sequences over {0,1} is uncountable. To show this we let f:A→P(A) be a supposed bijection. Since A is countable, we have some function a(k) to list out its elements a(0),a(1),a(2),.... An element X={a(2),a(5),...}∈P(A) can be view as an binary sequence (0,0,1,0,0,1,...) where we have a 1 if a(i) is in X and a 0 otherwise. So f satisfies the Diagonalization theorem. A complement of the diagonal for f will still be in P(A) but not mapped to by f. By letting N be the natural numbers, then P(N) is uncountable.
On the other hand, The set of all TM is countable. To show this,we observe that the set of all strings S* is countable for any alphabet S. With only finitely many strings of each length, we may form a list of S* by writing down all strings of length 0, length 1, length 2, and so on. The set of all Turing machines is countable because each Turing machine M
has an encoding into a string .
Let L be the set of all languages over alphabet S. We show that L is uncountable by giving a bijection with B, thus showing that the two sets are the same size. Let S* = {s1, s2, s3, . . .}. Each language A in L has a unique sequence in B. The function f : L−> B, where f(A) equals the characteristic sequence of A, is one-to-one and onto, and hence is a bijection. Therefore, as B is uncountable, L is uncountable as well. Thus we have shown that the set of all languages cannot be put into a bijection with the set of all Turing Machines. We conclude that some languages
are not recognized by any Turing machine.
Group Members: Charles Long , Minh Duong, Ezekiel Calubaquib
'''Originally Posted By: ezekiel2'''
Corollary. Some languages are not recursive enumerable.<br><br>The set of all languages is uncountable since we see that the set of infinite sequences over {0,1} is uncountable. To show this we let f:A→P(A) be a supposed bijection. Since A is countable, we have some function a(k) to list out its elements a(0),a(1),a(2),.... An element X={a(2),a(5),...}∈P(A) can be view as an binary sequence (0,0,1,0,0,1,...) where we have a 1 if a(i) is in X and a 0 otherwise. So f satisfies the Diagonalization theorem. A complement of the diagonal for f will still be in P(A) but not mapped to by f. By letting N be the natural numbers, then P(N) is uncountable. <br><br>On the other hand, The set of all TM is countable. To show this,we observe that the set of all strings S* is countable for any alphabet S. With only finitely many strings of each length, we may form a list of S* by writing down all strings of length 0, length 1, length 2, and so on. The set of all Turing machines is countable because each Turing machine M<br>has an encoding into a string . <br><br>Let L be the set of all languages over alphabet S. We show that L is uncountable by giving a bijection with B, thus showing that the two sets are the same size. Let S* = {s1, s2, s3, . . .}. Each language A in L has a unique sequence in B. The function f : L−> B, where f(A) equals the characteristic sequence of A, is one-to-one and onto, and hence is a bijection. Therefore, as B is uncountable, L is uncountable as well. Thus we have shown that the set of all languages cannot be put into a bijection with the set of all Turing Machines. We conclude that some languages<br>are not recognized by any Turing machine.<br><br>Group Members: Charles Long , Minh Duong, Ezekiel Calubaquib
(c) 2024 Yioop - PHP Search Engine