... Yes, it is an encoding. To encode a Turing Machine, first assume that the start state is always q_1 and the final state (and there can be only one final...
It is trivial to prove that S={e|M_e accepts the string 00} is c.e. My proof is below. Is there some sort of step missing? Am I assuming the proof is unduly...
... When I took the theory course it was assumed "no". I don't remember seeing a theorem which uses this assumption as a necessity, though. Best, Tony...
... Yes. See pages 324-325 of Hopcroft, Motwani, and Ullman[1] for an example of a Turing machine that does just this. If you don't have the above text, see...
Hi, everyone. The minimal description of x, written d(x), is defined as by Sipser's book (p.215 ), "The shortest string <M,W> where TM M on input w halts with...
Hi gridkim, ... Remember that d(x) is of the form <N>w, where N is a TM that on input w, outputs x. So <M>d(x) looks like <M><N>w. Now by M's definition, it...
First of all, thanks for replying, binarygrrl and pnenp. That was very helpful. I am thinking about majoring in A.I area. Before I get down to that area, I am...
Enderton's book is helpful. Cori and Lascar have a two-volume set on mathematical logic. Also, Professor Monk at University of COlorado at Boulder keeps a nice...
Hi Kim, For an introduction to logic with a strong computer science slant, I would recommend "Computability and Logic" by Boolos and Jeffrey. For a more...
I am interested in the algebraic approach to the theory of computation, developing the theory of automata and formal languages in terms of abstract algebra. I...
... Abraham Ginzburg: Algebraic Theory of Automata -- "a totalitarian ideology that hates freedom, rejects tolerance, and despises all dissent." --- Bush...
Hi Mark, I'm not personally familiar with this text, but "Finite Automata" by Mark V. Lawson looks like it might serve your needs. It starts out with a more...
Hi, I m happy to introduce myself as Krishna,from bangalore.Joined an SW Co. here out of college. I m very much intersted in Theory of Computer Science. My...
Hi everyone.. I need help about graph theory ( network problems ,Critical points edges) .. I have below problem . Does anyone know any existence algorithms...
I'm sorry I think I said it wrong, I've just reread the problem.. for the critc link is was wondering, you could make something like .. for each subgraph...
The vertices of graph can be divided into two partitions - blocks and cut-vertices. These cut-vertices refer to the critical nodes that you mentioned. A...
Hi, I am a recent graduate of Dartmouth College and am working with young alumni from around the country to promote a new non-profit, online database of...
Hi Peter, The database for thesis papers is a nice idea, but I'm not sure why you restrict access to the database if your aim is to expose this research to a...
Kurt, Harlan Mills, in _Software Productivity_, mentions that formal languages are fundamentally algebraic, despite widely different notations due to ...
Hi, Mark. I think that you might find the books listed below to nicely suit your needs. Based on the table of contents of the book you cited, I'm thinking...
Hi Peter, Okay, I retract my comment about survey papers. (By the way, that wasn't meant to be pejorative; a well written survey paper can be very valuable...
Hi Mark, I don't know very much about this area, but there should be others on the list who might be able to add to the discussion. The impression I have...
Given: a set of positive integers {x1,x2...xn} and another positive interget k. Query: Is there a set of indices I, which is a subset of {1,2....n}, where...
Dear members, I am a Research Scholar (Computer Science) in T.I.F.R.,India.I am doing my PhD(1st year)in Graph Algorithm.Can anyone of you suggest me about...
Hi Mark, Well, I think I need to retract myself, yet again. Here's an interesting link I came across, for a workshop to be held at Berkeley next summer: ...
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.
