http:^^www.cs.washington.edu^education^courses^431^96s^bboard.shtml

来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 1,486 行 · 第 1/4 页

comments.

  > Subject: HW 1 #3.2
  > 
  > Hi, I have questions regarding Homework #1:
  > 
  > First, I don't understand why D will run forever on any input w
  > that N rejects.  N rejects a string w if it reaches the end of
  > w and is not in q_accept.  

You're confusing TM's with finite automata and PDA's, where reaching
the end of the input was part of the definition of acceptance.  It's
NOT part of the definition for TM's.  (Where IS the end of the input
after I erase it, or add to it or otherwise mangle it?  We could
define it, I suppose, but the TM definition is simpler without it --
you accept if you enter q_accept.  Period.

  > D simulates N with a copy of w on
  > tape 2, and by following a particular branch of N via the
  > node addresses given on tape 3.  If some branch results in a
  > rejecting configuration, why shouldn't D also reject?

There are perhaps 2 questions here.  (1) why doesn't it accept:
because D is programmed to do something else when it determines that
N has reached q_reject.  (2) why couldn't we change it to reject:
because then D would accept a different language than N does.  This
is a really important (and often misunderstood) feature of nondet
machines.  In an NTM, q_reject is sort of poorly named.  q_dead-end
might be a better name.  Think about the example of accepting
polynomials p(x) having integer roots.  Give it, say x^2-1.  What
happens on the path in the tree where it "guesses" x=5?  It
evaluates p(5), gets 25-1 = 24 != 0, and so enters q_reject.  Does
that mean p has no integer root?  NO!  it just means the particular
guess it was following on that path didn't pan out, but by no means
does it mean that some/many other guesses couldn't work (e.g. x=+-1
in this case).  So bazillions of paths ending in q_reject don't mean
the input is rejected; only the total absence of paths ending in
q_accept mean that it rejects.  Yes, very asymmetric.  Think of it
like Lotto tickets -- just because me and everyone else I happen to
know buy loosing tickets, doesn't mean there isn't a winner.  Can I
tell whether there is a winner by looking only at my ticket?  I can
if I'm one of the lucky winners, but not if I'm a looser; you have
to look at ALL the tickets to verify they're all loosers before you
know for sure there is no winner.

  > Second, I'm not sure what is meant by the last sentence on
  > page 121:  "Sometimes a symbol may not correspond to any choice
  > if too few choices are available for a configuration."
  > 
  > Third, some clarification on #5 (b):  the example ADD instruction
  > given combines the use of literal and indirect addressing?  Where
  > literal addressing refers to, what I learned as, an immediate
  > instruction in CSE 378.  So I take it that the "=" symbol means 
  > that j is a literal or constant, and k up-arrow is an address?

Yes.  (The syntax isn't important, of course, just happens to be what
I remember from the Tyranasauriac assembler.)
<hr size=4><a name="828682867001">Date: 4 Apr 1996 21:13 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: Michael Clay &lt;[e-mail]&gt;
Subject: <b>Re: HW1</b>
Cc: [e-mail]
</a>

    I think that this text has enough bugs and the rug has been pulled 
    out from under us enough times on this assignment, that the entire 
    *assignment* should be due Monday, not just 3.3.  

