--- In learn-cs-theory@y..., "Dotan Dvir" <dotandvir@M...> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi everyone,

  Good to see the group so active. Let's get rolling into action as
long as momentum is still high!
I suggest we each suggest a book for the first task and setup a
voting schedule (using a poll on Yahoo!), don't forget we still have
to get the book once we select it!

I'm pretty much open to any suggestion so fire away.

Take care,
Dotan

-----BEGIN PGP SIGNATURE-----
Version: PGP 6.5.1i for non-commercial use <http://www.pgpi.com/>

iQA/AwUBO1SK3CUiSSu0gtYSEQKLNwCeKySBKsdAU3+4bjhBU3g9MoiJqSkAn2KB
5Pa3l74atrAihr9+6iVmvJkA
=iC6s
-----END PGP SIGNATURE-----
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi Jim,

Unfortunately I gave only the chapter names and not the sections
within chapters; this is probably ok for Papadimitriou but it is
misleading for Sipser.  Here's a link to the full table of contents
for Sipser: http://www-math.mit.edu/~sipser/itoc-1.html .  I think
that Sipser covers all of the traditional topics, but it does seem to
devote more space to complexity theory and less to automata and
languages.  Whereas Padadimitriou skips automata and languages
altogether and starts with a self-contained description of Turing
machines.  I suppose that could be a plus or a minus depending on
what
one's interests are.  A few people here have expressed an interest in
mathematical logic, so the logic section in Papadimitriou might be
appealing.

I'm undecided at the moment--I'll have to wait and see what other
comments and suggestions people have.

-Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., Jim Nastos <jnastos@s...> wrote:

Hi, folks.

   I think this is my first posting.
   My background is in math (discrete) and I'll be starting a MSc in
computer science (graphs, algorithms, complexity, etc) this September.
Theory of Computing is my favorite field in computer science, so I'd
like
to contribute to the discussions and work on interesting problems
when the
come up.
   My interpretation of "theory of computing" seems to be a little
different than what I've heard so far from email... P=NP is indeed in
the
theory of computing, but it branches off into complexity theory,
which I
hold a little different from 'theory of computing.'

> I'm pretty much open to any suggestion so fire away.

   The text I learned from would be John C. Martin's
book "Introduction to
Languages & the Theory of Computation," dealing with finite automata,
determinism, context-free languages, grammars, push-down automata,
turing
machines, reductions, hierarchy of computational models, Church-Turing
thesis and evidence, etc, etc.
   Someone mentioned that the current book of interest used lisp
