01:38:11 -!- calamari has quit ("Leaving").
02:28:47 -!- mitte has joined.
02:38:14 -!- Sgep has quit.
02:44:46 -!- calamari has joined.
02:55:58 -!- calamari has quit ("Leaving").
04:00:50 -!- marcan_ has joined.
04:05:47 -!- marcan has quit (Connection timed out).
05:06:20 -!- mitte has left (?).
07:39:14 -!- kipple has joined.
07:41:50 -!- marcan_ has quit (Success).
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
08:02:03 -!- marcan has joined.
09:10:16 -!- CXII has joined.
09:17:23 -!- CXI has quit (Nick collision from services.).
09:17:25 -!- CXII has changed nick to CXI.
09:32:08 -!- puzzlet has quit (Read error: 110 (Connection timed out)).
11:40:40 -!- puzzlet has joined.
12:11:24 -!- int-e has joined.
13:11:54 -!- puzzlet has quit (brown.freenode.net irc.freenode.net).
13:11:56 -!- tokigun has quit (brown.freenode.net irc.freenode.net).
13:12:40 -!- puzzlet has joined.
13:12:40 -!- tokigun has joined.
13:45:06 -!- jix has joined.
13:58:25 -!- puzzlet has quit (brown.freenode.net irc.freenode.net).
13:58:25 -!- tokigun has quit (brown.freenode.net irc.freenode.net).
13:58:41 -!- puzzlet has joined.
14:01:43 -!- tokigun has joined.
14:11:14 -!- tokigun has quit (brown.freenode.net irc.freenode.net).
14:11:15 -!- tokigun has joined.
14:45:41 -!- kipple has quit (Read error: 104 (Connection reset by peer)).
14:46:33 -!- kipple has joined.
16:54:43 -!- Keymaker has joined.
17:02:53 -!- lirthy has quit ("in truth there is no better place to be").
17:08:50 -!- lirthy has joined.
18:06:51 -!- int-e has left (?).
18:27:22 -!- Keymaker has left (?).
18:48:43 -!- int-e has joined.
19:17:01 -!- int-e has left (?).
20:31:25 -!- calamari has joined.
20:38:20 -!- jix has quit ("Bitte waehlen Sie eine Beerdigungnachricht").
21:11:29 -!- Sgep has joined.
21:36:26 <calamari> hmm.. I wonder if it is possible to simulate a Turing machine that is possibly a decider, or whether I can only simulate a recognizer
21:36:54 <calamari> (I mean if the TM is possibly a decider or a recognizer, but I don't know which)
21:37:22 <calamari> err strike that.. makes no sense :)
21:38:25 <calamari> the halting problem I think tells me that I can't simulate a TM and produce a decider
21:46:36 <Sgep> decider? recognizer?
21:46:51 <calamari> <calamari> err strike that.. makes no sense :)
21:47:44 <calamari> the only recognizers I know of are for TM's and Tron.. hehe
21:49:29 <calamari> hmm, actually maybe it would work
21:49:44 <calamari> if the simulation got to a reject state then it would reject
21:50:00 <calamari> I was getting confused with nondeterministic TM's
22:12:16 -!- Arrogant has joined.
22:20:05 -!- Keymaker has joined.
22:20:37 <Keymaker> bertram and daniel have posted very short entries..
22:24:34 <Keymaker> i can't wait to see their solutions
22:25:31 <calamari> I unfortunately can't justify writing an entry :( too much homework .. working on it now even
22:26:13 <calamari> maybe I can extend the deadline a couple weeks.. (just kidding)
22:26:31 <Keymaker> what time is it over there now?
22:27:29 <calamari> wow.. my watch is over 12 minutes off from them real time
22:27:57 <Keymaker> hmm, when i wake up tomorrow, the competition has ended. nice :D
22:28:15 <Keymaker> then i can get to see the others' entries..
22:28:48 <calamari> yeah.. although I still need to write the test cases
22:28:54 <Keymaker> well, in case nobody else enters i'm kinda "third" ;)
22:28:59 <calamari> and that won't be happening until after finals
22:29:14 <Keymaker> 1. file with only one new-line
22:29:27 <Keymaker> 2. file with few ks of "abc" pattern
22:29:28 <calamari> I have 11 different orderings of a b and c I need to test for :)
22:29:59 <Keymaker> remember to have some long tests, over 255 chars of each
22:30:20 <calamari> I'll probably write some randomly generated tests as well
22:30:46 <calamari> but everyone will be tested with the same things, for fairness
22:31:24 <calamari> ok, afk to continue my thrilling proof of the equivalence of a 2 stack PDA and TM
22:44:07 <fizzie> Are you doing that just for fun, or is it an exercise of some sort?
22:44:21 <fizzie> Can't you just say it's obvious that they're equivalent? :p
22:50:21 <fizzie> Heh, on the 'introduction to theoretical computer science' course we mostly had to just design TMs for various languages. Though there were some "prove foo" exercises, too.
22:53:35 <Gs30ng> the more powerful model of computation, TM > PDA > FSA, right?
22:54:07 <calamari> TM > decider > nondeterministic PDA > deterministic PDA > FSA
22:54:29 <Gs30ng> iirc PDA has it's own stack-like data management system
22:55:09 <Gs30ng> FSA does not, but PDA has one stack-like thing
22:55:26 <Gs30ng> so i think that term '2 stack PDA' is a little bit weird
22:56:30 <calamari> on the homework it is described as a k stack PDA, where k=0 an NFA, k=1 a normal PDA
22:57:04 <calamari> NFA being a nodeterministic FSA
22:57:36 <calamari> NFA's and FSA's are equally powerful
22:57:49 <calamari> as are TM's and nondeterministic TM's
22:58:24 <fizzie> And n-track TM's and n-tape TM's, although that's somewhat obvious too.
22:58:30 <calamari> there is some question whether a probabilistic TM is more powerful than a normal TM.. at least according to wikipedia
23:05:03 <calamari> argh.. PDA's don't give EOF.. messing up my proof. hehe
23:17:05 -!- Sgep has quit.
23:22:57 -!- kipple has quit (Read error: 110 (Connection timed out)).
23:27:56 -!- Sgep has joined.