Hello group members. Just forwarding a message from Yahoo groups. They will be getting rid of any file attachments made to emails soon, so please save any...
I know "halting problem" is undeciadable ,but what means the reachability problem of Turing machine is undecidable?? can someone give me further explaination...
Where did you find this problem? Is it in Sipser? (A quick glance at the index of Sipser and the exercises in Chapter 5 didn't reveal it.) If the...
Lawrence L Larmore
larmore@...
Aug 2, 2003 2:42 pm
1180
Is this the same as "useless states" ? (4.20 in Sipser, which is for PDA's and not TM. Of course it could be rephrased for TM's. ... glance at the ... reaches ...
... There are two problems that people refer to as 'reachability'. The first is "Given a directed graph G and two vertices s and t of G, decide if there exists...
Dear all, Hi I'm Wendy! friends call me Akimi. I'm a comp-sci student. I found comp-sci- theory groups in www, and found the topics and the people great. I...
Hi Akimi, Nice to see you in the group! I think when we worked through chapter one of Sipser (gosh, that must have been a couple of years ago now), we skipped...
Kurt, Use the definition of the equivalence relation "distinguishable by L" in Problem 1.34 on page 89 of Sipser, and let L be the language given by the...
Lawrence L Larmore
larmore@...
Aug 6, 2003 3:12 pm
1187
OOPS! MISTAKE! ... The distinguishing string is 0^{i-1}. Sorry ... ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ! Lawrence L....
Lawrence L Larmore
larmore@...
Aug 6, 2003 4:30 pm
1188
Hello, I am tracing a result from Babai, fortnow, and Lund. It is at http://citeseer.nj.nec.com/15039.html The paper used a lemma (lemma 5.8) from David...
Hi Kurt, Wow, thanks for welcoming me! My reply is late...pls. blame it the timezone barriers. But next semester I will be almost the same timezone as you are....
Hi Kurt, Wow, thanks for welcoming me! My reply is late...pls. blame it the timezone barriers. But next semester I will be almost the same timezone as you are....
I am now reading book"introduction to automata theory" (written by John E.Hopcroft 1979 version) I cann't understand what is meaning "crossing sequence" in...
... I don't have that book handy but we've discussed crossing sequences of Turing Machines on this list already. In general, you position yourself at a certain...
... in fact , it defined as following: The list of states below each boundary between tape squares is termed a crossing sequence. and 2dfa just means that the...
... The crossing sequence is taken for a particular cell, and for an automaton like yours, would consist of 1 element, since your automaton is never going to...
thank you very much. now I know what is the probelm of my understanding,this is, the definition of crossing sequence, I should see it from vertical view ,not...
Hi group, I was wondering about this question : If f is a correspondence from N to N and L = {a^f(i)b^f(i) i >= 1 } ; ( a raised to f(i) followed by b raised...
Of course there are examples of $f$ that will make the language undecidable. Clearly L is always a subset of ${ a^n b^n : n \in N}$. So given a $a^n b^n$ we...
Hi group, I was wondering about this problem. Suppose we want to prove that Hitting-Set with k=3 is NP-complete. Is it OK to prove that : Vetex Cover (n,3)...
... I will answer question #2 first. The answer is yes; every language that is NOT recursive is accepted by a finite number (namely 0) of TMs. (This is because...
hi all. havent been scanning this group but just went thru last batch of posts. nice to see lots of new faces. fyi, I just ran across this via google & was...
... Yes, it is. Given a deterministic TM M, it is easy to check whether M satisfies the desired conditions. So we just keep enumerating TMs and see whether one...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