(scheme? I
don't recall)... this book is purely theoretical, so does not use a
specific language to teach its concepts. I see this as an advantage
for
the most part (although I'm sure some would find it a disadvantage.)
   Someone also mentioned that they will be taking some math courses
which
might come in handy. I see set theory being very useful when
investigating
language properties, for example. I'm not sure where the ring and
group
theory will come into play, however... (unless the following:)

   Some people have, on top of the P=NP issue, expressed other
algorithm
issues; I suppose the group/ring theory and coding languages may be
useful
if we concentrate on algorithms, but again, I would say that a study
of
algorithms can be done independently of a study of the theory of
computing. As I understand it, this discussion group is going to work
at
the theory of computing at an introductory level.

   Anyway, I'm okay with any book, as long as when people ask
questions,
they clearly state the problem and any difinitions which might not be
generally understood. I don't plan on working through the chosen book
with
the group, as I won't have enough free time for that, but I do look
forward to possibly working on challenging and interesting problems
people
might bring up.

   I'm located in Canada, for those curious. 23 years old. I have a
BMath
in Combinatorics&Optimization (C&O) and am 3 days away from finishing
a
B.Ed degree in secondary mathematics education.

Jim Nastos
--- End forwarded message ---

--- In learn-cs-theory@y..., Jim Nastos <jnastos@s...> wrote:

Okay, I just did a websearch for the book, and on the first page
returned
by Google, I found the following:

A review of it by  Doug Baldwin, a computer science professor (BSc
MSc PhD
Yale,) at
http://www.cs.geneseo.edu/~baldwin/math-thinking/Reviews/Martin-
Theory.html

The text is used as a reference book for the course COT6315 at the
University of Florida.
The text is used as the primary text for CSCI 551 at the University of
South Carolina.
The text is used as the primary text for course 0605-700 at the
Rochester
Institute of Technology.

   And, what's more, I also found an outline of the contents of the
book:

Part I: Mathematical Notation and Techniques. Basic Mathematical
Objects.
Mathematical Induction and Recursive Definitions.

Part II: Regular Languages and Finite Automata. Finite Automata. Non
Determinism. Kleene's Theorem. Minimal Finite Automata. Regular
Languages
and Non Regular Languages.

Part III: Context-Free Languages and Pushdown Automata. Context-free
Languages. Derivation Trees and Ambiguity. Pushdown Automata. The
Equivalence of CFG's and PDA's. Parsing. CFL's and Non-CFL's.

Part IV: Turing Machines, Their Languages, and Computation. Turing
Machines. Variations of Turing Machines. Recursively Enumerable
Languages.
More General Grammars. Unsolvable Decision Problems. Computability:
Primitive Recursive Functions. Computability: Recursive Functions.

Part V: Introduction to Computational Complexity. Some NP-Complete
Problems.


   We did not cover the whole book in our 4 month course, so there's
still
things in there for me to learn (and which I think others should
learn)
and there's still everything in the book for me to brush up on. I
still
vote Martin.

Jim
--- End forwarded message ---

--- In learn-cs-theory@y..., Jim Nastos <jnastos@s...> wrote:
On Wed, 18 Jul 2001 kvanette@c... wrote:

> Michael Sipser, "Introduction to the Theory of Computation", $89
> Christos H. Papadimitriou, "Computational Complexity", $47
> John C. Martin, "Introduction To Languages and The Theory of
> Computation", $95

   Good selection of books.
   At the University of Waterloo, Papadimitriou's book is used for a
4th
year theory course, which has prerequisite of a 3rd year theory course
which uses Martin's book.
   By the looks of the contents you listed, Papadimitriou's book is
more
algorithms and complexity, and does not spend time on things like
finite
automata, regular languages, context-free languages, etc.
   Sipser's book looks like it is closer to Martin's book, but does not
sound very detailed. I'm not sure what is in those chapters you
listed,
but I don't know if PDA's (deterministic and nondeterministic) are
covered, since the only mention of automata is in chapter 0. Are
Turing
Machines defined as a generalization of a PDA? There does not seem to
be a
chapter on just turing machines, which would be nice, because
analysing
nondeterminism, multi-tapedness, two-way tapedness, etc, and their
simulations are a few good things to know about them.
   I'm sorry, I don't own Martin's book so I can't tell you what's in
it. I
went through my course without buying the required text. His book is
also
used at UMichigan. My vote still goes to Martin's book; it has a very
strong emphasis on fundamental concepts.

Jim
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi all,

--- In learn-cs-theory@y..., "Dotan Dvir" <dotandvir@M...> wrote:
> I suggest we each suggest a book for the first task and setup a
> voting schedule (using a poll on Yahoo!), don't forget we still have
> to get the book once we select it!

Another great idea!  I can set up a poll once all the suggestions are
in.  Now, a number of books have been mentioned in recent posts as
being of interest, but not necessarily as the selection for studying.
So to avoid confusion, here are the ones that I think are candidates
so far--let me know if I've missed any.  I'll also include the price
from Amazon.com (in US$):

Michael Sipser, "Introduction to the Theory of Computation", $89
Christos H. Papadimitriou, "Computational Complexity", $47
John C. Martin, "Introduction To Languages and The Theory of
Computation", $95

Given how rapidly the field of computer science is advancing, I think
we ought to choose a text that is not too old, and preferably one
that
is currently being used somewhere to teach an undergraduate theory
course.  I think all of the above meet that criteria.

Now, I'm not sure how useful the following will be, but it occurred
to
me that it might be helpful in comparing the texts to have the tables
of contents.  Here are the ones that I have handy:

Sipser: (Chapter: Title)
0:  Introduction
   Part One: Automata and Languages
1:  Regular Languages
2:  Context-Free Languages
   Part Two: Computability Theory
3:  The Church-Turing Thesis
4:  Decidability
5:  Reducibility
6:  Advanced Topics in Computability Theory
   Part Three: Complexity Theory
7:  Time Complexity
8:  Space Complexity
9:  Intractability
10: Advanced Topics in Complexity Theory


Papadimitriou:
   Part I: Algorithms
1:  Problems and Algorithms
2:  Turing machines
3:  Computability
   Part II: Logic
4:  Boolean logic
5:  First-order logic
6:  Undecidability in logic
   Part III: P and NP
7:  Relations between complexity classes
8:  Reductions and completeness
9:  NP-complete problems
10: coNP and function problems
11: Randomized computation
12: Cryptography
13: Approximability
14: On P vs. NP
   Part IV: Inside P
15: Parallel computation
16: Logarithmic space
   Part V: Beyond NP
17: The polynomial hierarchy
18: Computation that counts
19: Polynomial space
20: A glimpse beyond

I'm not familiar with Martin's book.  Jim, if you still have it handy
maybe you could list the contents for us.  Hmmm, here's the author's
web page: http://www.cs.ndsu.NoDak.edu/~jmartin/ .  It looks like
he's
using his text for a two-semester sequence in theoretical computer
science.

Keep the suggestions coming in!  And if you do happen to have the
text
nearby, go ahead and list the contents.

Thanks,
   Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., vznuri@e... wrote:
SICP has the distinction of being
both introductory/freshman level yet
has been ranked as one of the
top CS books of all time even by
experts, along
with books like Godel,Escher,Bach
by Hofstadter.

I was very fortunate to have some
very enlightened professors at
my school who committed to it for
incoming freshmen engineers. Ive
gone through about half of the book.
it has a lot relating to lowlevel
compiler design.

however its all in scheme, a lisp
variant. it really does get to the
core theoretical ideas behind
CS, recursion in particular,
esp when you realize that Lisp
is somewhat based on church's
lambda calculus!! but it is not
a good reference for computational
complexity theory such as P vs NP
etcetera (it does not really even
address it iirc)

KLVE: wow, nice link--I had zero
idea that SIPC was free on the web!!
yowza. thats a theory-edge link
for sure. how neat it is to get
cross pollination between groups.

not to intrude, but one suggestion for
your consideration.
Ive noticed that traffic is often
sustained by newcomers as the oldtimers/
regulars tend to sit back a little.
this may just be theory-edge, or it
may be a more global phenomenon.

so imho, regular ads can be really crucial
in keeping the energy/vitality of a group
up. its nice that posting to usenet
is so easy/untimeconsuming.
--- End forwarded message ---

--- In learn-cs-theory@y..., Elmien Wolvaardt <lotus@e...> wrote:
Hi Kurt

As to why I'm doing this as self-study...
* My university doesn't have a very good compsci department.
* I'm an older student (25) and have found that self-study leads to
better understanding.
* And since we have been blessed with an outstanding maths and
applied maths department, I've decided to focus on the courses they
offer.

Good news is that this semester I'll be exposed to some applied
algebra, including set theory, groups, rings etc, which I think will
nicely supplement what we're doing.

Can I just suggest that we leave some time between deciding on the
textbook and actually starting, since it might take me a little while
to get it - South African bookshops being what they are.

Regards, and greetings to all the other members
Elmien
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi all,

Regarding the timetable for getting started:  I'd like to wait for a
few more days to see if we get any new members from the comp.theory
invitation, and then we can really get down to business.  In the
meantime, are there any other responses to Dotan's post?  This would
be a good time for anyone who hasn't already posted to give their
opinions.

Once we settle on the text, the next step is to set a schedule for
working through it.  So you may want to start thinking about how much
time you'd like to devote to this project.  These books are pretty
densely written, so just averaging a page or two per day may be
enough
to keep us busy.  Of course there's no need to set a rigid schedule
for the whole book at the beginning, but I would like to set some
general goalposts to help us pace ourselves.

Vlad, thanks for the reference to the message on collaborative
software.  The report on Internet groupware
(http://software-carpentry.codesourcery.com/Groupware/report.html)
was
very interesting, but I noticed that several of the links to
groupware
companies were no longer working--evidently they were "dot-bomb"
casualties.

-Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Welcome to the group, Elmien!

Given your background, I don't think you'll have any trouble at all
with whatever text we end up choosing.  I am a little curious,
though,
about why you're doing this as self-study instead of taking the
corresponding classes at school.

I wasn't familiar with either SICP or "The computational beauty of
nature", and I just spent some time at the MIT Press web site reading
about them.  They both seem like awesome books--it makes me wish I
had
more free time for reading.  I think I will have to eventually get a
copy of "computational beauty ...".  BTW, in case anyone is
interested
the full text of SICP is available online at:
http://mitpress.mit.edu/sicp/ .

I'm amazed at how diverse this group is geographically.  Even though
we only have a handful of members, we seem to have a large part of
the
globe respresented already.  The Internet is wonderful!

-Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., Elmien Wolvaardt <lotus@e...> wrote:
Hello - my name is Elmien, and I'm a second-year university student
in Cape
Town, South Africa, currently taking applied mathematics.

I've recently started working through SICP (Structure and
Interpretation of
Computer Programs - the freshman text at MIT), by myself. I'm
enjoying it a
lot. It's an excellent text, and so far I've made good progress, but
it
would be great to discuss some of the excercises.

I'm not sure if my background is sufficient: 3 semesters applied maths
(modelling and applied computing, dynamics, vector analysis, ordinary
differential equations), 2 semesters math (calculus), 1 semester
stats, 2
semesters physics, 1 semester philosophy ('critical reasoning').

I'm very interested in logic, automata and complexity, and would be
very
happy to start with a basic text and work my way up - will trust your
recommendations for a good book.

In fact, I think my goal is to be able understand the book "The
computational beauty of nature" by Gary William Flake in it's
entirety - my
partner is a programmer and the book has been lying at home -
tantalisingly
so.

Well, hope things work out and we can get going soon!

Regards
Elmien
--- End forwarded message ---

--- In learn-cs-theory@y..., vznuri@e... wrote:
hi everyone. its really great to see
a spirit of collaboration here.  it
seems not all that common in
cyberspace sometimes. esp directed
toward learning, what a great goal.
I hope it can be sustained over time even
after the initial burst of enthusiasm
that accompanies a new list/playground.

KLVE: have you/are you considering
posting to comp.theory? my experience
is that posting about every 4-6 weeks
in the same place will still bring
in new subscribers every time. this
is probably due to that newgroups
have very few regular readers but
many ppl who pop in from time to time.

I see so many P=?NP queries on
comp.theory, maybe that will be the
best way for you to recruit subscribers.
I will refer people to your list
as long as it stays active.

re: collaboration/software, here is a very
nice set of links on tools etc
just dug up by FI
on theory edge

http://groups.yahoo.com/group/theory-edge/message/3349
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi Dotan,

--- In learn-cs-theory@y..., "Dotan Dvir" <dotandvir@M...> wrote:
> I suggest we first of all focus the discussion on the topics we wish
> to study and then select the text. ...

That's an excellent suggestion.  For myself, I'd like to achieve two
things: first, to learn about computational complexity and
NP-completeness in particular, and second, to get a solid background
for further studies.  Most of the introductory texts I've browsed
through take roughly the same approach, starting with automata and
formal languages, then Turing machines and computability, and finally
complexity theory.  I liked Sipser's book because it seems readable
enough and appears to put more emphasize on complexity theory, but
I'm
by no means set on it.

> I have not read the Sipser text but instead read at the time of my
> studies a book by Papadimitriou, which I consider very well
written.

I just spent some time browsing through
Papadimitriou's "Computational
Complexity" (is that the book you refer to?) and it looked very
interesting.  It starts with Turing machines and computability, then
goes to logic and Godel's theorems, and then to complexity theory.
It
does seem to be well written and not too difficult to digest.  I
don't
know if the lack of time spent on automata and languages would be a
problem with later studies or not.

> ... If I may make a
> suggestion, then may we please pick a not very advanced text for the
> begining as it will give us all a chance to zero in on the basic
> definitions.

I couldn't agree more.  Unfortunately, none of the books I've looked
at seem to be particularly easy, despite my earlier comments about
their readability.  I don't have a good feel yet for what everyone's
background is, so I don't know just what the right "entry point"
should be.  Comments anyone?

  -Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., "Dotan Dvir" <dotandvir@M...> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

I have not read the Sipser text but instead read at the time of my
studies a book by Papadimitriou, which I consider very well written.
I suggest we first of all focus the discussion on the topics we wish
to study and then select the text. For me anything that will let me
practice the art of mathematical argument again is a valid decision.

Possible topics for group reading are:
1. Combinatorics
2. Computabilty Theory
3. Logic (which is also connected with the former topics)
4. Algebra (pretty much a catch all phrase)

Hoping to hear comments and the final text selection. If I may make a
suggestion, then may we please pick a not very advanced text for the
begining as it will give us all a chance to zero in on the basic
definitions. I would also like to suggest we solve the excercises
together and compare notes.

Really looking forward to this project begining,
Dotan

-----BEGIN PGP SIGNATURE-----
Version: PGP 6.5.1i for non-commercial use <http://www.pgpi.com/>

iQA/AwUBO1HTbyUiSSu0gtYSEQLTTgCgwqrX166lQlYTj/BMEg73N/s7jzYAnRTC
WQpwe4bSqRmdh/lIqtI0ZMfS
=iEra
-----END PGP SIGNATURE-----
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi Satyadev, welcome to the group!

--- In learn-cs-theory@y..., satyadev_n@y... wrote:
>    Could we have a discussion on the basic concepts of P space, P
> Time, P and NP, and some graph theoretical problems that are
closely
> asssociated with these ideas?

I'm sure whichever book we settle on will include material on P and
NP, etc. (and as I've mentioned, this is something I'm also
interested
in).  I suppose most texts will also include some examples of
graph-theoretical problems, although this may vary quite a bit by
author.  One possibility, if there is sufficient interest, would be
to
choose something for our second book that covers graph theory.  (Of
course, this assumes that we survive reading through the first
selection!)

BTW, I'm interpretting your post as refering to topics you'd like to
see covered in the reading.  If there's anything you'd like to start
discussing immediately, by all means jump right in.

-Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., satyadev_n@y... wrote:
Hi,

    I am Satyadev, and I am working as a software engineer in
Bangalore, India.

    Could we have a discussion on the basic concepts of P space, P
Time, P and NP, and some graph theoretical problems that are closely
asssociated with these ideas?

Regards.
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Welcome Mahboob and Dotan!

I've posted a message on comp.theory inviting people to come and take
a look at this list.  The volume of messages on comp.theory is really
low right now, with everyone being out on vacation; so I'm not sure
what kind of response to expect.  But I can always post again in
September.  Let me know if there are other places you think I ought
to
be advertising the group.

After we see what kind of new membership we get in the next week or
so, I think we can start in earnest about selecting the text and
setting up a schedule.  (I'm assuming it will be Sipser, and I see
that Mahboob has already voted with his wallet, so to speak.  But I'm
remaining noncommital in case we get a flood of people with other
ideas about what to read.)  Even if we don't get much response I
think
we have enough "critical mass" now to be successful.

John, the math book sounds interesting.  I see you decided to go with
something in "pure math" instead of something geared more toward
computer science applications.

I didn't realize there was so much Internet-based "groupware" out
there.  I'll have to start looking around to see what's available for
free or just a nominal charge.  I'm not sure how much we will even
use
chat, but I figure it would be a good idea to have it as an option.

Thanks,
   Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., john.f@a... wrote:
7/14/01 11:59:19 AM

	 Hello Mahoob and Dotan, nice to see that other people are out
there.
In my search for a text on the introduction to advanced mathematics,
I
decided to go with the appropriately named "Introduction to Advanced
Mathematics" ISBN: 0130167509.  By the table of contents it appears
to
cover most of what I want.  Mahoob said he had already purchased
Sipser's book, tho Kurt I sa you mentioned that you had received
recommendations from other people.  Is there a consensus so far that
people want to work through a book?  How many people do you guys
think
ought to be participating.  I have been looking around at online
white
boards and related software.  MS NetMeeting has one, but I've never
used it.  There is large list at http://directory.google.
com/Top/Computers/Software/Online-Training/Collaborative_Learning and
related listings.  Most are seem to have more functionality than I
think is needed and are in the price range of expensive to very very
expensive ( > $20,000).  Enterprise users seems to be the target
market
for these tools.
--- End forwarded message ---

--- In learn-cs-theory@y..., "Dotan Dvir" <dotandvir@M...> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

I,m a 27 (almost 28) years old software engineer. Graduated from the
Technion in Israel and been working for nearly 2 years now. Looking
towards returning for an Msc. one day soon, in the mean time I would
like to extend my knowledge of CS theory.

Pleased to meet you all,
Dotan

-----BEGIN PGP SIGNATURE-----
Version: PGP 6.5.1i for non-commercial use <http://www.pgpi.com/>

iQA/AwUBO0/seCUiSSu0gtYSEQKoZwCffM562m5DTsxGa2qMc0shYZCcDdkAn2c4
LIJe2FCmZDpwXKjG6Kf7fL/u
=HOip
-----END PGP SIGNATURE-----
--- End forwarded message ---

--- In learn-cs-theory@y..., mahboob_h@y... wrote:
Hi,

About me:
Studied - Mechanical Engg. in India. Worked  - Mechanical Design
Engineer for 5 years. Switched to programming 5 years ago. Been in
the U.S for over 2 years now.

Interested to learn C.S/computation theory. Like this concept of
using a mailing list to learn a subject. Already ordered Sipser.

Thanks,
Mahboob
--- End forwarded message ---

--- In learn-cs-theory@y..., vznuri@e... wrote:
hi guys

bruce eckel is a great writer,
wow. I downloaded his c++ book
that's free on the web. amazing.
what a hard worker, and generous
to boot.

re: turing's proof. well there
is a very easy way to visualize
the halting problem proof, starting
with the idea behind cantor's proof
of the nondenumerability of
the reals.

in fact when you look at turing's
paper its clear, that was the
key inspiration/framework he
used to come up with the discovery.
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi John,

--- In learn-cs-theory@y..., john.f@a... wrote:

> To be more specific about my interests, it's my desire to be able
to
> understand Godel's Incompleteness Theorem and the work of
> Turing/Church.

The book we used back in my college course (Machtey and Young, "An
Introduction to the General Theory of Algorithms"), actually has a
proof of Godel's Incompleteness Theorem in it.  So you might find
that
text interesting.  However, I wouldn't recommend it as an
introduction
to the subject.  Just speaking for myself, I know that if I'm going
to
be tackling this without the benefit of an instructor, I want to be
sure to start off with something that's relatively easy going.  My
feeling is that if this group is successful and we make our way
through the first text, then we can either look at a more advanced
text on the same topic, or branch out into other areas.

> Besides an introductory book to start with, I have also been
looking
> for a survey or encyclopedia like book to fill the holes in my
swiss
> cheese knowledge.

I'm not sure about a general survey text for computer science, but if
you want something with all of the mathematical basics for use as a
reference, you might want to look at some discrete math texts.  I've
used "Discrete Mathematics and Its Applications" by Kenneth H. Rosen,
and it's ok.  I've also seen recommendations for "Concrete
Mathematics
: A Foundation for Computer Science" by Ronald Graham et al.

> I am also curious about people's experiences buying
> used books and the condition they came in.

I've purchased a used book once through Amazon.com, and had no
problems with it.  They act as a broker for individual sellers, so
it's going to depend a lot on who you're actually buying from.  The
only drawback was that it took a while to receive the book--it was
sent book class and there wasn't any way to request faster shipment.

-Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., john.f@a... wrote:
7/11/01 1:03:36 PM


kvanette@c... wrote on 7/10/01 9:59:52 PM:

>John, thanks for your post!  I was beginning to wonder if anyone
else
>was going to join in.  I've only advertised this group in a very
>limited fashion so far (on the theory-edge and algorithm-forge
mailing
>lists) because I wanted to have a chance to get some feedback and
>refine the focus of the group before soliciting more members.  But I
>almost get the impression from your post that you found this group
by
>searching through the group index on Yahoo.  Is that true?

I came across this group by way of the theory-edge list.  I was
reading
one of the comp.* newsgroups and saw a post advertising that list.  I
surfed on over, saw your post inviting people to check this list out,
and did so.  I wasn't looking for it, but I have been gearing up to
do
some studying in this area, and consider it a rather fortuitous
coincidence.  It hadn't occurred to me that people might be using the
internet in this way.

>My own specific interest is in gaining the background necessary to
>really understand the P vs. NP question and related issues, so I
>suppose that falls under the heading of complexity theory.  I picked
>the name "learn-cs-theory" for the group because I wanted something
>that wasn't unduly long and I wanted to emphasize the "learn" part.
>My inspiration for forming this group was actually the "JavaThink"
>group (also on Yahoo).  Their aim is studying a single
book, "Thinking
>in Java" by Bruce Eckel.  I figured that if they could do that, then
>maybe it would work for me (although maybe without quite so narrow a
>focus).

To be more specific about my interests, it's my desire to be able to
understand Godel's Incompleteness Theorem and the work of
Turing/Church.
   My goal is more basic in that what I want  really to understand are
   what the limits of math/logic can say.  If there are limits.  I
think
   that most people who come here will have different goals for
   themselves, but I don't see that as a problem.

>I think that the most important prerequisite for an introductory
>theory of computation text is going to be an understanding of logic
>and how mathematical proofs are structured.  Plus some set theory,
and
>just a little calculus for things like Big O notation.  Some graph
>theory and number theory might be nice for understanding some of the
>example problems, but probably wouldn't be necessary for
understanding
>the concepts themselves.

As I said, I have been investigating advanced math for awhile in
preparation of beginning some self-study.  I definitely more
interested
in reading a textbook along with other people than ad hoc posts.
Besides an introductory book to start with, I have also been looking
for a survey or encyclopedia like book to fill the holes in my swiss
cheese knowledge.  I have become slightly familiar with set, group,
and
number theory just from looking around the internet; but I like
having
books in front of me.  I have not been able to find any one book
which
fits the bill though.  I would be interested in anyone's
recommendation
about a book or two that is sufficiently general or conceptual.  I
have
seen many that are non-fiction rather than textbook (not that I don't
like those book either).  I would rather learn the method and be able
to replicate the work myself rather than simply read that something
is
so and accept it.  I am also curious about people's experiences
buying
used books and the condition they came in.
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi Vlad,

Thanks for the post.  Perhaps it's fitting that yours is the first
post, if you think of yourself as being in some sense the godfather
of
this list.  (For any readers who may not be aware, Vlad Nuri is the
creator of the theory-edge mailing list.)

Hmmm, leadership experiences?  I'm hoping this will really be a
"group" activity, with people participating equally.  The moderator
responsibilities, such as they are, should be mainly technical in
nature.  I'd like this group to have the feel of a bunch of students
sitting around the math or cs lab, talking about the last class
assignment.

Thanks for the comp.theory FAQ suggestion, that will definitely go
onto the group web page.  (The web page is not too interesting right
now, eh?  That will change with time.)

-Kurt

--- In learn-cs-theory@y..., vznuri@e... wrote:
> haha. another baby spinoff-hatchling.
> and by some amusing oversight, I am
> the first to post, hehe
>
> good luck with the new list KLVE!!
> maybe you could describe your background,
> I am curious.
> esp. things like leadership experiences
> are very relevant to starting a group
> & gaining people's involvement.
>
> also, what are some of your favorite
> links on the subject? for starters
> I highly recommend the comp.theory FAQ
> to everyone.
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
I see that we're starting to get some additional members joining the
list so I thought I'd say hello again to everyone.  Most of you have
not posted anything yet so I'm assuming that you're just looking in
to
see if any interesting questions or discussions come up...  But if
any
of you are actually interested in working through a text please
either
post or send me an e-mail so I have a feel for what people want to do
here.

Vlad, thanks for the book recommendations.  I've seen Kozen mentioned
several different times now so I'll have to make a point of looking
at
that one.

John, thanks for your post!  I was beginning to wonder if anyone else
was going to join in.  I've only advertised this group in a very
limited fashion so far (on the theory-edge and algorithm-forge
mailing
lists) because I wanted to have a chance to get some feedback and
refine the focus of the group before soliciting more members.  But I
almost get the impression from your post that you found this group by
searching through the group index on Yahoo.  Is that true?

My own specific interest is in gaining the background necessary to
really understand the P vs. NP question and related issues, so I
suppose that falls under the heading of complexity theory.  I picked
the name "learn-cs-theory" for the group because I wanted something
that wasn't unduly long and I wanted to emphasize the "learn" part.
My inspiration for forming this group was actually the "JavaThink"
group (also on Yahoo).  Their aim is studying a single
book, "Thinking
in Java" by Bruce Eckel.  I figured that if they could do that, then
maybe it would work for me (although maybe without quite so narrow a
focus).

I think that the most important prerequisite for an introductory
theory of computation text is going to be an understanding of logic
and how mathematical proofs are structured.  Plus some set theory,
and
just a little calculus for things like Big O notation.  Some graph
theory and number theory might be nice for understanding some of the
example problems, but probably wouldn't be necessary for
understanding
the concepts themselves.

Thanks,
   Kurt
--- End forwarded message ---

--- In learn-cs-theory@y..., john.f@a... wrote:
7/10/01 6:17:51 AM

	 Hello List, my name is John.  I already know a bit about
computers; programming, administration, networking, etc.  I am mostly
self taught.  Learning computation theory is something I am keenly
interested in
doing.  My main interests are mathematical logic and AI.  I am
concerned that my mathematical background is a little weak for this;
calculus, some basic statistics (mostly forgotten).  The title of the
list is "learn-cs-theory"
while the introduction on yahoo states that is about the theory of
computation.  Theory of computation is probably only going to be of
interest to people learning computer science, but there is a
distinction between the two
that leaves me wondering in what direction people want to go with
their studies.  Regarding some points from the earlier post "cs
newbies" from vznuri; I do not think this list is too specialized, I
think it's quite a good idea
with just the right scope.  Two things I have observed in distance
learning type classes that makes them effective is that participation
is voluntary and there are no fixed times.  It's a gross
generalization, but with voluntary
students (that is people who are just here because they want to be
with no grades or attendance etc) you are probably going to have a
more serious and dedicated group pursuing this than you would
otherwise.  The
autonomy of this kind of study allows one use what they want and
explore what they want without upsetting the curriculum.  It is a
neat way for people with different methods and goals to come together
and use each other
as resources in our related interests.  I have spent a lot of time
learning things on my own, and one thing I do miss about school is
the discussion and interaction with other students and teachers; a
list like this can help
with that.  So I do think a list like this is rather a good thing and
has the potential to be a great resource.
	 About the proposed book, I can't say I have any knowledge
with which to form an opinion.  I suppose that defaults to a "Sure,
why not?" :)  I poked around and found the web page for the book
created by the
author at MIT:  http://www-math.mit.edu/~sipser/book.html.  Looking
around there some more will take you to the Theory of Computation
Group at MIT (http://theory.lcs.mit.edu/) which has, among other
things, class
descriptions and hand outs for their Theory of Computation class.
You simple search will yield pages a bunch of intro. to computation
classes at various schools around the world, but MIT's was the only
one I
looked at.  As far as buying the book goes, allbookstores.com is like
the pricewatch of books, I see it listed there used for about half
price.  If enough people are interested in this list, it's possible
to arrange a
discounted bulk order from some retailers; but I think that would
require one person collecting money from the rest, placing and
receiving the order, and then re-distributing the books through the
mail to all the
rest...I think it would have to be a big discount to pay for the loss
of convenience.
	 On yahoo, I see that the list has 10 subscribers, but only
see postings from 2.  No one wants to introduce themselves?  I think
the benefits of an enterprise like this are lost without
participation.
--- End forwarded message ---

--- In learn-cs-theory@y..., vznuri@e... wrote:

hi KLVE. wow, a godfather. well my
brother is having a baby but I will
just have to settle for cybergodfather haha.
lets credit SB also as creating a similar
list & making advances in this area in
cyberspace.

I think overall the group
is a good idea. however as I wrote you in
email once, I was afraid it might be too
specialized. let the record show I invited
you to try out the idea on theory-edge. but
yeah, theres a natural incompatibility. I routinely
suggest to newbies to try out comp.theory &
so does stas.

on the other hand, there are so many
newbie queries to comp.theory, its really
amazing, they pop up daily. it seems like
there ought to be many potential subscribers.
the pool is larger if you are willing to
consider talented high schoolers.

re: leadership. well I like the egalitarian
spirit you are proposing, but it seems
that one can never get a group of people
together without disagreements sometimes
arising & imho leadership experiences help in resolving
them fairly. although usually not a problem with
smaller sized lists.

here are some suggestions on possible
texts:

I like david harel, "spirit of computing". written
in a very intuitive style, lots of nice diagrams.
very accessable.

papadimitriou is a possibility. also kozen has
an introductory textbook.

the book "structure & interpretation of computer
programs" is used in MIT freshman classes. uses
scheme, but it is one of the great books in CS.
I must admit I didnt understand recursion at all
until I studied their book.
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Hi all,

Since I've invited everyone to post a little introduction, I suppose
I
should start it off by telling a little bit about myself.  I received
my B.A. in mathematics back in 1984 from the University of South
Florida.  Since then I've been working in various capacities as a
programmer (mostly statistical programming using SAS), but one of my
pet interests has been the theory of computation.  I've decided to
start actively studying this again, and I want to begin by
"relearning" what I studied in school.  Rather than just reading a
text on my own, I thought maybe others would be interested in forming
a study group to work through a text together.  So that's why I
formed
this group.

The text we used in school was "An Introduction to the General Theory
of Algorithms" by Machtey and Young.  My recollection is that the
book
was rather abstract and not an easy read.  From browsing through
people's recommendations on comp.theory and at amazon.com, Sipser's
"Introduction to the Theory of Computation" sounds like a good
introductory text.  I would be very interested in hearing other
suggestions.  I would also like to hear about any web resources that
might be useful, such as online course notes, downloadable texts, etc.

Once (and if) enough people join this group who are interested in
working through a text together, we can choose the text and set up a
timetable.  If people are interested we could also set up chat times.
(If anyone knows of any good "whiteboard" software/services we could
experiment with that too.)

I've set up a web page for this group, at:
   http://www.geocities.com/pnenp/
There's not much of interest there right now, but eventually it
should
hold links to web resources and other useful stuff.

Thanks,
   Kurt Van Etten
--- End forwarded message ---

--- In learn-cs-theory@y..., kvanette@c... wrote:
Welcome to the learn-cs-theory group.  (See the end of this
message for the mechanics of using this list.)

The purpose of this group is to provide a forum for studying
the theory of computation.  This could be in the form of:
1) adhoc posts and responses on any relevant topic; or
2) a paced reading of an introductory theory of computation
text, with chapter-by-chapter discussion of the text and
exercises.

One of the first orders of business for this list will be to
choose a text and set up a rough schedule for working through
it (assuming there is sufficient interest).  I would suggest
Michael Sipser's Introduction to the Theory of Computation as
a possibility, although I would welcome any other suggestions
for a text.  I would also be very interested in hearing about
other resources such as online course notes, e-books that can
be downloaded, etc.

I would urge all new subscribers to send a short post giving
a little bit of information about themselves and their ideas
for using this list, including their level of interest in
working through a textbook.

Thanks,
   Kurt Van Etten
   learn-cs-theory moderator


P.S.  Now for the mechanics of using this mailing list.  To
send a message to members of this group, simply send email to:

   learn-cs-theory@y...

You may unsubscribe by sending an email to:

   learn-cs-theory-unsubscribe@y...

You may also use the group web site to view and send
messages, modify your subscription, and access additional
group features:

   http://groups.yahoo.com/group/learn-cs-theory/

(You may need to create a Yahoo id to access certain features.)
--- End forwarded message ---

--- In learn-cs-theory@y..., vznuri@e... wrote:
haha. another baby spinoff-hatchling.
and by some amusing oversight, I am
the first to post, hehe

good luck with the new list KLVE!!
maybe you could describe your background,
I am curious.
esp. things like leadership experiences
are very relevant to starting a group
& gaining people's involvement.

also, what are some of your favorite
links on the subject? for starters
I highly recommend the comp.theory FAQ
to everyone.
--- End forwarded message ---