00:00:11 AnMaster, I've got a good chunk of the conversation, although from around halfway in. 00:02:48 Does Co-NP = NP? 00:03:02 http://sprunge.us/OgDa has some stuff 00:03:09 that's an unsolved problem, it's believed to be false. 00:03:24 Lawl, Madk marked Schrodilang while on his Madkap adventures of finding pages to delete :P 00:03:39 oerjan: Indeed, and seems somewhat more interesting than P?=NP, at least to me right now 00:04:00 cpressey: well P=NP would imply NP=co-NP 00:04:16 -!- MizardX has joined. 00:04:30 Sure, but everybody knows that P!=NP. The argument there is simple: A lot of very smart people have been trying to prove that P=NP and have gotten nowhere ;) 00:04:33 also if NP=co-NP then NP is so called _low_ for itself (you can answer NP questions freely inside an NP computation) 00:04:48 -!- augur has joined. 00:05:29 and then all that oracle hierarchy stuff NP^NP^NP^... collapses 00:05:38 Yes. 00:06:00 just like it did for NL when NL = co-NL was proved 00:06:35 NL being? 00:06:45 nondeterministic logarithmic space 00:06:48 ah 00:06:55 Wait, I have just realised that checkShips() doesn't do what I thought it did. 00:08:14 L \subset NL \subset P \subset NP \subset PSPACE is a famous sequence of inequalities. with the exception of L, NL != PSPACE none of those are proved to be different 00:08:21 oerjan: I have some ideas about co-NP, but they involve algorithmic information theory, which is somewhere I should probably not be treading. 00:10:09 oerjan: If we could prove P < Co-NP, we prove P < NP, don't we? 00:10:16 sure 00:10:43 P = Co-P and Co- respects inclusion 00:13:55 I don't stand a icecube's chance in hell of actually proving this, but I might as well give it a go, just to understand more about it. It's enlightening to see a conjecture crash on the rocks sometimes. 00:14:27 you know I don't think an icecube could prove much of anything.. 00:14:34 except maybe some physics 00:14:45 if we accept a very vague notion of prove 00:14:48 -!- genjix has joined. 00:14:55 It ... proved itself useful in keeping my drink cool? 00:15:15 ...that gets both a "ha" and a facepalm. 00:16:45 icecube proves second law of thermodynamics 00:17:23 in a tragic heroic manner 00:19:46 Complete guess: SAT with monotonic sentences (no NOT) is in P. Maybe even a greedy algorithm 00:20:11 You know, 00:20:14 if you set all variables to true, then it has to be true iff there is any satisfying answer at all 00:20:19 Exactly. 00:20:40 I still don't know why the bug manifested itself worse given some code and not as bad other code, but it seems to be completely squashed 00:20:58 also, monotonic circuit evaluation is P-complete 00:21:28 What about monotonic TAUT? 00:21:44 set all variables to false 00:21:46 -!- genjix has left (?). 00:22:26 oerjan: then it's just false 00:22:44 x AND y is not a tautology, but x AND x is 00:22:54 assuming you actually _have_ any variables 00:22:56 um no 00:23:04 it most certainly is not :D 00:23:06 wait yeh 00:23:41 the constant true is the only monotonic tautology 00:24:08 yes. 00:24:21 I was getting there, slowly :) 00:24:47 i recall a theorem related to the clones of post's lattice: basically satisfiability is in P unless the clone includes the implication function, in which case it's NP-complete 00:24:50 OK, I'm compiling Battleships. If I die, tell someone. 00:24:56 Clearly, its paucity of tautologies means that monotonic logic is superior. 00:25:39 oh not implication, but non-implication 00:26:06 http://en.wikipedia.org/wiki/Post's_lattice#Applications 00:27:29 presumably tautology is co-NP-complete iff it contains the dual of that function 00:27:38 Good old Post. 00:27:42 FUN FACT 00:27:48 He invented the Turing machine :o 00:28:09 And then went on to found his cold cereal empire 00:28:11 O_o 00:28:44 cpressey: i assume that's an american-only pun 00:29:21 oerjan: probably. http://www.thethriftymama.com/wp-content/uploads/2010/01/post-raisin.jpg 00:30:06 non-implication is A and (not B), so the dual is A or (not B), hm that's just implication reversed 00:30:08 Phantom_Hoover: HELLO? HELLO? ARE YOU STILL THERE? 00:30:11 OH GOD NOOOOOOO 00:30:16 He shouldn't have done it 00:30:22 THE FIRST DAY OF ETERNITY I CAN SEE IT NOW 00:30:47 Some days I love this channel. 00:31:03 Anyway, g'night folks :) 00:31:06 -!- cpressey has quit (Quit: Leaving.). 00:31:07 bye 00:31:15 http://pastebin.com/8EmX5cpS is my first game. 00:31:44 Note that all ships are on (1,1) and player 1's first hit takes out all of player 2's ships. Yet player 2 wins. 00:31:57 Phantom_Hoover: AWESOME 00:31:58 X-D 00:32:12 Gregor-W, omygodlet'smicrocosmit 00:32:20 omygodyes 00:32:24 It can be our flagship game! 00:32:35 a famous theorem is that _intuitionistic_ implication has PSPACE-complete satisfiability 00:32:43 Phantom_Hoover: Excuse me, I have to go sodomize myself with a rake first. 00:32:50 OK, you need to s/conio.h/termios.h/ and s/getche/getchar/ 00:33:12 OK, need to sleep. 00:35:59 maybe every set of boolean functions is either trivial or np-complete 00:36:07 I'M WAY BEHIND YOU 00:36:34 -!- Mathnerd314 has quit (Ping timeout: 260 seconds). 00:36:37 -!- Mathnerd314_ has joined. 00:36:48 -!- Mathnerd314_ has changed nick to Mathnerd314. 00:37:57 -!- Phantom_Hoover has quit (Ping timeout: 245 seconds). 00:48:08 typeof(document.createElement("object")) == "function"; typeof(document.createElement("function")) == "object"; 00:55:09 fancy. 01:01:00 -!- augur has quit (Remote host closed the connection). 01:18:22 Attention anyone who hasn't yet: Vote in the poll in the /topic. kthx :P 01:20:51 -!- ski has quit (Ping timeout: 264 seconds). 01:24:02 -!- dbc has quit (Ping timeout: 246 seconds). 01:24:31 -!- dbc has joined. 01:26:37 -!- Gregor-W has quit (Quit: Page closed). 01:27:35 -!- ski has joined. 01:37:49 Gameplay now differs between DEBUG and RELEASE 01:48:54 lol 01:48:57 what changelog is this? 01:49:28 hmm... more people should vote for the last option, then we should do it anyways 01:50:52 coppro, it's my project 01:51:05 There is a reason for it, though 01:51:19 The change made to Release makes it difficult to repeatedly play the same puzzle 01:51:28 So I decided that it made sense to omit it from Debug 01:53:23 ah 01:53:32 I guess that makes sense 01:53:39 although you might provide another means 01:53:51 * coppro knows a game where -DCHEATS does all sorts of fun stuff 01:54:27 DEBUG partially means cheats at this point 01:54:39 Mostly, actually 01:54:52 things like the ability to edit any puzzle, warp, etc. 01:54:55 Oh, and occasional verbose output into chat 02:49:55 -!- SevenInchBread has joined. 02:52:10 -!- CakeProphet has quit (Ping timeout: 258 seconds). 02:58:13 -!- sshc has quit (Read error: error:1408F10B:SSL routines:SSL3_GET_RECORD:wrong version number). 03:00:29 -!- sshc has joined. 03:18:49 -!- BeholdMyGlory has quit (Remote host closed the connection). 03:36:13 -!- coppro has quit (Ping timeout: 276 seconds). 03:37:28 -!- coppro has joined. 03:39:48 -!- derdon has quit (Remote host closed the connection). 03:44:42 * Sgeo learns the value of naming conventions the hard way 03:49:52 * pikhq points, mocks 03:49:55 -!- Wamanuz has quit (Read error: Operation timed out). 03:52:30 Well, that's headache inducing 03:53:21 http://pastie.org/1064906 03:56:54 Woops 03:57:00 * Sgeo makes it a decimal parse 04:03:29 -!- jcp has quit (Quit: Later). 04:32:33 -!- GreaseMonkey has joined. 04:54:37 -!- augur has joined. 04:55:55 -!- jcp has joined. 05:02:09 -!- sftp_ has quit (Read error: Operation timed out). 05:11:40 -!- cheater99 has joined. 05:12:02 -!- SevenInchBread has quit (Ping timeout: 240 seconds). 05:16:27 -!- CakeProphet has joined. 05:17:53 howdy 05:17:58 !simpleacro 05:18:01 XBFOJMHXD 05:24:57 !show simpleacro 05:24:57 haskell import System.Random; import Control.Monad; main = do {len <- pick [2..10]; putStrLn =<< (replicateM len $ pick ['A'..'Z'])} where pick a = randomRIO (0, length a - 1) >>= return . (a !!) 05:26:35 Xanthine Boards For Only Jocular Machinists Have Xenocided Dogs 05:28:00 Ok, it's been too long since I've read Station V3 05:28:05 There's an entire new arc 05:30:17 !haskell import System.Random; import Control.Monad; main = do {len <- pick [2..10]; putStrLn =<< (replicateM len $ pick =<< pick ["AEIOU","BCDFGHIJKLMNPQRSTVWXZ"])} where pick a = randomRIO (0, length a - 1) >>= return . (a !!) 05:30:20 OEAGWN 05:31:28 !haskell import System.Random; import Control.Monad; main = do {len <- pick [2..10]; putStrLn =<< (replicateM len $ pick =<< pick ["AEIOU","BCDFGHIJKLMNPQRSTVWXZ"])} where pick a = randomRIO (0, length a - 1) >>= return . (a !!) 05:31:30 UWOEIAU 05:34:35 Two arcs 05:58:38 -!- CakeProphet has quit (Ping timeout: 240 seconds). 06:02:51 -!- CakeProphet has joined. 06:02:59 no see... 06:03:05 vowels don't really contribute to easier acronyms. 06:03:08 or better suited ones 06:05:25 -!- augur has quit (Remote host closed the connection). 06:05:30 -!- augur has joined. 06:05:33 grmbl 06:08:58 -!- CakeProphet has quit (Ping timeout: 276 seconds). 06:09:50 -!- sftp_ has joined. 06:10:05 -!- myndzi has joined. 06:10:31 -!- CakeProphet has joined. 06:15:26 -!- oerjan has quit (Quit: Good night). 06:20:04 -!- cheater99 has quit (Remote host closed the connection). 06:30:17 -!- sftp has joined. 06:30:39 -!- sftp_ has quit (Ping timeout: 240 seconds). 06:39:40 -!- GreaseMonkey has quit (Quit: New quit message. Entering 2006 in style.). 06:53:56 sftp = simple fart transfer protocol 06:53:58 hurr hurr hurr 06:56:28 Yeah ... that's "humor" 07:00:29 you guys just don't know what humor is 07:01:12 here's an example of good humor: 07:01:33 you die. I kill you. the last sound you make is the release of your bowels. 07:01:34 sftp == secure file transfer protocol 07:30:45 -!- Sgeo_ has joined. 07:33:32 -!- Sgeo has quit (Ping timeout: 240 seconds). 07:43:59 -!- coppro has quit (Remote host closed the connection). 07:52:44 -!- relet has quit (Quit: Leaving.). 07:59:59 -!- clog has quit (ended). 08:00:00 -!- clog has joined. 08:06:32 -!- tombom has joined. 08:14:34 -!- SevenInchBread has joined. 08:14:35 -!- SevenInchBread has quit (Client Quit). 08:14:51 -!- SevenInchBread has joined. 08:16:23 -!- CakeProphet has quit (Ping timeout: 248 seconds). 08:18:12 -!- SevenInchBread has quit (Read error: Operation timed out). 08:21:26 -!- CakeProphet has joined. 08:48:23 -!- CakeProphet has quit (Ping timeout: 248 seconds). 08:55:22 -!- CakeProphet has joined. 08:58:00 -!- tombom has quit (Quit: Leaving). 09:02:48 -!- Phantom_Hoover has joined. 09:15:27 -!- sftp has quit (Ping timeout: 240 seconds). 09:15:28 -!- sftp_ has joined. 09:18:13 I think if you type "lemon" as a target into that battleships game it counts as a hit. 09:18:38 Of course, this is all moot, since Player 2 must always win. 09:26:49 -!- CakeProphet has quit (Ping timeout: 265 seconds). 09:28:25 -!- CakeProphet has joined. 09:28:55 Hm. If you type "lemon" into scanf("%d", &target), it'll leave the whole lemon in the input stream (and not modify target at all); I guess it depends on getche whether it'll remove those characters from the stream later or not. If not, all future scanf's in the loop will do nothing much, since the lemon will still be there. 09:31:12 In any case target won't get modified unless you put some digits in, so I don't see why it'd necessarily count as a hit. Not that I've looked at the madness very closely. 09:32:04 Well, I think that it would bomb the same square as you did previously. 09:33:03 Yes, but is that a hit? Anyway, if you start with lemon, target'll be 0. 09:33:24 So I assume that the reason for the lemon thing was that the lemon blocks up stdin, meaning that you repeatedly bomb the same square, and he didn't check if you had hit a square before 09:33:37 And I had hit a square before 09:33:46 s/$/./ 09:34:11 Oh, okay. 09:34:21 Wait, this takes the cake. 09:34:34 Yes, I guess you can easily keep getting hits if you just bomb the same place over and over again. 09:34:50 It doesn't partition the two boards *at all*, so player 1 can hit their own ships. 09:35:53 Wait, maybe not... 09:37:14 It is melting my brain... 09:37:27 I think they're separate; player one's positions are in [shipname]p[idx], player two's (which the hit-test is against) are [shipname]p[idx]two always? Though it seems to only ask and initialize player one's ships. 09:38:02 -!- CakeProphet has quit (Ping timeout: 240 seconds). 09:38:06 No, it does read for player 2's ships, though their initialisation is questionable. 09:38:41 Oh, okay, in checkShips. 09:38:48 It was there in the middle, I had missed it. 09:39:34 That is a very easy mistake to make. 09:40:36 -!- atroo has joined. 09:42:45 -!- CakeProphet has joined. 09:58:00 -!- sftp has joined. 09:58:30 -!- sftp_ has quit (Ping timeout: 276 seconds). 10:06:18 -!- cal153 has quit (Ping timeout: 276 seconds). 10:08:23 -!- Quadrescence has quit (Ping timeout: 245 seconds). 10:08:58 -!- Leonidas has quit (Quit: Reconnecting). 10:09:01 -!- Leonidas has joined. 10:09:47 -!- Quadrescence has joined. 10:09:54 -!- cal153 has joined. 10:11:35 -!- Leonidas_ has joined. 10:11:54 -!- Leonidas_ has quit (Client Quit). 10:13:13 -!- Leonidas has quit (Client Quit). 10:13:19 -!- Leonidas_ has joined. 10:15:10 -!- Leonidas_ has changed nick to Leonidas. 10:19:02 -!- GreaseMonkey has joined. 10:31:35 -!- Slereah has quit (Ping timeout: 265 seconds). 10:32:43 -!- Leonidas has quit (Quit: An ideal world is left as an exercise to the reader). 10:33:33 -!- Leonidas_ has joined. 10:33:48 -!- Leonidas_ has changed nick to Leonidas. 10:37:25 -!- Slereah has joined. 10:56:16 -!- augur has quit (Remote host closed the connection). 11:10:52 -!- sftp has quit (Remote host closed the connection). 11:30:22 -!- GreaseMonkey has quit (Quit: New quit message. Entering 2006 in style.). 11:32:27 Why does Flash MOCK me? 11:32:56 "Oh, look, here's a clip on the iPlayer. BUT I'M NOT GOING TO LET YOU PRESS THE PLAY BUTTON!" 11:34:55 I've had some Flash clicking problems lately; the weirdest thing is that clicking seems to work if I right-click the Flash player context menu open, keep the right button down, and then left-click whatever it was I actually wanted to click. 11:35:13 Or just plain old attack the left button with ferocity, that also sometimes helps. 11:36:13 Sorry, I think the left-right-workaround more accurately was "open context menu; keep right button pressed; left-click once outside the context menu to dismiss it; left-click the original target; release right mouse button". 11:36:21 It makes no sense, but sense is not what it makes. 11:38:24 I'll try that... 11:39:58 Thanks, fizzie. Thizzie. 11:40:37 What, it actually did something? I was half-certain it was something unique to my somehow messed-up Flash. 11:41:28 64-bit Ubuntu, Flash from APT. You? 11:42:04 Well, the same. But actually I think my wife's PPC OS X laptop's Flash has had the same thing, albeit not at constantly. 11:42:21 Also the 64-bit Ubuntu, Flash supposedly from APT here at work has no problems clicking anything. 11:42:29 http://media.glennbeck.com/app/getfile.php?filename=../../../../../../../../../../../../../../../../../../etc/passwd%00 11:42:50 This is karmic instead of the lucid I have at home, though. 11:43:18 Quadrescence, Tut. 11:45:01 fizzie, it is a mystery, then. 11:46:37 On the other hand, left-clicking, that's not such a critical feature; only those hackery sort of power users do that. It's understandable that it might not work completely right everywhere. 11:47:28 grep sarcasm 11:50:02 * Phantom_Hoover wishes he'd taken that BBC Micro his friend offered him. 11:50:21 I could break into his house while he's out of the country... 11:52:40 Yes, and set fire to it! To, uh.. I'unno. To make him pay for you not taking it earlier? 11:52:53 The first "it" referring to the house, of course. 11:53:14 Regrettably, I don't know where he lives. 11:54:00 Well, I know which bit of Edinburgh he lives in and that he lives above a Chinese restaurant, which narrows it down a bit. 11:54:07 You need to just start breaking into houses; you'll hit the right one eventually. 11:54:21 Most probably won't have a BBC Micro in them, that'll also help. 11:59:13 -!- Wamanuz has joined. 12:04:02 Quadrescence: Directory transversal? 12:04:23 http://media.glennbeck.com/app/getfile.php?filename=../../../../../../../../../../../../../../../../../../../var/www/glennbeck/htdocs/bitrix/php_interface/dbconn.php%00 12:05:19 That's such an age-old problem, is nice that people still keep doing it. 12:05:59 redjel1o 12:08:32 Nice to know that Glenn Beck can afford competent web staff. 12:11:36 * Phantom_Hoover notes that the BBC nearly made a programme called "syntax era". 12:11:47 That one's worthy of oerjan. 12:20:21 -!- derdon has joined. 12:22:43 That's programme in the sense of "TV", in case that isn't clear. 12:34:56 Quadrescence, except that one doesn't work 12:35:04 "Warning: fclose(): supplied argument is not a valid stream resource in /var/www/glennbeck/htdocs/app/getfile.php on line 75
" is all you get 12:36:17 AnMaster, worked for me. 12:36:22 hm 12:37:03 Phantom_Hoover, maybe someone found putfile.php and broke it? ;) 12:37:16 still works for me 12:37:32 Same. 12:37:47 Evidently Glenn Beck doesn't trust you Swedes. 12:37:49 how strange 12:38:07 oh that %00 didn't copy properly 12:38:48 who is that glenn beck btw? 12:39:02 Weird right-wing commentator. 12:39:15 He probably doesn't trust the Swedish in any case. 12:39:37 anyway, adding %00 at the end of course solved it 12:39:54 Phantom_Hoover, right wing, I doubt he trusts open source then either? 12:40:04 yet he uses mysql and php 12:40:07 correct 12:40:23 AnMaster, yeah, but they aren't by FOREIGNERS. 12:40:37 Phantom_Hoover, mysql used to be developed by a Swedish company iirc 12:40:48 before Sun bought them 12:40:54 (and then Oracle bought Sun) 12:42:44 AnMaster, yeah, so it's a triumphant example of American businesses conquering the Swedish ones. 12:42:47 I assume someone already checked if one of those database passwords work for ssh login as well. I'm not going to do that. Might be going a bit too far. 12:45:04 btw it seems to be RHEL4 12:45:30 AnMaster: no 12:45:35 everyone has said the same thing as you 12:45:40 "IT'S GOING TOO FAR" 12:45:47 "BLA BLA BLA" 12:46:21 Quadrescence, only if trying to hack ssh with it. I don't think just looking at various files readable by the web server is going too far :P 12:47:18 Yeah, now we know Glenn Beck's favourite colour of jello. 12:47:51 sshd_config seems to be either in some unusual location, not installed, or not readable to the web server. ssh_config however is interesting, unless it is the default RHEL4 one, I don't have any red hat distro handy so can't compare 12:48:17 hm /usr/sbin/sshd is definitely there 12:49:05 /etc/shadow was inaccessible, at which point I gave up. 12:49:28 Phantom_Hoover, well you can still get /etc/passwd 12:49:35 that gives you the accounts 12:49:46 Indeed. 12:50:32 what does the php function trim() do? 12:51:21 Removes whitespace from both ends of a string. 12:51:27 ah 12:51:48 a pity there seems to be no way to get a directory listing 12:51:48 Okay, so not necessarily just whitespace; you can give it the character set to remove. 12:51:57 well this is called with just a string it seems 12:52:24 AnMaster: you are getting me excited 12:52:27 so I guess he only likes jello on his development box. There is one good thing here at least: He isn't developing directly on the production system 12:52:32 i want to see something cool happen 12:52:33 Okay, then it's the default set, which is whitespacey. (Apparently -- looked it up -- spaces, tabs, newlines, carriage returns, nul bytes and vertical tabs.) 12:53:52 vertical tab, my favourite control character 13:24:05 -!- BeholdMyGlory has joined. 13:26:22 What does the vertical tab even do? 13:28:16 Not much. 13:30:39 Technically speaking it should have approximately the same effect on the cursor as enough line feeds to get to next vertical tab stop, cf. horizontal tab and an amount of spaces. 13:32:33 Or in other words: "A format effector which advances the active position to the same character position on the next pre-determined line." (Whereas newline has the same description sans the word "pre-determined".) 13:32:39 What a waste of a code point 13:32:57 In this xterm it seems to advance to next line without moving to the beginning of the line, while a linefeed would nowadays. 13:33:12 htkallas@pc112:~$ echo -e 'foo\nbar\vbaz' 13:33:12 foo 13:33:12 bar 13:33:12 baz 13:34:47 Many of the ASCII control codes are not so very useful nowadays. When did you last use the "negative acknowledge" control code, for example? 13:35:22 (There's a nice listing in http://www.cs.tut.fi/~jkorpela/chars/c0.html of them.) 13:38:10 Yes, half the ASCII is useless 13:39:46 Pretty much only used ones are NUL, HT, LF, CR and ESC. 13:44:16 There's DC3/DC1 for flow-control purposes, and they've co-opted some for shell job control, like end-of-text (ctrl-c) that is still sort-of related in-theory a-bit. Oh, and end-of-transmission to send an EOF in. 13:45:25 In fortuitous circumstances you can also sometimes use BEL to annoy people.- 13:48:26 ^L is used in sources sometimes. 13:48:32 I have no idea why. 13:49:05 It's also used in usenet for spoiler-protection. 13:49:39 I've seen even graphical newsreaders handle it properly on that context. 13:49:51 Not sure about Google's webterface. 13:50:19 In sources I guess the author just wants all functions to start on a separate page. 14:00:55 -!- Mathnerd314 has quit (Ping timeout: 248 seconds). 14:21:39 hm fun 14:22:06 the OpenGenera docs uses IP-TCP instead of the (nowdays?) more common TCP/IP in several places. However it does use TCP/IP in a few places as well.. 14:26:28 -!- Phantom_Hoover has quit (Ping timeout: 265 seconds). 14:37:16 I'm just reading http://en.wikipedia.org/wiki/Befunge#Befunge-93_instruction_list 14:37:49 is there an official way to escape double quotes in string mode? what if I want to push one or more double quotes to the stack? 14:45:14 If you want 'foo"""bar' on the stack, you could do something like: "foo#"1-::"bar" -- double quote character being '#'-1, after all. 14:45:51 If you're doing Funge-98, you could "foo"'""bar" instead. Some people have done ' in supposedly Befunge-93 interpreters as an extension, too. 15:09:17 stuff not following either standard is really annoying since it is impossible to know if any program expecting either of the versions will work 15:11:06 Since 93 doesn't really say what to do with undefined ops, it's reasonably safe to add new ones and still expect 93-compliant programs to work. 15:11:29 Can't safely use those in intended-to-be-portable code, of course, but that's another thing. 15:18:45 -!- cpressey has joined. 15:20:49 -!- derdon has quit (Read error: Connection reset by peer). 15:21:42 -!- derdon has joined. 15:27:19 -!- sshc has quit (Quit: leaving). 15:37:26 -!- Mathnerd314 has joined. 15:45:39 -!- MigoMipo has joined. 16:00:51 -!- oerjan has joined. 16:02:13 -!- Wamanuz has quit (Read error: Connection reset by peer). 16:04:03 -!- BeholdMyGlory has quit (Ping timeout: 264 seconds). 16:06:22 -!- relet has joined. 16:06:34 * Phantom_Hoover notes that the BBC nearly made a programme called "syntax era". 16:06:42 looks more like a spelling era to me. 16:07:34 party, oerjan! 16:07:45 fascist! 16:07:50 :ADSF 16:08:32 you and your contorted yoga positions 16:08:41 did i mention i think i solved my first open problem 16:08:47 ooo 16:09:12 *+n 16:09:14 it was sort of trivial so i sent the prof email so he can point out my error :D 16:09:20 ah. 16:10:12 "if a 2-directional AFA can go outside the string, to north and south, to a blank space, do we still get the regular languages" 16:10:54 my answer is "trivially not" 16:10:55 um does this mean if it cannot, you _do_ get regular ones? 16:11:02 yes 16:11:05 i proved it yesterday 16:11:12 i *think*. 16:11:29 um north and south? is this some weird 2-dimensional motion? 16:11:39 yes 16:11:51 the original question is about picture languages 16:12:04 "does it help to be able to go outside the pic" 16:13:04 that does sound weird that it should make a difference 16:13:25 can you go as far from the string as you want, or just one space? 16:13:26 just hover on top of the string and you can simulate a two-headed NFA 16:13:41 O_o 16:13:46 um, how? 16:14:05 guess what the cells to your bottomright and bottomleft have, check this, and move accordingly 16:14:30 if head on the right goes left, you go bottom-left etc 16:14:40 have to have some bookkeeping for even distances between heads 16:15:20 i still don't see this. how do you keep track of two heads simultaneously? 16:20:46 befunge is funny: "Integer division: Pop a and b, then push b/a, rounded down. If a is zero, ask the user what result they want." 16:21:11 -!- BeholdMyGlory has joined. 16:21:12 lol 16:25:54 -!- MigoMipo has quit (Ping timeout: 276 seconds). 16:29:00 what's the name of the game? 16:29:15 oklopol: Are you listening to ABBA again? Bad oklopol! 16:29:26 is that an abba song? :D 16:29:33 Sadly, yes 16:29:38 abba is the perfect band for formal language theorists tho 16:29:48 or theoreticians 16:29:49 And it's like the first thing that popped into my head when I read that 16:29:57 Because my parents are ABBA fans 16:29:59 * cpressey shudders 16:30:01 well for game theorists too. the winner takes it all. 16:30:06 :D 16:58:17 -!- MigoMipo has joined. 16:59:58 "most strings are complex in the sense that they cannot be significantly compressed: K(s) is not much smaller than | s | , the length of s in bits" -- wikipedia 17:00:17 K(s) being the Kolmogorov complexity function 17:00:43 anyone know: Is this true, and if so, where I can find a reference? 17:01:21 I'm certain it's true, I don't have a citation handy. 17:01:24 And if there is a precise notion of "most" 17:03:05 cpressey: it's a trivial application of the pigeonhole principle 17:03:31 you cannot compress most strings because there aren't enough smaller strings to compress them into 17:03:50 oerjan: OK -- I can easily see that for "there exists an uncompressible string" -- I guess it extends to a collection of string 17:03:54 *strings 17:04:23 well you know there are 2^n strings of length n, at _most_ half of them can be compressed at all 17:04:30 er 17:04:42 *length <= n 17:04:56 let me fix that 17:05:05 2^n-1 strings of length < n 17:05:27 and 2^(n-1)-1 strings of length < n-1 17:05:38 that gives about half, maximum, i think 17:06:03 if you compress by at least k bits, you can only do about 1/2^k of the strings 17:06:07 Everything you are saying makes sense. Actually, I'm sure I've seen it before, now, in another context. 17:08:47 So, define sumK(L) to be the sum of K(s) for every string s in the language L. Then sumK((0|1)^n) = O(2^n)? 17:09:25 Er, wait 17:10:15 Describing the language in English: L = {all strings of 0's and 1's of any length up to and including n} Then sumK(L) = O(2^n)? 17:12:01 I think so, but it would take me a while to draw it all out 17:18:24 -!- Phantom_Hoover has joined. 17:18:41 P******_H*****! 17:19:43 O(2^n * log n), perhaps 17:21:49 OK. Well, 17:21:59 * cpressey hits head against wall 17:22:21 (you need to actually store the strings, not just count them :D) 17:22:57 er wait duh 17:22:57 I was actually hoping for >= O(2^n), and that works. But now I think I see why it doesn't even matter. 17:23:05 O(2^n * n) 17:23:29 I know, abuse of O() there. I believe it's o() for lower bound? 17:23:36 -!- Gregor-P has joined. 17:23:44 no, that's Omega 17:24:26 oh right, i was confusing omega with theta 17:24:31 o() is like O() but stricter, ratio must approach 0 rather than being bounded by a constant 17:24:59 anyway, later 17:25:00 haha 17:25:02 small theta 17:25:05 :D 17:25:21 -!- oerjan has quit (Quit: Bye). 17:25:29 * oklopol is funny 17:25:41 -!- jcp has quit (Ping timeout: 265 seconds). 17:27:54 What algorithm are we talking about? 17:29:08 Phantom_Hoover: Compress all possible strings of length n or less, basically. 17:29:28 cpressey, can that even work? 17:29:46 Pigeonholing would make it impossible. 17:30:59 -!- jcp has joined. 17:31:36 Phantom_Hoover: Er, I mean "compress them all as far as possible, even if that means 0% compression for some of them, which it does". 17:32:21 It means -% compression if anything is compressed at all 17:32:59 Well, I was looking for a lower bound, so I was happy to ignore expansion 17:35:51 By expansion do you mean making a few strings much larger? 17:36:32 Phantom_Hoover: Well, somewhat larger, yes. You should never need to make a string much larger. 17:37:10 I assumed you meant expansion by "-% compression". 17:37:16 Yes. 17:37:33 But you would need some kind of definition of "useful" for that. 17:37:42 -!- Wamanuz has joined. 17:43:00 -!- Mathnerd314 has quit (Read error: Connection reset by peer). 17:43:01 -!- Mathnerd314_ has joined. 17:43:16 -!- Mathnerd314_ has changed nick to Mathnerd314. 17:43:38 Phantom_Hoover: This is all pretty pure theory -- no usefulness express or implied :) 17:44:01 cpressey, but then how do you decide which strings to expand or compress? 17:44:28 Phantom_Hoover: Try compressing them all. Any ones you can't compress, leave be. 17:44:44 cpressey, pigeonholing, though. 17:44:57 Phantom_Hoover: ? 17:45:04 You'll have to embiggen some of them. 17:45:31 Phantom_Hoover: By a constant amount, only, which could be ignored even if I wasn't looking for a lower bound. 17:45:48 I'm not sure what your concern is 17:45:52 -!- cheater99 has joined. 17:46:14 cpressey, are you trying for the biggest average compression? 17:48:10 No. I have a set of all possible strings of length n or less. I want to compress them all and stick them on a disk (say), and I want to know the order of how much space that'll take. According to oerjan, it's omega(2^n * n). I'm happy just knowing it's omega(2^n). 17:48:43 Well, I'm not happy, exactly, but yeah. 17:50:02 -!- cheater99 has quit (Ping timeout: 240 seconds). 17:53:13 It's kind of a rabbit hole, because "set of all possible strings of length <= n" is sort of a theoretical worst case. Hey, actually, if you knew the set contains all possible strings, you could compress the whole thing very well -- just write a program to generate them! 17:58:57 -!- Gregor-W has joined. 17:59:15 -!- Gregor-P has quit (Quit: Bye). 18:00:01 -!- Mathnerd314_ has joined. 18:01:01 -!- atroo has quit (Quit: Abandonando). 18:02:00 -!- Mathnerd314 has quit (Disconnected by services). 18:02:08 -!- Mathnerd314_ has changed nick to Mathnerd314. 18:04:14 -!- cheater99 has joined. 18:05:07 * Phantom_Hoover has a strange desire to write a processor emulator 18:05:45 I get those sometimes... 18:09:35 It was weirdly directed at the 6502... 18:09:57 http://www.devtopics.com/category/languages-obscure/ 18:10:03 Apparently Haskell is "obscure". 18:10:03 I don't think that's realistic, though, since I have no idea how a 6502 works. 18:10:17 cpressey, they deserve what's coming to them 18:11:16 I think by "obscure" he means "script kiddies haven't heard of them". 18:11:24 I guess so. 18:12:33 -!- cheater99 has quit (Ping timeout: 245 seconds). 18:13:07 6502 is not a particularly complex processor, so it's a reasonable project. 18:14:02 "The Cyclone programming language is a safe dialect of C." 18:14:10 How can that possibly work? 18:14:22 Er -- I used to know 18:14:30 Phantom_Hoover: How about instead of writing a processor emulator, you make an existing processor-emulator (JSMIPS) better? :P 18:14:53 Gregor-W, does that stand for JS? 18:15:01 s/JS/JavaScript/ 18:15:08 Yes, JS does stand for JS :P 18:15:21 It even stands for JavaScript 18:15:32 Phantom_Hoover: It works by adding semantics to C to allow for static and runtime memory safety. 18:15:49 Phantom_Hoover: the wikipedia page gives an overview. Pointer arith is restricted, importantly. 18:15:56 Most obviously, it adds multiple types of pointers 18:17:28 I'll bet it would be really difficult to write an interpreter with a garbage collector in Cyclone :P 18:17:50 -!- cheater99 has joined. 18:18:10 Gregor-W, I have JS trauma. 18:18:15 Cyclone appears to provide GC itself 18:18:53 cpressey: Ahhhhh well that makes sense then, I guess the real question should have been how it could be safe without GC, but I guess the answer is it has GC :P 18:19:10 Phantom_Hoover: But JS is lurrrrrrvely! 18:19:28 Hmh? It could be safe without GC 18:19:33 Gregor-W, I believe I mentioned the cause of the trauma yesterday. 18:19:54 Phantom_Hoover: JSMIPS probably doesn't work on IE5 :P 18:20:25 Gregor-W, I, being sane, used Safari or Firefox. 18:21:12 It was more being asked to write the same program about 5 times. And then test it thoroughly. 18:22:01 The point was to check that an integer was within certain bounds, and sometimes whether you were in jail. 18:22:05 cpressey: Yes, that'd require static checking of all allocations. 18:22:28 When I pointed out that if you were in jail you'd be unlikely to answer honestly, no-one listened. 18:22:52 pikhq: It makes no claims of being *statically* safe 18:23:21 cpressey: Yes; hence the GC. 18:23:25 :) 18:23:48 OK, I give up then 18:24:11 * Phantom_Hoover really needs to stop bitching about that 18:28:07 How does GC make it safe while lack of GC would make it not safe? 18:29:28 cpressey: I pass a pointer into a complex maze of functions, one of which frees it. Now I use that pointer. 18:29:48