Prev: The decision time is bounded by a polynomial in |x| and k.QED
Next: Thank you, Dublin!
From: anonymous anonymous on 23 Apr 2010 10:33
Trying to understand the countable set and uncountable in context of
Turing machine. To me it looks like powerset of some countable set
like set of strings is countable. Am I missing something?

Here goes my understanding.


Let us say S1 is set of all strings over alphabet {a,b,c}.


So S1 will be something like this:
{a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac...,aca,acb...}


As we know S1 is countable.


Let us form set S2, from S1 where the strings in S2 are such that:
1.They do not start or end with alphabet c. (so ac, bc are not part
of
S2)
2. They do not include string where alphabet c occurs consecutively
i.e. (cc, acc are not part of S2)


So S2 looks like this: {a,b,aa,ab,ba,bb,aaa,aab......,aca,acb....}


Since S2 is subset of S1 it will be countable.


Now Let us say S3 is set of all string over alphabet {a,b}.


As we know S3 is also countable.


Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
{ab},
{ba},{bb},...,{a,a},{a,b}...}


Of what we know S4 is supposed to be uncountable (using the binary
encoding method).


Now S4 can be easily derived from S2. Replace the alphabet 'c' with
','(comma) and put curly braces.


We know S2 is countable so S4 must be countable too.


Alternative way:
============
We can make an enumerator for S4 by listing elements in the order of
number of alphabets.


Powerset of an infinite string can be enumerated as follows:
{
{}
{0}, {1}
{00},{01},{10},{11},{0,0},{0,1},{1,0},{1,1}
{000},{001},...{111},{0,00}....{1,11},{0,0,0}......{1,1,1}
{0000},......{1,1,1,1}
....


}


Like this there can be one to one mapping b/w natural numbers and
powerset. So given a natural number N, we can print the Nth element
of
the powerset. Basically while enumerating the powerset categorize
based on the number of symbols inside the set in the set too.
From: Patricia Shanahan on 23 Apr 2010 11:58
anonymous anonymous wrote:
> Trying to understand the countable set and uncountable in context of
> Turing machine. To me it looks like powerset of some countable set
> like set of strings is countable. Am I missing something?

The subject line is a bit weird. If there is a 1 to 1 mapping between
set S and a countable set, S is countable.

> Let us say S1 is set of all strings over alphabet {a,b,c}.

Are you limiting it to finite strings, or including infinite strings?

....
> Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
> {ab},
> {ba},{bb},...,{a,a},{a,b}...}

Are you limiting it to finite subsets, or do you mean the actual
powerset, which, if S3 is infinite, includes infinite subsets?

Patricia
From: Virgil on 23 Apr 2010 15:52
In article
<81f5e8c3-61d7-44d6-9cf7-4c4a7cb96419(a)m24g2000prc.googlegroups.com>,
anonymous anonymous <anonymous500081(a)gmail.com> wrote:

> Trying to understand the countable set and uncountable in context of
> Turing machine. To me it looks like powerset of some countable set
> like set of strings is countable. Am I missing something?
>
> Here goes my understanding.
>
>
> Let us say S1 is set of all strings over alphabet {a,b,c}.
>
>
> So S1 will be something like this:
> {a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac...,aca,acb...}
>
>
> As we know S1 is countable.
>
>
> Let us form set S2, from S1 where the strings in S2 are such that:
> 1.They do not start or end with alphabet c. (so ac, bc are not part
> of
> S2)
> 2. They do not include string where alphabet c occurs consecutively
> i.e. (cc, acc are not part of S2)
>
>
> So S2 looks like this: {a,b,aa,ab,ba,bb,aaa,aab......,aca,acb....}
>
>
> Since S2 is subset of S1 it will be countable.
>
>
> Now Let us say S3 is set of all string over alphabet {a,b}.
>
>
> As we know S3 is also countable.
>
>
> Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
> {ab},
> {ba},{bb},...,{a,a},{a,b}...}
>
>
> Of what we know S4 is supposed to be uncountable (using the binary
> encoding method).
>
>
> Now S4 can be easily derived from S2. Replace the alphabet 'c' with
> ','(comma) and put curly braces.
>
>
> We know S2 is countable so S4 must be countable too.
>
>
> Alternative way:
> ============
> We can make an enumerator for S4 by listing elements in the order of
> number of alphabets.
>
>
> Powerset of an infinite string can be enumerated as follows:
> {
> {}
> {0}, {1}
> {00},{01},{10},{11},{0,0},{0,1},{1,0},{1,1}
> {000},{001},...{111},{0,00}....{1,11},{0,0,0}......{1,1,1}
> {0000},......{1,1,1,1}
> ...
>
>
> }


No it cannot, as every member of your alleged enumeration is finite but
not all subsets of an infinite set are finite.
From: anonymous anonymous on 23 Apr 2010 23:19
On Apr 23, 8:58 pm, Patricia Shanahan <p...(a)acm.org> wrote:
> anonymous anonymous wrote:
> > Trying to understand the countable set and uncountable in context of
> > Turing machine. To me it looks like powerset of some countable set
> > like set of strings is countable. Am I missing something?
>
> The subject line is a bit weird. If there is a 1 to 1 mapping between
> set S and a countable set, S is countable.
>
> > Let us say S1 is set of all strings over alphabet {a,b,c}.
>
> Are you limiting it to finite strings, or including infinite strings?
>
> ...
>
> > Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
> > {ab},
> > {ba},{bb},...,{a,a},{a,b}...}
>
> Are you limiting it to finite subsets, or do you mean the actual
> powerset, which, if S3 is infinite, includes infinite subsets?
>
> Patricia

I am including infinite string and infinite subset like
{a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.

Ok here is the slides from where I was learning Turing machine and
countable sets.
http://www.cs.rpi.edu/~moorthy/Courses/modcomp/slides/Universal_Turing.ppt

If you look at slide number:
Slide 14 to 28 there is part of proove that even set of rational
numbers which have many infinite strings is countable.
Slide 32-52 will show that powerset of an infinite set is uncountable
which looks like not true to me.

Anyway I will send a mail to the author's themselves and ask.
From: Patricia Shanahan on 23 Apr 2010 23:44
anonymous anonymous wrote:
> On Apr 23, 8:58 pm, Patricia Shanahan <p...(a)acm.org> wrote:
>> anonymous anonymous wrote:
>>> Trying to understand the countable set and uncountable in context of
>>> Turing machine. To me it looks like powerset of some countable set
>>> like set of strings is countable. Am I missing something?
>> The subject line is a bit weird. If there is a 1 to 1 mapping between
>> set S and a countable set, S is countable.
>>
>>> Let us say S1 is set of all strings over alphabet {a,b,c}.
>> Are you limiting it to finite strings, or including infinite strings?
>>
>> ...
>>
>>> Let us say Powerset of S3 is S4 and will look like: {{a},{b},{aa},
>>> {ab},
>>> {ba},{bb},...,{a,a},{a,b}...}
>> Are you limiting it to finite subsets, or do you mean the actual
>> powerset, which, if S3 is infinite, includes infinite subsets?
>>
>> Patricia
>
> I am including infinite string and infinite subset like
> {a,b,c...............,aaaaaaaa.......,}. Otherwise there is no fun.

The set of infinite strings is uncountable. I think you may be confusing
it with the set of finite strings, which is countable.

Patricia
 |  Next  |  Last
Pages: 1 2 3 4
Prev: The decision time is bounded by a polynomial in |x| and k.QED
Next: Thank you, Dublin!