hmmm...  I think there was only that one bug relevant to this
assignment (which is listed on sipser's web errata page by the way),
so I don't think you should need more time, but if you really really
want it, I guess I could take #3.2 on monday also.

By the way, I hate having a book with errors, too.  So far, even
though this one is labeled &quot;Preliminary edition&quot;, I havn't found it
any worse that 10 year old n-th editions I've used, and the online
errata list is much better than usual.  The good news should be that
KNOWING there are errors in the book might nudge us all to read
it more carefully -- not an altogether bad habit.
<hr size=4><a name="828683292001">Date: 4 Apr 1996 21:42 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: Jason Murray &lt;[e-mail]&gt;
Subject: <b>Re: HW1</b>
Cc: [e-mail]
</a>


  &gt; Date: Thu, 4 Apr 1996 20:00:59 -0800 (PST)
  &gt; From: Jason Murray &lt;[e-mail]&gt;
  &gt; To: Michael Clay &lt;[e-mail]&gt;
  &gt; cc: Larry Ruzzo &lt;[e-mail]&gt;, [e-mail]
  &gt; Subject: Re: HW1
  &gt; 
  &gt; On Thu, 4 Apr 1996, Michael Clay wrote:
  &gt; 
  &gt; &gt; On 3 Apr 1996, Larry Ruzzo wrote:
  &gt; &gt; 
  &gt; &gt; &gt; #3.2: There's a crucial bug in the text related to this problem ---
  &gt; &gt; &gt; in the first sentence in the paragraph preceeding corollary 3.8
  &gt; &gt; &gt; (p122), it is *NOT* true that D will always halt if N does.  In
  &gt; &gt; &gt; particular, D will run forever on any input w that N rejects, even
  &gt; &gt; &gt; though N halts on all paths on input w.
  &gt; &gt; 
  &gt; &gt; Why does N run forever?  What is it doing, once it has run out
  &gt; &gt; of &quot;lexicographically next strings&quot;?  Besides halting in a reject
  &gt; &gt; state, that is.
  &gt; 
  &gt; It doesn't run out of lexicographical next strings.  It doesn't say 
  &gt; anywhere that it halts in a reject state.  The only way to make it halt 
  &gt; is with an excepting state.

small clarification: that particular algorithm never enters a reject
state; other TM's sometimes do and they always halt if they do.  (I
was afraid someone would misread your statement as saying that
q_reject is not a halting state; it is.)
<hr size=4><a name="828684564001">Date: Thu, 4 Apr 1996 22:09:19 -0800 (PST)
From: <b>Michael Clay &lt;[e-mail]&gt;</b>
To: Larry Ruzzo &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>Re: HW1</b>
</a>



On 4 Apr 1996, Larry Ruzzo wrote:

&gt;     I think that this text has enough bugs and the rug has been pulled 
&gt;     out from under us enough times on this assignment, that the entire 
&gt;     *assignment* should be due Monday, not just 3.3.  
&gt; 
&gt; hmmm...  I think there was only that one bug relevant to this
&gt; assignment (which is listed on sipser's web errata page by the way),

It wasn't in the errata last week (last updated 2/5/96.)
Interestingly enough, the errata (last updated 3/27/96) now
shows that you submitted this bug 3/29/96.  Is the author 
psychic or do we need errata for the errata.

&gt; so I don't think you should need more time, but if you really really
&gt; want it, I guess I could take #3.2 on monday also.

Am I the only one who has gotten stuck beating his head on the 
first (buggy) problem and second (not covered yet) problem?  
If so, I would have expected to see more questions on the following
problems than have been posted to the group.

I personally didn't finish the third problem till just a few minutes 
ago and am not looking forward to working on the fourth and fifth 
problems till the wee hours of the morning.

&gt; By the way, I hate having a book with errors, too.  So far, even
&gt; though this one is labeled &quot;Preliminary edition&quot;, I havn't found it
&gt; any worse that 10 year old n-th editions I've used, and the online
&gt; errata list is much better than usual.

My more cynical side suggests that the errata list is short because
the text hasn't been around long enough to collect many bug reports.  
(The earliest listed erratum is only 11/22/95!)

&gt;                                         The good news should be that
&gt; KNOWING there are errors in the book might nudge us all to read
&gt; it more carefully -- not an altogether bad habit.

This would be pretty dense reading even without the bugs.
Just my 2 cents worth.

See you after problem# 4.

	Michael ([e-mail])

<hr size=4><a name="828945735001">Date: 7 Apr 1996 23:39 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>Office Hours This week</b>
</a>

Jayram and I are switching our monday/friday hours this week:
    Monday 4/8 : 1:00-2:00 ruzzo  sieg 415
    Friday 4/12: 1:00-2:00 jayram sieg 326 (I think)
<hr size=4><a name="829715127001">Date: 16 Apr 1996 21:18 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>Re: CSE431: Hw #2 questions</b>
</a>

    I have a couple of questions I hope you can answer for me.  In
    ex. 4.17 is the language C accepting prefixes of the strings D
    accept?

Not quite.  In &quot;xy&quot;, x is a prefix, perhaps without any clear
boundary marking the end of x from the begining of y, but in &quot;&lt;x,y&gt;&quot;
they're encoded so that the boundary between x and y is clearly
visible.  E.g. perhaps x and y are from an alphabet like {0,1} that
lacks the &quot;,&quot;, &quot;&lt;&quot;, and &quot;&gt;&quot; characters, and &quot;&lt;x,y&gt;&quot; means literally
stick x and y together with those three punctuation characters.

    In doing our proof I assume we as usual have got to show both
    directions of the statement we are to prove.  In this case, we
    would have to show 1) when C is enumerable we must construct D
    and 2) when we have D that C is enumberable, is this correct or
    am I totally off on a tangent here?

