Hi folks, My name is Henry Chou. I'm current a CS graduate student in the University of Florida. Our formal languages and computation theory course uses...
Hello, How goes the proof that the time hierarchy theorem relativizes for any oracle? can anyone give an example of a proof that doesn't relativize? thanks...
... There are indeed proofs that don't relativize. I remember that there is a result stating that MA is included in PP whereas this is not the case under some...
... proof ... The time hierarchy theorem relativizes. :) ... for any ... there is ... the case ... not dig ... relativize! ... oracles ... be ... result) ... ...
I want to show that it is undecidable to determine whether a Turing machine halts on an input word that has an even number of symbols. Here is what I did: ...
I am given the two sets: L1={e|M_e accepts at least 481 different inputs} L2={e|M_e accepts at most 481 different inputs} I am to decide which one is c.e. and...
Unfortunately, your proposition does not work. First let me introduce some notation. Let <M> be the string representation of the Turing machine M. So: S_all...
Hi friends. It is proven that is L is a Context-free language, head L is also Context-free language. How I can create this Context-free grammar from grammar of...
Dear Mr. Saravanan We have been waiting for your mail. Kindly send us the pre-requisite material. ... YAHOO! GROUPS LINKS Visit your group "comp-sci-theory" on...
The problem doesn't say anything about P_even not halting on odd-length input words. It just says it does indeed halt on even length inputs. I still think my...
Dear Michael or whoever chooses to answer, ... To construct R, could you not have on the input tape of R all the words in the universal language separated by...
Hi all. I'm Mike Christoff, the moderator of Computer Science Theory. I just wanted to welcome all of our new members to the group. I hope you find your stay...
I have it this time. I am going to reduce the halting problem to P_even. See below. ______________________________________________________________ Given e...
I can now prove L2={e|M_e accepts at most 481 different inputs} is not c.e. See below. _____________________________________________________________ Let ...
My prior proof of why L1 is c.e. is completely bogus. It assumes what it sets out to show. I go back to my original idea of running M in parallel on all words...
computation process for a word w. I know it's decidable for moves consecutively two times to the right. but seems not work for the three times version. Can...
Recently, Reingold showed that undirected s-t connectivity is in logarithmic space. It seems straightforward that this algorithm must be optimal in space...
... thanks. ... Undecidable. Suppose it is decidable by a TM M. Consider the following TM algo: On input w, considered to be the encoding of some TM N, ...
Hello, When i do #strings /proc/kcore as root i get the following error. strings: /proc/kcore: Operation not permitted I run fedora core 3. My kernel version...
... From: comp-sci-theory@yahoogroups.com [mailto:comp-sci-theory@yahoogroups.com]On Behalf Of ptt_hatred Sent: Monday, October 24, 2005 5:11 AM To:...
let s={<M>|M is a turing machine that accepts wr whenever it acceptes w}.Show that s is undicidable. wr is the reverse of w and r is superscript. First way to...
Hi Tony, ... Hmmm, you mean that you found a statement of the optimality of this somewhere, but no references or links to a proof? ... You mean space...
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.
