00:00:05 which is exactly the [] and (++) analogues here 00:00:13 and you can also use like, mconcat 00:00:23 you can also just use functions directly though 00:05:15 sometimes it feels like the amount of rep i get for a stackoverflow answer is inversely correlated to the amount of work it was... 00:06:40 that doesn't surprise me 00:07:02 -!- Phantom_Hoover has joined. 00:08:10 it doesn't really surprise me either 00:08:47 an answer that's easy to make is also easy to understand 00:10:10 -!- R40UL has quit. 00:11:04 so... concat xs = foldr (.) [] (map (\x -> (\xs -> x ++ xs)) 00:11:14 this would be O(n)? 00:11:23 n being all list elements 00:11:47 well, that's the same as foldr (++) [] 00:11:52 (you mean foldr (.) id but yeah) 00:12:14 oh, yeah 00:12:17 okay 00:12:38 foldl would be n^2, wouldn't it? 00:12:42 myname: GHC probably fuses that into something simple 00:12:57 -!- Phantom_Hoover has quit (Ping timeout: 250 seconds). 00:13:10 okay 00:13:48 and yeah foldl is n^2 at least if it doesn't fuse, i'm not sure nowadays... 00:15:43 so, what is the advantage of using that function composition thingie instead of concat' = concat . reverse 00:16:15 you could just do foo:bar:[], couldn't you? 00:16:23 if you just want concat you can write foldr (++) [] 00:16:28 i assumed you were doing something more complicated than that 00:17:45 i am not quite sure, i have to take a look on how often i actually have to look into that list, but as far as i know it shouldn't happen that much 00:18:00 nice to know, though 00:18:11 @tell b_jonas but the way it is, it's not even turing complete, because there are only finitely many valid eodermdrone programs <-- you're jumping straight into our discussion of what TC means, i see 00:18:11 Consider it noted. 00:26:06 -!- callforjudgement has joined. 00:26:33 callfornickmolting 00:29:04 -!- ais523 has quit (Ping timeout: 244 seconds). 00:29:18 -!- callforjudgement has changed nick to ais523. 00:29:25 molting complete 00:40:35 hi 00:42:28 hopia 00:42:46 there appears to be a boily shortage 00:44:26 -!- PinealGlandOptic has quit (Quit: leaving). 00:56:09 -!- hjulle has quit (Ping timeout: 252 seconds). 01:00:50 -!- ProofTechnique has joined. 01:05:09 *sigh* hit the power button again 01:05:24 fortunately i restarted fast enough it didn't disconnect 01:05:52 i already changed it from "reboot" to hibernate, i think i shall change it to "do nothing" 01:07:21 after all, i never really use it anyway; whenever i _actually_ reboot it's to restart immediately. 01:10:01 -!- MDude has joined. 01:12:19 -!- Phantom_Hoover has joined. 01:27:38 -!- ais523 has quit (Ping timeout: 265 seconds). 01:38:05 -!- CADD has quit (Remote host closed the connection). 01:38:55 -!- merdach has quit (Quit: WeeChat 1.1.1). 01:40:04 -!- bb010g has quit (Quit: Connection closed for inactivity). 01:43:37 -!- tromp has quit (Ping timeout: 255 seconds). 01:51:44 -!- tromp has joined. 01:53:34 -!- GeekDude has joined. 02:03:46 -!- PinealGlandOptic has joined. 02:18:35 -!- MDude has changed nick to MDream. 02:23:49 -!- devdean1 has joined. 02:33:57 -!- ProofTechnique has quit (Ping timeout: 250 seconds). 02:36:08 -!- MDude has joined. 02:38:07 -!- MDream has quit (Ping timeout: 250 seconds). 02:39:51 @src 02:39:51 src . Display the implementation of a standard function 02:40:23 @src src 02:40:23 Source not found. Do you think like you type? 02:42:20 -!- arjanb has quit (Quit: zzz). 02:43:28 @src id 02:43:28 id x = x 02:43:28 -!- MDude has changed nick to MDream. 02:44:24 @src not 02:44:24 not True = False 02:44:24 not False = True 02:44:30 -!- ProofTechnique has joined. 02:47:59 @activity 3600 02:47:59 112*total 93*private 9*#haskell-blah 5*#esoteric 4*#haskell 1*#scannedinavian 02:52:28 -!- Phantom_Hoover has quit (Read error: Connection reset by peer). 02:56:01 ok girl genius, _that_ was unexpected. 02:58:13 so much for time travel being involved. 02:58:24 -!- kapil___ has joined. 02:58:47 (it'll still be involved _elsewhere_, presumably.) 03:01:21 @wn esoteric 03:01:22 *** "esoteric" wn "WordNet (r) 3.0 (2006)" 03:01:22 esoteric 03:01:22 adj 1: confined to and understandable by only an enlightened 03:01:22 inner circle; "a compilation of esoteric philosophical 03:01:22 theories" [ant: {exoteric}] 03:10:23 -!- bb010g has joined. 03:59:04 -!- PinealGlandOptic has quit (Quit: leaving). 04:27:11 -!- merdach has joined. 04:41:36 -!- _1_lyndero3 has joined. 04:41:44 <_1_lyndero3> hi 04:42:19 -!- _1_lyndero3 has quit (Remote host closed the connection). 04:49:55 -!- GeekDude has quit (Quit: ZNC - http://znc.in). 04:58:40 What's the worst that could happen if I upload this music to YouTube? 05:05:54 This one sounds like someone really playing a real piano... and making mistakes :/ 05:18:42 -!- Patashu has quit (Remote host closed the connection). 05:19:07 -!- Patashu has joined. 05:23:05 -!- bluckbot has joined. 05:25:46 http://runt-of-the-web.com/amazingly-unhelpful-fun-facts 05:27:50 http://horseysurprise.tumblr.com/ 05:34:18 Sgeo: that tumblr site not only has too small text, but it neutralizes attempts to zoom it. i suggest killing it with fire. 05:37:09 also, agreeing with me on this is mandatory hth 05:37:34 * oerjan may have waited a bit too long to eat 05:40:10 *attempts to neutralize attempts to zoom it 05:40:37 well in IE it succeeds. 05:41:47 You just made me open IE. I shall not forgive you. 05:42:27 Fails for me in IE too. Where fail is defined as "not as effective as perfect neutralization would be" 05:43:01 i define "neutralization" as "prevents getting it to an actually readable size" hth 05:43:51 I was able to increase the size, slower than I should have been able to, but it still increased each time 05:44:11 Besides the images are usually the important part 05:44:34 And it's the images where zoom isn't working well :/ 05:44:37 um ok i actually meant the image hth 05:45:08 stupid geeks taking blathering literally 05:45:12 CLicking the image then clicking the image works for me 05:45:35 i think you didn't read the part where i said agreeing was mandatory hth 05:46:09 's ok my blood sugar should return to normal soon. unless it overshoots again. 05:47:46 Diabetes, or just bad regular eating habits? 05:48:24 well i somehow waited for 8 hours before eating 05:49:24 diabetes runs in the family but i didn't have it when tested two years ago. 05:50:07 Some point I might need to get tested for it. 05:50:18 Turns out it runs in the family for me as well. 05:50:29 ("somehow" ~ "started trawling a webcomic archive for an old strip") 05:50:40 :) 05:50:59 never found it. maybe i'm imagining the strip, or have misremembered the character involved 05:52:01 What comic what strip? 05:52:17 Not that I'm especially likely to know personally 05:52:20 yet another fantasy gamer comic 05:52:29 -!- kapil___ has quit (Quit: Connection closed for inactivity). 05:52:47 (that's the name btw) 05:53:15 the current act reintroduces some rather old characters that haven't been seen in a while 05:53:18 *arc 05:54:26 i thought there was a strip where dewcup met those ranna worshippers in arachne's dungeon 05:54:43 except i'm not sure if they had shown up yet 05:54:59 so i think it may have been someone other than dewcup 05:56:15 * oerjan doesn't expect anyone else here to know, anyway. 05:56:26 Try /r/tipofmytongue ? 05:56:27 -!- CrazyM4n has joined. 05:56:40 Or any comic-specific forums 05:57:17 hm i was going to check which arc the worshippers showed up in 05:58:45 it's moved servers so the whole archive has been reorganized 06:09:06 "The word 'onomatopoeia' is also an onomatopoeia because it's derived from the sound produced when the word is spoken aloud." 06:10:45 ah i was confusing dewcup with jone. 06:31:02 -!- CrazyM4n has quit (Remote host closed the connection). 07:14:54 -!- kapil___ has joined. 07:47:41 `` echo 1 07:47:48 nm 07:48:08 !echo 1 07:48:10 1 07:52:14 int-e: well that was an unexpected girl genius development. 07:53:04 was it now, I haven't even read Wednesday's GG yet. 07:55:29 i suppose someone might have predicted it. 07:57:42 Well it surprised me. 07:58:00 King of all cats... I remembered that. 08:14:36 but I don't recall Krosp being explicitly connected to Dr. Vapnoople 08:19:51 hm 08:20:27 i tried looking up some of that earlier 08:21:23 ttp://girlgenius.wikia.com/wiki/Krosp_I is helpful, but the story of Krosp's creation didn't reveal the creator 08:22:05 i looked at wikia too and got frustrated because so many references were to the novels 08:24:24 well krosp is seen hiding when she first meets dr. dim 08:25:28 but he's been hiding on the airship ever since his creation, so all I read into that is that there was some convenient hiding place nearby 08:27:08 anyway it doesn't really matter; even if it has been mentioned before I probably wouldn't have remembered it 08:27:28 http://www.girlgeniusonline.com/comic.php?date=20040319 08:28:55 oh. thanks. 08:39:49 -!- CrazyM4n has joined. 08:47:42 -!- CrazyM4n has quit (Remote host closed the connection). 08:59:26 -!- CrazyM4n has joined. 09:13:26 -!- CrazyM4n has quit (Quit: sleep). 09:15:14 -!- cpressey has joined. 09:26:26 -!- vanila has joined. 09:26:34 hi 09:33:15 hi vanila 09:34:10 here's the OS i wrote 09:34:16 0000000 0583 8000 000b eb01 00f7 0000 b002 1bad 09:34:16 0000010 0003 0001 4ffb e451 000c 0000 0000 0000 09:34:16 0000020 0000 0000 0000 0000 0000 0000 09:34:35 http://i.imgur.com/VX4TjY0.png 09:44:34 heh :) 09:45:19 i assume that's a hexdump of the bootblock? 09:45:50 yeah and boot it with GRUB 09:46:20 itsj ust a multiboot header + loop that increments some address 09:46:38 -!- TieSoul_ has joined. 09:46:44 what I can't figure out how to do is boot it on a real computer :\ 09:46:55 i tried usb drive but it doesnt work 09:47:32 i don't know anything about multiboot 09:48:20 in fact, i don't think i've ever gone beyond booting from a floppy 09:49:02 -!- TieSoul has quit (Ping timeout: 245 seconds). 09:51:45 cpressey: we had a discussion here at one time about System F / second order logic, you can look at that as a complexity class if you want and it contains ackermann and even the goodstein sequence 09:52:29 (someone here wrote up an implementation of the latter in non-recursive rank-N haskell, which is basically equivalent) 09:53:31 -!- Phantom_Hoover has joined. 09:55:05 oerjan: you don't know how much it freaked me out to see you talking about webcomics and killing webpages with fire, in the logs 09:55:23 huh? 09:55:44 whew, maybe that wasn't you? 09:55:56 no, it was me, but still, huh? 09:56:15 \o/ 09:56:15 | 09:56:15 | 09:56:15 /| 09:56:15 >\ 09:56:20 (most webcomics i read i learned about in this channel) 09:56:21 i just booted it for real 09:56:34 myndzi: psst your script is running twice or something 09:56:50 \o/ \o/ \o/ \o/ \o/ 09:56:50 | | | | | 09:56:50 | | | | ¦ 09:56:50 /'\ |\ /< |\ ´¸¨ 09:56:50 |\ /´\ /'\ /| >\ 09:56:53 hahaha 09:57:01 it's been noticed before 09:57:12 they look like keys 09:57:18 that's weird 09:57:46 cpressey: most webcomics i've followed i learned about via this channel 09:58:21 cpressey: my huh is because i don't know why that freaked you out. 09:59:10 as someone who has recently become a lot more dependent on zooming webpages, it irritates me a lot when they make it hard. 10:00:48 -!- Korok has joined. 10:01:05 -!- Korok has left. 10:02:26 Oh, by the way, a fungot status update. Our Internet arrives on March 3, but I'll be out of the country from March 2 to 13, so I have a fungot ETA of maybe mid-March. 10:02:30 oerjan: never mind -- I think there's something wrong with me. 10:02:59 (Very suboptimal.) 10:03:06 fizzie: you don't happen to have another way of making HackEgo join a channel, do you? it's actually connected... 10:03:25 I have one but it's convoluted. 10:03:39 cpressey: i'd give you the standard lewis carroll quote but HackEgo isn't here... 10:04:08 -!- devdean1 has quit (Quit: Leaving.). 10:05:21 oerjan: Anyway, I have to just conclude that complexity theorists don't care about the upper reaches 10:05:44 I can almost hear them yawn when it gets bigger than NP 10:05:45 cpressey: that seems likely 10:06:14 nah that's not true, PSPACE and EXP get a fair workout don't they 10:06:41 That's true, I've seen them be interested in PSPACE at least 10:08:17 although you could maybe make a case for "only classes not known to be larger than NP" 10:08:45 Not that anyone here would necessarily know offhand, but: like Ackermann is sort of the poster-child for "not in PR", are there any obvious candidates for "not in "? 10:08:51 I mean, even guesses would be fine 10:09:01 I'd just be a little irked if there are no "natural" examples 10:09:13 Not that Ackermann is particularly natural 10:09:19 But compared to some things, it is 10:10:17 Oh wait 10:10:21 I forgot, I don't actually care. 10:10:31 fiendish 10:10:42 Nihilism is harder than it looks, isn't it 10:11:32 whatever 10:12:04 * oerjan whistles innocently 10:12:39 * oerjan whistles 4'33'' innocently 10:12:44 I just get the feeling that there's no point in me trying to understand these things, because I'm sure I never will. This grates against the fact that they fascinate me. 10:14:02 i think that when you look at very small or very large complexity classes things tend to get intertwined with logic questions 10:14:54 It does seem reasonable, once you get above EXP and friends, to stop treating it as complexity and start treating it as computability 10:15:26 what is the thing being investigated? 10:15:36 vanila: hard to say 10:15:51 Okay, laptop is up and keyboard is connected to phone. 10:16:02 Next, I need to something something something. 10:16:18 i'm not sure i know any problems between goodstein/hydra things and the halting problem/busy beaver stuff 10:16:35 What, there's no nc on Android shell. 10:16:42 vanila: algorithms that run a long, loooong, loooooooong time, but we still know that they eventually finish <-- very approximate way to describe it 10:17:07 fizzie: good man 10:17:08 that's a really interesting topic 10:17:13 I can push the SSH key from the laptop to the phone (which is the only thing Internetted here), but I'm not sure how to get it to somewhere else. 10:17:21 oerjan: at least I know about the hydra, but I'll have to refresh myself on goodstein 10:17:23 it can get a bit philosophical 10:17:37 cpressey: i think they're sort of on the same level 10:18:19 both are about things that can grow a lot in size but always shrink as ordinals 10:18:49 yeah as soon as you get to the point of needing transfinite induction to prove that it terminates... sheesh 10:19:13 ok, i can see why this is not a well-trodden area 10:20:42 I'm probably overthinking things, too 10:22:26 I don't get it. I pushed the files to Download/ but they're not visible there. 10:22:39 A cool thing about the dependent type theory as opposed to something like charity is you can write programs that take a very very long time to halt 10:22:44 Maybe the storage indexer thing doesn't refresh from just an adb push. 10:23:26 Or maybe the "Downloads" list and the Download/ folder aren't a 1:1 thing at all. 10:23:56 fiendish 10:27:14 -!- Koen_ has joined. 10:27:48 I think I might have got it 10:29:36 the ebola virus? 10:29:49 The server is being really really slow. 10:29:57 again :( 10:30:05 the slowver 10:30:35 but not so slow that HackEgo is pinging out... 10:30:56 -!- HackEgo has joined. 10:31:01 It is done. 10:31:05 whee! 10:31:07 And it was stupidly complicated. 10:31:09 `? mad 10:31:37 It took maybe 5 seconds to reply to simple shell commands, so I don't expect the umlbox stuff will run very fast. 10:32:13 maybe someone is DOSing the wiki. it could happen. 10:32:27 Maybe CloudAtCost. 10:32:57 I could have a look at network traffic, but I need some breakfast first. 10:32:59 "But I don't want to go among mad people," Alice remarked. "Oh, you can't help that," said the Cat: "we're all mad here. I'm mad. You're mad." "How do you know I'm mad?" said Alice. "You must be," said the Cat, "or you wouldn't have come here." 10:33:10 cpressey: ^ quote 10:34:43 http://catseye.tc/installation/Cheshire_Text <-- but you need to read the whole thing, top to bottom, for it to work 10:35:11 can't imagine why 10:35:21 oh 10:38:56 well that went rather more quickly than I expected... http://int-e.eu/~bf3/tmp/cheshire.png 10:43:23 (Hmm, couldn't the same effect be achieved by a CSS transition?) 10:44:26 grin grin grin 10:45:14 I thought: a brainfuck OS 10:45:25 the kernel is in assembly and has interrupts for each of <, >, +, -, ., ... 10:45:48 so you can compile a brainfuck program into syscalls.. but then someone could still use registers and things 10:46:59 -!- TieSoul_ has changed nick to TieSoul. 10:51:46 If you feel overwhelmed, go with minor-closed graph classification, which takes only cubic time. 10:52:02 vanila: I like the idea of one syscall per BF instruction for some reason 10:52:16 it has a certain terrible elegance 10:52:23 i like things with a certain terrible elegance 10:52:43 :) 11:02:40 speaking of which, I should write that recursive-{de,a}scent {parse,generato}r I've been meaning to 11:06:49 recursive scent 11:17:49 -!- bluckbot has quit (Remote host closed the connection). 11:18:42 -!- bluckbot has joined. 11:22:17 oerjan: I am going to steal that term if you don't mind 11:22:27 at least in this implementation 11:23:13 this smells of recognition 11:23:50 -!- hjulle has joined. 11:27:28 so many curses 11:29:04 -!- Patashu has quit (Ping timeout: 255 seconds). 11:31:11 done. can anyone recommend a pastebin? 11:32:07 because I just know you are all pastebin connoisseurs 11:32:40 gist it is! 11:34:29 https://gist.github.com/cpressey/dd3f63eda91b33e429fa 11:35:03 now you may all tell me that I should have done it with monads, dependent types, and CSS transitions 11:39:14 cpressey: are you going to ask for justifications of such claims? 11:39:23 if not I'd be happy to oblige. 11:39:44 cpressey: I sometimes use dpaste 11:44:06 int-e: no, I'll just say "oh, I know, I know" like Mrs. Fawlty on the phone 11:44:52 -!- ProofTechnique has quit (Ping timeout: 244 seconds). 11:49:17 definitely monads yeah 11:51:47 oh, I know, I know 11:54:38 int-e will have to take care of the CSS transitions and elliott the dependent types 11:58:57 -!- SopaXorzTaker has joined. 12:00:58 -!- oerjan has quit (Quit: leaving). 12:04:06 what's going on i just woke up 12:04:32 for the sake of fantasy i would like you all to believe that i have irc pings hooked up to an alarm 12:08:13 elliott: 12:08:59 or do you mean CTCP pings, hmm 12:09:35 every time i am talked to i have to hit the alarm off. please be considerate and leave me alone forever 12:11:40 elliott: I think you got the reverse psychology idea wrong. 12:12:18 You *can* go around explaining a new toy to children, then forbid them to use it. But you shouldn't be surprised if they end up playing with them anyway. 12:12:31 s/them/it/ 12:12:57 i feel like the utter certainty all of you would spend hours setting off my alarm were it real is why this channel sucks so much 12:13:55 cpressey: this is cute. there is work on this kind of thing in The Literature, i think 12:14:03 parser combinators that go both ways, etc. 12:16:02 hmm, "both ways" http://hackage.haskell.org/package/boomerang 12:17:15 right. there's like, an Actual Name for it and Actual Papers. maybe "reversible grammar" or something, I don't know. 12:17:27 you get things like, instead of fmap taking a function it takes an isomorphism 12:17:34 one function for each direction 12:17:42 cpressey: am I academising sufficiently here? 12:29:09 -!- SopaXorzTaker has quit (Ping timeout: 252 seconds). 12:32:47 for the sake of fantasy i would like you all to believe that i have irc pings hooked up to an alarm 12:32:58 I have done this in the past & suspect someone else does this 12:33:30 vanila: like a proper alarm or just making your computer make a lot of noise 12:33:35 ideally it should be like, clockwork 12:33:59 oh just the computer, but t woldnt be too hard with an adruino or something.. 12:35:03 elliott: yes, thank you. i realize it is nothing very special, but i think it's cute too 12:37:10 reversible parsing is very awkward 12:37:17 parsing is not usually a bijection 12:37:27 because of things like skipping whitespace, comments 12:37:48 iits better to specify a parse as something that if you print it out and parse that you get the same thing 12:38:52 on the other hand it's often kinda useful not to drop things like comments in an AST so you can do things like error reporting and code transformations without disturbing things like that (but it is awkward yeah) 12:43:44 maybe "a certain terrible elegance" that i referred to means "it suggests an algebra" because what is interesting me right now is, are there any operation-sets besides "parse" and "generate" that make any sense 12:44:11 i can only think of fairly contrived ones, and minor (relatively) variations on those two 12:44:51 "count terminals in grammar" is not exactly interesting 12:45:06 the operations in http://matt.might.net/articles/parsing-with-derivatives/, maybe? 12:45:23 (taking the derivative with respect to a token, deciding whether a grammar admits an empty string, etc.) 12:45:33 probably not doable with the imperative recursive-descent style though so n/m 12:45:40 *the empty 12:46:22 hm 12:46:27 well, this code makes it abundantly clear that the RDP could be a passive data structure instead of a set of functions 12:46:30 isnt empyness undecidable for CFG? 12:46:46 no, its decidable 12:46:56 so maybe it admits a notion of derivative too? 12:46:58 intersection of 2 being empty is, i thnk 12:47:12 although that might let you determine equality which is undecidable.. 12:47:33 I guess there's no derivative for CFGs then 12:47:52 vanila: that article is about derivative for CFGs 12:50:00 :O 12:50:02 wow 12:50:18 i assumed it was about regex 12:50:39 it's about using derivatives to parse arbitrary CFGs 12:54:50 oh okay 12:54:56 the trick is that the derivative is an infinite object 12:55:10 so that stops you from being able to use it to determine equality 12:59:53 i remember coming across derivative of regular languages a few years ago; you can basically extend it to a kind of linear algebra, which is neat. didn't realize you could extend it to CFL's 13:00:13 vanila: well, it's infinite if the original grammar is, I think 13:00:22 because of left recursion 13:00:27 well, no, not necessarily, sometimes it can be finite 13:10:43 "There's no backtracking in the algorithm." <-- for some reason that made me interrobang 13:11:06 this is actually quite cool 13:11:10 yeah! 13:16:59 i'm probably not understanding it entirely correctly, but it's like the memoization and fixed-point parts avert any possibility of backtracking, early on 13:17:21 have you looked at the regex version of this? 13:17:35 you can use derivatives of regexes to build a DFA 13:28:43 vanila: yes, in a book, probably about 8 years ago :/ 13:29:04 -!- Tritonio has quit (Ping timeout: 252 seconds). 13:29:05 the linear alg thing was what stuck in my mind 13:34:53 the no-backtracking property might mean it'd be good for parsing streams (e.g. data over a socket) too 13:56:30 at the end it almost sounds like they want to add some "hash-consing" to it too :) 14:19:31 -!- Lymia has quit (Ping timeout: 265 seconds). 14:22:39 -!- SopaXorzTaker has joined. 14:23:36 -!- SopaXorzTaker has quit (Max SendQ exceeded). 14:29:52 -!- cpressey has quit (Remote host closed the connection). 14:33:55 -!- cpressey has joined. 15:01:55 @tell ais523 wait, doesn't it have to be the other way around? You need a mapping (O(n) or otherwise) from TMs to programs in language X, for X to be TC 15:01:55 Consider it noted. 15:02:55 If you have a mapping from at least 1 universal TM to at least 1 program in language X, X is fancy-L-complete or whatever 15:04:27 I don't see a lot of "naturally occurring" "compiler mappings" like these that exceed O(n log n), but it might be nice to have some contrived examples 15:11:25 maybe some esolang where programs have to be arranged "just so" and a compiler from-TM-to-it has to take that into account when constructing the target program 15:12:04 you have to fit the commands into a tesselation or something, so compiling to it requires solving a NP hard puzzle 15:13:14 vanila: exactly, something like that 15:13:27 heh, there are two esolangs called "Numberwang" 15:16:28 -!- SopaXorzTaker has joined. 15:17:27 well, i can't find anything on esolangs.org that fits the bill offhand, but that thing's huge now :) 15:18:15 a lot of them might fit the bill, if we knew more about them :) 15:20:04 -!- ProofTechnique has joined. 15:20:25 who needs anything like that when you have masterpieces like https://esolangs.org/wiki/Pig 15:21:07 fizzie: is esolangs.org HSTS yet 15:21:53 Where are the languages based on qubits? 15:24:25 -!- ProofTechnique has quit (Ping timeout: 252 seconds). 15:27:58 NP-hard might still = P, who knows, so I'd prefer something EXPTIME-complete 15:28:45 I should try to remember that I don't really care before I actually try to devise something like this 15:29:52 FreeFull: there are some: https://esolangs.org/w/index.php?search=qubit&title=Special%3ASearch 15:30:22 -!- SopaXorzTaker has quit (Quit: Leaving). 15:30:41 -!- MDream has changed nick to MDude. 15:37:16 -!- SopaXorzTaker has joined. 15:37:31 -!- boily has joined. 15:38:24 cpressey, NP-hard is definitely larger than P 15:38:58 cf. http://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg 15:39:01 NP-hard includes everything that is outside P, doesn't it? 15:39:06 no. 15:39:14 Ok 15:39:47 An EXPBLARGL program consists of a description of a Turing machine, a number k, and a Befunge program. To run an EXPBLARGL program, first you determine if the given TM halts in k steps. If it does, you run the Befunge program. If it doesn't, you run 99 bottle of beer on the wall, or something. 15:40:15 and, uh, k must exqual the size of teh Befunge program 15:40:35 no, the compiler can always just pick easy TMs 15:40:49 maybe the Befunge program has to double as the TM description 15:41:10 and the only reason I chose Befunge is because I was going to choose brainfuck but then Phantom_Hoover walked in 15:41:31 Phantom_Hoover: I thought NP-hard meant >= NP-complete 15:41:51 yeah 15:42:07 so it includes problems which aren't in P or NP 15:42:23 um, is NP-complete not in NP? 15:42:32 NP-complete is in NP 15:42:51 so if x is NP-hard it might be NP-complete which might (WHO KNOWS) be in P 15:43:05 for a concrete example, the halting problem is NP-hard but not in NP 15:43:28 Phantom_Hoover: yes but "NP-hard but not in NP" is not the same as "NP-hard" 15:43:32 http://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg NP complete is a lemon 15:44:18 looks more like an american football 15:44:19 cpressey, oh, were you talking about individual problems rather than the classes as a whole? 15:44:54 Phantom_Hoover: yes, I'm trying to make a contrived language to which you can't compile a TM in O(n log n) because ais523 15:45:01 ah 15:46:27 I'm not sure that matters, given the diagram vanila linked to, but I don't really care 15:49:19 -!- GeekDude has joined. 15:50:52 -!- SopaXorzTaker has quit (Quit: Leaving). 15:51:10 -!- SopaXorzTaker has joined. 15:51:16 cpressey: unefunge 15:51:37 -!- SopaXorzTaker has quit (Remote host closed the connection). 15:51:38 unefunge or blank would be simpler 15:52:02 EXPBLARGL as defined is only P-complete b/c the length is effectively given in unary 15:52:07 lemme try again 15:53:28 and, sorry, I'm going to use brainfuck because it's convenient. besides, it will give Phantom_Hoover something to blog about 15:54:11 -!- SopaXorzTaker has joined. 15:54:13 an EXPLBARGL program is a brainfuck program except first you interpret it as a base-8 number and call than n and then you only run it if you determine it does *not* halt in n steps 15:55:02 ok, EXPLBLARGL was actually a typo there, but that's fine 15:55:09 cpressey: regarding the complexity of compiling stuff to Turing machines, how do you represeny Turing machines? If an n state Turing machine requires O(n log n) data then that should also be a lower bound for a compiler. 15:55:37 cpressey: How about some sort of incremental XOR? 15:58:15 A turing machine requires potentially unbounded memory, depending on what is to be compiled. 15:58:57 Though I don't know if that's what you're asking. 15:59:09 int-e: well, the "obvious" way to me to describe a TM has length O(nm) where n is # states and m is # symbols. but if ais523 is going to allow some tricky compression, I dunno 15:59:46 MDude: yeah, that's not a problem, I'm only considering compiling TMs to other languages that also have unbounded storage 16:01:15 sigh, EXPLBLARGL still fails 16:01:27 I think? 16:01:34 cpressey: Ah I was thinking about a fixed number of symbols. How do you avoid the log n factor? 16:02:12 wait a sec 16:02:15 isnt this impossible? 16:02:29 No. 16:02:30 what about that kthing where you write an interpreter for another lagnuage, then provide your code as data 16:03:06 the interpreter is a fixed number of characters and the data can probably be at worst a unary encoded number 16:03:15 -!- SopaXorzTaker has quit (Ping timeout: 246 seconds). 16:03:17 int-e: I don't see any need to avoid it myself. I think it's ais523 who's aiming for O(n). I'm just observing there aren't many cases where you need a compiler that is more than O(n log n) 16:03:24 the log n is for the symbol table 16:03:29 * cpressey waves hands a lot 16:03:45 ah, fresh air! 16:04:22 MDude, well? 16:04:46 Wait, what were you asking about the impossibility of? 16:04:51 alright 16:04:59 Compiling things to turing machines, or compiling turing machines to other things? 16:05:23 MDude: compiling TMs to other things and needing more than O(n log n) time to do it 16:05:28 vanila: Which shows that you need to be precise with the rules. Is providing extra data on the tape allowed? Of course you can prefix the interpreter by code that initialises the tape but then you /may/ run into issues with encoding the state numbers in O(1) symbols. 16:06:55 though it's easy to devise encodings for TMs where this works (for example you can encode references to the "next" state by a fixed string) 16:07:07 as a (bad) example, compiling a TM to a Perl program shouldn't require more than O(n) time, where n is the length of the TM description (and yes, I'm assuming things like, the TM description is given as a table, and it starts with a blank tape) 16:09:33 emit prelude; for each transition in table { emit a bit of Perl with if statements and goto statements }; emit postlude /* probably not even needed here */ 16:09:37 -!- TieSoul_ has joined. 16:10:07 prelude defines a global variable for the tape and whatnot 16:10:31 I'd emit a TM interpreter followed by the TM description 16:10:47 cheating? maybe, but where exactly do you draw the line? 16:10:50 maybe the program oculd be encrypted, so to compile to something eslseyou have to decrypt it 16:10:55 and that could require brute force 16:11:07 -!- TieSoul has quit (Ping timeout: 245 seconds). 16:11:18 -!- TieSoul_ has changed nick to TieSoul. 16:11:29 the interpreter for the program would have to do the same decryption work of course, so it wouldnt' be a efficient programming language 16:12:17 int-e: not cheating at all; in fact that's O(n) too. question is, is there any target language where you can't do it in O(n log n), even given tricks like that 16:12:42