Hi, ... size of ... Well, it depends on how exactly we're specifying the problem. If the machines need to start with a blank tape (or other input device), and...
Hi all, Now that we've all had a nice vacation, let me see if I can get my mind back into gear and start looking at Sipser again. For week 19 we cover section...
Hi Charlie, After reading your note I'm not quite sure if we're in agreement or not...it seems like your concerns have more to do with philosophical issues...
Hi all, It looks like so far only Charlie has posted anything about the chapter 6 problems. ... Charlie's answer (it's quoted below) is in the spirit of the...
... The identity relation on any set works. R_1 = { (x,x) | x in X } ... This seems to describe an linearly ordered set. Take X to be the integers, R_1 as...
Lieven Marchand
mal@...
Jan 5, 2002 10:28 am
342
Hi Lieven, ... First order logic. Since I omitted these details when I gave the section summary, maybe I should mention a few things now for anyone who is not...
Hi all, Here is problem 6.11 again: Let (N,<) be the model with universe N (the natural numbers) and the "less than" relation. Show that Th(N,<) is decidable....
Hi everyone, For this week we cover section 6.3 in Sipser, "Turing reducibility". This is such a short section that I had originally just tacked it onto...
Hi, Here are some problems that deal with the material on Turing reducibility: 6.7 Show that for any two languages A and B, a language J exists where A <=T J...
Subj:[comp-sci-theory] Digest Number 52 Date:1/8/02 4:40:13 AM Eastern Standard Time From:comp-sci-theory@yahoogroups.com To:comp-sci-theory@yahoogroups.com ...
Hi Charlie, Thanks for taking the time to post on this problem. (I think there are some technical glitches in your post, although it doesn't really matter.)...
In a message dated 1/13/02 11:47:39 AM Eastern Standard Time, ... Please advise. Accuracy matters. ... Yes, that is what I meant by there being a theorem...
... there ... really ... Sorry, all I meant was that there seems to be a font problem with viewing this section in my browser: [Proof: Consider the predicate...
Hi all, Let's see if we can dispense with some of the previous problems before we start into section 6.4. The only problem from section 6.2 that we haven't...
Hi again, Ok, now it's time for the section 6.3 problems. 6.7 Show that for any two languages A and B, a language J exists where A <=T J and B <=T J. I think...
Hi everyone, Next week we start on part 3 of Sipser, "Complexity Theory". But first we finish up chapter 6 with section 6.4, "A definition of information", on...
Hi all, So we've defined the descriptive complexity K(x) of a string x, and proved a couple basic results. Now it's time to show how our definition compares...
Hi again, Let me finish up my summary of section 6.4. Sipser gives two more results in this section. I won't bother to give the proofs for these unless...
Hi, Here are the chapter 6 problems that deal with the material from section 6.4. 6.13 Show how to compute the descriptive complexity of strings K(x) with an...
Hi, There is one problem in chapter 6 for which it isn't obvious to me what section it applies to. *6.19 Let A and B be two disjoint languages. Say that...
Hi everyone, Here's a news item that's being discussed on the theory-edge list (thanks, Vlad), that couldn't be more timely for what we're studying right now. ...
Hi everyone, I'm a little surprised at how quiet the list has been lately, but maybe that's a good thing considering what the alternative could be. Let's see...
... As a hint, what's wrong with this argument? Given a TM for x and y, we can construct a TM for xy in size K(x)+K(y)+O(1) where the constant depends on the...
Lieven Marchand
mal@...
Jan 20, 2002 4:11 pm
360
Hi Lieven, ... the ... I'm supposing that what you have in mind is that we would use the scheduling TM M to describe the string xy as <M><X>p<Y>q (where <X>p ...
Hi everyone, We've reached the point in Sipser where we start on the third general topic, complexity theory. I'd like to just pause for a moment and say ...
Hi everyone, It's been awfully quiet lately on the list. That's also true for some other lists that I follow...I wonder if something's going on in cyberspace....
Hi all, My apologies to those of you received message #363...one small drawback to having an unmoderated list is that stuff like that occasionally slips...
Hi all, I hope everyone is doing well. This is my second 'week 23' post; the first one seems to have disappeared into the ether(net). So if it eventually...
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.