Just right.
<hr size=4><a name="829723132001">Date: 16 Apr 1996 23:20 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>Re: CSE431: Hw #2 questions</b>
</a>

    In ex. 3.9 &amp; 3.10 is it sufficient to give informal descriptions
    of the TM's that would accept these languages?  Also I have some
    trouble seeing the difference between 3.9 &amp; 3.10.  When doing
    3.9 I'm constructing TM's that accept these languages (i.e. when
    concatenating L=L1L2) and using the &quot;sublanguages&quot; (in this case
    L1 and L2) as subroutines.  In 3.10 couldn't I just do the same
    while just being careful from depending on subroutines that
    might loop?

Yes, the key difference between 3.9 and 3.10, i.e. between deciders
and acceptors, is that you must be careful that the former
always halt, and that looping in the later doesn't cause inputs
to be rejected when you don't want them to be rejected.

&quot;Informal descriptions&quot;: through out the rest of the quarter, unless
otherwise specified, I want &quot;high level descriptions&quot; as discussed
on page 127.

 Two small points: 
  1) in 3.9 you're constructing TM's that &quot;decide&quot; these languages,
not merely &quot;accept&quot;.
  2) L1 and L2 aren't subroutines, although machines that
decide or accept them can be.  I hate to be pedantic about small
points like this, but I think students get themselves confused,
sometimes deeply confused, by a collection of small things like
this.  L1 is a language, i.e. a set of strings; if L1 is decidable
there is some program/TM, say M1, that distinguishes those strings
in L1 from those strings not in L1. (And there may be lots of other
programs that can also do this job.)
<hr size=4><a name="829742010001">Date: Wed, 17 Apr 1996 04:53:23 -0700 (PDT)
From: <b>Larry Roske &lt;[e-mail]&gt;</b>
To: Larry Ruzzo &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>Re: CSE431: Hw #2 questions</b>
</a>

I see that for enumerable union we need to avoid looping to
check acceptance by one OR the other TM, but is this necessary
for enumerable cat, star, and intersection since if the
first TM loops (in cat or intersection) this doesn't accept
which is what we want anyway in these cases?

On 16 Apr 1996, Larry Ruzzo wrote:

&gt; Yes, the key difference between 3.9 and 3.10, i.e. between deciders
&gt; and acceptors, is that you must be careful that the former
&gt; always halt, and that looping in the later doesn't cause inputs
&gt; to be rejected when you don't want them to be rejected.
&gt; 
<hr size=4><a name="829755533001">To: Larry Roske &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>Re: CSE431: Hw #2 questions </b>
In-reply-to: Your message of &quot;Wed, 17 Apr 1996 04:53:23 PDT.&quot;
             &lt;[e-mail]&gt; 
Date: Wed, 17 Apr 1996 08:38:40 PDT
From: <b>------------------------------------------------------------------------ &lt;[e-mail]&gt;</b>
</a>

&gt;&gt;&gt;&gt;&gt; &quot;LR&quot; == Larry Roske &lt;[e-mail]&gt; writes:

LR&gt; I see that for enumerable union we need to avoid looping to check
LR&gt; acceptance by one OR the other TM, but is this necessary for
LR&gt; enumerable cat, star, and intersection since if the first TM loops
LR&gt; (in cat or intersection) this doesn't accept which is what we want
LR&gt; anyway in these cases?

You have to be careful about concatenation and star. Note that if w
belongs to K.L for two languages K and L, w can be written as uv,
where u is in K and v is in L. BUT the crucial thing is that the
decomposition is **not known in advance**, meaning that
w itself does not encode where u ends and v begins.
Furthermore, the decomposition may not be unique.

Contrast this with the language 
{ &lt;u,v&gt; | u in K and v in L }
where from the input w=&lt;u,v&gt;, we can extract the two parts u and v in
a unique way.

Similar remarks apply for star as well.

-jayram.


<hr size=4><a name="829756248001">Date: 17 Apr 1996 08:49 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: Larry Roske &lt;[e-mail]&gt;
Subject: <b>Re: CSE431: Hw #2 questions</b>
Cc: [e-mail], Larry &lt;[e-mail]&gt;
</a>

that's OK for intersection, but not clear to me for cat or star.
<hr size=4><a name="829850875001">To: cse431@cs
Subject: <b>statistics for hw1</b>
Date: Thu, 18 Apr 1996 11:07:46 PDT
From: <b>------------------------------------------------------------------------ &lt;[e-mail]&gt;</b>
</a>

Low: 22
High: 48
Avg: 39.1

Each question was worth 10pts for a total of 50.
-jayram.
<hr size=4><a name="829940288001">Date: Fri, 19 Apr 1996 11:58:00 -0700
From: <b>jayram@curie (Jayram Thathachar)</b>
To: cse431@cs
Subject: <b>office hours today</b>
</a>

Prof. Ruzzo will not be holding office hours today. Please send mail
to him if you need to meet him.

-jayram.
<hr size=4><a name="830203567001">Date: 22 Apr 1996 13:03 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>Office hours/Midterm</b>
</a>

1) Effective today, Mondays 1:00-2:00 office hour will  be Ruzzo
(415 sieg) &amp; Fridays 1:00-2:00 will be Jayram (sieg326).  I.e. times
are unchanged, but we've traded days.  Other previously announced
hours are unchanged.

2) MIDTERM will be in class, Monday May 6.
<hr size=4><a name="830322083001">Date: 23 Apr 1996 21:57 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: David Mears &lt;[e-mail]&gt;
Subject: <b>Re: Homework #3, 5.7</b>
Cc: cse431@cs
</a>

  &gt; Date: Tue, 23 Apr 1996 21:28:37 -0700 (PDT)
  &gt; From: David Mears &lt;[e-mail]&gt;
  &gt; Subject: Homework #3
  &gt; 
  &gt; Problem 3 ( exercise 5.7 ) on the new homework has me wondering what the
  &gt; definition of an 'enumerable problem' is.  It seems like it should go 
  &gt; something like this:
  &gt; 
  &gt; We say that a problem is enumerable if it can be restated as a test for 
  &gt; membership in an enumerable language.
  &gt; 
  &gt; Is this correct?

yes.  I'd even go further and say, at least for purposes of this
exercise, that &quot;enumerable problem&quot; and &quot;enumerable language&quot; are
synonyms.
<hr size=4><a name="830456544001">Date: 25 Apr 1996 11:20 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>Partner's</b>
</a>

If you have NOT yet arranged a partner for prob 1 on the next HW
assignment, please let me know as soon as possible.
<hr size=4><a name="830537716001">Date: Fri, 26 Apr 1996 09:55:11 -0700 (PDT)
From: <b>Michael Clay &lt;[e-mail]&gt;</b>
To: [e-mail]
</a>

The errata list has more than doubled since the start of class, including 
some new errata for chapter 5.  If you haven't downloaded the errata list