< 1532649739 491033 :oerjan!oerjan@hagbart.nvg.ntnu.no JOIN :#esoteric < 1532650195 65395 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532650412 292977 :trout!~variable@freebsd/developer/variable QUIT :Ping timeout: 265 seconds < 1532651160 410650 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1532651278 815 :Sgeo!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 264 seconds < 1532651584 225169 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 260 seconds < 1532651675 254632 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1532651702 191990 :mertyildiran!b0e332f3@gateway/web/freenode/ip.176.227.50.243 QUIT :Quit: Page closed < 1532652254 394527 :trout!~variable@freebsd/developer/variable JOIN :#esoteric < 1532652402 221076 :variable!~variable@freebsd/developer/variable QUIT :Ping timeout: 256 seconds < 1532652994 518241 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :CMV: graph rewriting cannot be done without using variables and binding said variables to subgraphs. < 1532653226 801598 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :OH MAN < 1532653240 802467 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :imode: define graph rewriting and variables here < 1532653313 185983 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :. o O ( channel mini ...what?... ) < 1532653319 858606 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :change my view. < 1532653342 731278 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :. o O ( darn, fooled by PPCG chat ) < 1532653374 452727 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :alercah: graph rewriting, rewriting over graphs. lhs -> rhs rules, only both the lhs and rhs are graphs. lhs is a pattern (that may include variables on edges, nodes, etc.) that's to be found in the given graph, and rhs is the pattern that's supposed to replace it. < 1532653396 140550 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so "variable" here means a label? < 1532653426 299875 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :"variable" means a variable. naively, something you can store something in, namely a node label, an edge label, or an entire subgraph. < 1532653439 962597 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I know off the top of my head of two formulations of HR grammars, one that work in terms of an algebra of equations, like how a CFG works < 1532653447 373903 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the other works with labeled vertices < 1532653455 24385 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :HR grammars? < 1532653468 339600 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :to google! < 1532653469 200072 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :hyperedge replacement < 1532653473 441369 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ah. < 1532653481 151969 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :. o O ( highly recursive ) < 1532653487 186114 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :start with a hypergraph, with labeled verticces < 1532653504 777277 :rain1!~rain1@unaffiliated/rain1 PRIVMSG #esoteric :whats graph rewriting for? < 1532653543 331538 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :each rule is G -> H where G and H are hypergraphs < 1532653561 742692 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :alright... < 1532653565 863202 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :hm. < 1532653567 154022 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :they must have a certain number of distinguished vertices, the same in each < 1532653583 620000 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :do you have some example rules and transformations? you have my curiosity. < 1532653600 17395 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :if you have a label match between a hyperedge in your graph, and the distinguished vertices in G, then you replace the edge with H < 1532653620 853009 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you could do it without labels in theory, but labels get you a lot more power < 1532653637 59695 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :unlabeled is what I'm after in the long run. < 1532653640 216054 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :because otherwise you don't have much control over how matches work < 1532653661 901474 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :if you just want to eliminate labels, you could just invent unique gadgets to replace labels < 1532653676 678973 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah, just unique local "shapes". < 1532653694 931326 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :imode: do you know the series-parallel graphs? < 1532653697 720899 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the problem is I can't wrap my head around how you'd specify certain arrangements of nodes and edges. < 1532653704 930513 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :in circuits? < 1532653707 440884 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :yeah < 1532653711 431794 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah. < 1532653734 957178 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the recursive procedure to build them up can be expressed as an HR grammar < 1532653743 720206 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :...interesting. < 1532653776 875352 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so let's say I have, for example, a loop that I want to extend. let's say I have a cycle of length 5, with nodes A, B, C, D, E, and F arranged linearly, with F connected to A. < 1532653802 435479 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I want to match any loop of 5 nodes, and then add a node after the last node. what would the rule look like for that. < 1532653811 548546 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :HR doesn't do that < 1532653814 348433 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :it only replaces edges < 1532653822 193050 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :okay, so you can't add or remove vertices. < 1532653825 51932 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you can < 1532653832 665744 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you can replace an edge with a graph < 1532653839 791678 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :wat < 1532653850 472263 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :1 sec, let me make sure I get this right < 1532653857 28664 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :sure, thanks for even bothering. < 1532653872 759273 :rain1!~rain1@unaffiliated/rain1 PRIVMSG #esoteric :what ab out regex < 1532653882 284497 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :imode: this was my masters thesis :) < 1532653887 417685 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :o shit. < 1532653892 823095 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(hence the OH MAN) < 1532653894 273173 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :came to the right person then. :P < 1532653910 6541 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :imode: so do you know the definition of series-parallel graphs by reduction? < 1532653917 887450 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :uh, shoot. < 1532653930 958145 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :also the thing that sparked my interest was https://www.slideshare.net/slidarko/computing-with-directed-labeled-graphs-3879998 < 1532654009 809112 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :a graph is series-parallel if it can be reduced to P_2 by removing duplicate edges and by contracting a vertex of degree 2 (other than the endpoints) < 1532654071 375220 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :contracting a vertex of degree 2. in or out degree. < 1532654077 653946 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :or are we talking about undirected, sorry. < 1532654093 945959 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :undirected < 1532654104 819369 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :oh wait my bad, I got this construction of HR slightly wrong T_T < 1532654105 194184 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :gotcha. okay. < 1532654110 286403 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(I worked with the algebraic one) < 1532654112 554030 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :lmao, it's cool. < 1532654124 105878 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I take it you're somewhere around computer engineering? < 1532654136 275343 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532654137 723616 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the thesis was in graph structure theory < 1532654144 208294 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I'm a SWE at Google atm < 1532654149 983076 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :damn. sweet. < 1532654215 593886 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the labeling is on edges, not vertices < 1532654223 160605 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and it denotes the nonterminals < 1532654227 429009 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :alright. < 1532654239 990630 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I don't think the rules could possibly apply to all hypergraphs then, could it? < 1532654245 174511 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so e.g. for series-parallel, we have one nonterminal S < 1532654300 727408 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and we have rules v-S-w -> v-S-x-S-w, and v-S-W -> v=SS=w < 1532654307 233140 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :kind of silly notation < 1532654315 502426 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :but the first one is meant to be series construction and the second one is parallel < 1532654328 854209 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :or in other words, subdivision and duplication < 1532654346 29052 :trout!~variable@freebsd/developer/variable QUIT :Ping timeout: 260 seconds < 1532654361 343737 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and then you have one rule v-S-w -> v-w < 1532654366 393000 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :which just eliminates the nonterminal < 1532654368 98443 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that's pretty interesting notation, I can see the forking and merging. < 1532654374 512932 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :yeah this is just invented right now for IRC < 1532654378 43838 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I would not recommend it in general :) < 1532654409 758253 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(hypergraphs are often depicted with, say, cicles for edges and boxes for vertices, as otherwise they get pretty ambiguous pretty fast) < 1532654430 407047 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so the series-parallel graphs are the ones you get starting from one S-edge and then replacing edges < 1532654435 870519 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :lmao, I figured. but that's interesting. so you can derive any "reasonable" circuit from those two rules. < 1532654440 871088 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :yep < 1532654451 821904 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the result is well-known, it just happens to be a nice simple example of an HR grammar < 1532654464 985734 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :but that does use variables. < 1532654468 995199 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :to bind to labels. < 1532654477 407821 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :it uses nonterminal labels < 1532654483 882517 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :but in a similar way to how a CFG does < 1532654495 375507 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :e.g. S -> xSw < 1532654510 466165 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ah. < 1532654543 457523 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you can use labels to restrict the bindings, yeah < 1532654576 574977 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so I guess I'd ask.. how would I use hyperedge rewriting to do general graph manipulations like I detailed above? < 1532654581 335190 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that's kind of what I'm after. < 1532654596 827482 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :HR can't do that I think < 1532654617 487235 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ah. that's still interesting though, I didn't know there was a process for deriving those kinds of graphs. < 1532654630 900040 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :it's actually the start of a rabbithole of deep results < 1532654646 271492 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I can understand why you don't want labeled verts, because in those graphs, all you _really_ care about are the edges. < 1532654703 650594 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :yeah < 1532654710 820448 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :nothing wrong with using labels to carry information, as well < 1532654716 641133 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :tru. < 1532654747 162681 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the HR grammars are nice because they naturally correspond to the CFGs over strings < 1532654757 310871 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :there are other kinds, though, like vertex replacement < 1532654778 546699 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :similar idea, but they use vertices as the replacement point, rather than edges < 1532654782 939869 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :what corresponds to unrestricted grammars? < 1532654804 970212 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I'm not sure off the top of my head < 1532654929 604928 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :might be worth thinking about it in terms of the algebraic formulations < 1532654935 636425 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the other way of expressing HR grammars < 1532654944 774565 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and that was the one I was thinking of initially < 1532654951 948492 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :hrmmmmm. < 1532654983 244397 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :but I mixed the two up < 1532655002 696892 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so in this system, you work over graphs where each graph has some labeled vertices, no two identical < 1532655006 405036 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(called sources) < 1532655061 937569 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you can freely rename sources, or make a source into a non-source < 1532655090 121152 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(technically renaming needs to preserve uniqueness so it's best expressed as swapping to keep things mathematically simple, but that's not necessarily relevant) < 1532655114 298575 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and then you can do a parallel composition, where you glue two graphs together at matching sources < 1532655131 384413 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :huuuuuuuh. now _that's_ interesting. I can see how they're equivalent. < 1532655167 141573 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :this can be expressed as an algebra < 1532655173 975867 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(that is, a bunch of things and some operations on them) < 1532655184 917410 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and then you can view a grammar as a system of equations < 1532655294 37136 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :e.g. for series-parallel, S = st | S // S [parallel construction] | rename[t->p](S) // rename[s->p](S) [series construction] < 1532655306 186108 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :st is a constant single edge with ends s and t < 1532655326 829901 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and then S // S is parallel since it joins two graphs at s and t < 1532655341 880261 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and the series construction is obtained by taking two graphs, renaming opposite ends of them to p, then merging < 1532655349 995343 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so p is fused but s and t remain as the endpoints < 1532655360 808652 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(oh I forgot you have to add a forget[p] operation) < 1532655365 193955 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(heh) < 1532655426 772955 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the graphs generated by this grammar are just the minimal solution to the system of equations < 1532655465 906145 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :wild. < 1532655476 868387 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :inherently, though, it can't do the sort of structural replacement you're looking for because it is focused on having a sort of exposed surface to glue graphs together, if you will < 1532655510 895936 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you could use it to extend a cycle, but not sensitively to the size < 1532655525 386276 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah I can see that. but from what I'm seeing, the gluing operation can be used to construct the desired graph. < 1532655532 268440 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :just with a specific sequence of operations. < 1532655548 671366 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :correct me if I'm wrong on that. < 1532655557 567220 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :yep < 1532655588 396824 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :but it turns out you cannot create a grammar in this system that will have unbounded cycle size < 1532655594 174691 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(assuming you are restricting to finite graphs) < 1532655622 531035 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :the fundamental limitation is on the fact that you can only "keep track" of finitely many vertices < 1532655647 282472 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so eventually you'd lose track of how big the cycle is and just keep expanding it indefinitely < 1532655657 80981 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :err wait < 1532655661 429970 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :not all cycles < 1532655667 757393 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :bleh, ignore that < 1532655671 217174 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I was thinking slightly wrongly < 1532655677 428426 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :'s all good. I think wrongly all the time. < 1532655713 311496 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you can of course do that because the series-parallel graphs do that :P < 1532655722 670880 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you can't have unbounded cliques though < 1532655737 494358 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :because once you forget a vertex, its relationships are finalized < 1532655804 223985 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :and this kind of model can't take edges away < 1532655822 469796 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :so once you have a 5-cycle, you can't turn it into a 6-cycle < 1532655886 456180 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ah. < 1532655930 774130 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :CFGs basically work on the same underlying technology < 1532655937 535575 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah, just over strings and not graphs.. < 1532655941 180381 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :yeah < 1532655949 295593 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :and they have the same limitation of finite-ness... < 1532655973 935493 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I guess the unrestricted grammar version would probably just be allowing arbitrary equations on the left-hand side as well < 1532655991 505895 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah. I think that'd solve the vertex amnesia. < 1532656014 287648 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :and actually allow you to construct arbitrarily large cycles. < 1532656057 41389 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :it might < 1532656063 850358 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :you also can do this with different underlying algebras < 1532656071 242436 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :since HR is far from the only reasonable algebra on graphs < 1532656115 746838 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(there's some tricksy technology that's used to define what it means to be an equational set i.e. generated set here, but I think the general idea is sound) < 1532656115 872360 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :given. all sorts of graph grammars and equivalent algebras to explore. :P < 1532656162 705168 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :I'd probably point you at Courcelle if you want to read more :) < 1532656171 95952 :trout!~variable@freebsd/developer/variable JOIN :#esoteric < 1532656175 180266 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :his papers cover a lot of relevant stuff < 1532656206 572909 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :say no more fam, I've got it logged down to research. < 1532656289 360518 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :there's also some cool relation to the regular languages here: you can generalize the idea of a regular language in a couple of different ways (e.g. myhill-nerode construction, DFAs) < 1532656300 902 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :(and a homomorphism-based one) < 1532656337 62802 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :they all work out to be the same thing < 1532656346 217936 :variable!~variable@freebsd/developer/variable QUIT :Ping timeout: 256 seconds < 1532656349 474618 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :but the relationship between recognizable sets (this generalization) and equational sets is not subset like with strings < 1532656370 719939 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :but you do get the filtering theorem, that the intersection of equational and recognizable is equational < 1532656500 695008 :S_Gautam!uid286066@gateway/web/irccloud.com/x-svfnjqzydtlrivds QUIT :Quit: Connection closed for inactivity < 1532656836 571443 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :@metar ENVA < 1532656838 491312 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :ENVA 270150Z 10010KT CAVOK 21/13 Q1020 RMK WIND 670FT 09006KT < 1532656936 738083 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :upcoming heatwave < 1532656998 262051 :alercah!~alercah@unaffiliated/alercah PRIVMSG #esoteric :imode: did I change your view :P < 1532657259 693895 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ehh, not realy. to actually implement your concepts, you still need binding. :P < 1532657275 7936 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :and it doesn't generalize to all graphs (I'm interested in working over semantic nets). < 1532657283 945315 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :but by god what you covered was interesting as hell. < 1532657769 632916 :MDude!~MDude@c-73-187-225-46.hsd1.pa.comcast.net QUIT :Ping timeout: 268 seconds < 1532658170 18 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532658358 298665 :trout!~variable@freebsd/developer/variable QUIT :Ping timeout: 265 seconds < 1532660449 226311 :trout!~variable@freebsd/developer/variable JOIN :#esoteric < 1532660646 30483 :variable!~variable@freebsd/developer/variable QUIT :Ping timeout: 260 seconds < 1532662428 193429 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532662610 710532 :trout!~variable@freebsd/developer/variable QUIT :Ping timeout: 256 seconds < 1532662970 489385 :variable!~variable@freebsd/developer/variable QUIT :Quit: /dev/null is full > 1532662972 560716 PRIVMSG #esoteric :14[[07ZZT-Flip14]]4 10 02https://esolangs.org/w/index.php?diff=57061&oldid=56952 5* 03Zzo38 5* (+258) 10 < 1532664737 785479 :sprocklem!~sprocklem@unaffiliated/sprocklem QUIT :Quit: sprocklem < 1532664758 89793 :sprocklem!~sprocklem@unaffiliated/sprocklem JOIN :#esoteric < 1532664809 45851 :sprocklem!~sprocklem@unaffiliated/sprocklem QUIT :Client Quit < 1532665012 660474 :sprocklem!~sprocklem@unaffiliated/sprocklem JOIN :#esoteric < 1532666720 94248 :MDude!~MDude@c-73-187-225-46.hsd1.pa.comcast.net JOIN :#esoteric < 1532669075 398167 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532670516 483045 :oerjan!oerjan@hagbart.nvg.ntnu.no QUIT :Quit: Nite < 1532671613 44270 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1532672768 571044 :sftp!~sftp@unaffiliated/sftp QUIT :Ping timeout: 244 seconds < 1532672961 638878 :XorSwap!~XorSwap@wnpgmb016qw-ppp-103-253.dynamic.bellmts.net JOIN :#esoteric < 1532673518 657022 :moei!~moei@softbank221078042071.bbtec.net QUIT :Quit: Leaving... < 1532673618 316555 :moei!~moei@softbank221078042071.bbtec.net JOIN :#esoteric < 1532673641 89240 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532673918 2277 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 260 seconds < 1532673948 15662 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532674062 473752 :variable!~variable@freebsd/developer/variable QUIT :Client Quit < 1532676107 260898 :SopaXorzTaker!~SopaXorzT@unaffiliated/sopaxorztaker JOIN :#esoteric < 1532677034 286620 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 JOIN :#esoteric < 1532677624 229315 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 260 seconds < 1532679357 100508 :S_Gautam!uid286066@gateway/web/irccloud.com/x-pavkxobmfolgdats JOIN :#esoteric < 1532679491 802485 :XorSwap!~XorSwap@wnpgmb016qw-ppp-103-253.dynamic.bellmts.net QUIT :Quit: the creeping crawling chaos will return. < 1532680001 346132 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532680284 227179 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 260 seconds < 1532685703 239280 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532685989 229374 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 260 seconds < 1532686093 748606 :SopaXorzTaker!~SopaXorzT@unaffiliated/sopaxorztaker QUIT :Remote host closed the connection < 1532688757 999063 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532689987 190092 :fungot!~fungot@momus.zem.fi QUIT :Ping timeout: 245 seconds < 1532690005 3119 :fungot!~fungot@momus.zem.fi JOIN :#esoteric < 1532690659 562872 :trout!~variable@freebsd/developer/variable JOIN :#esoteric < 1532690867 310731 :variable!~variable@freebsd/developer/variable QUIT :Ping timeout: 265 seconds < 1532692096 248360 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532692394 234725 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 260 seconds < 1532692549 568811 :variable!~variable@freebsd/developer/variable JOIN :#esoteric < 1532692740 377373 :trout!~variable@freebsd/developer/variable QUIT :Ping timeout: 245 seconds < 1532693628 717736 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1532693660 167866 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :trying to prove Stun Step TC has been very interesting < 1532693702 645083 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the issue is that we don't have any TCness proofs for reversible counter machines yet, and it's fairly difficult to emulate anything using a reversible counter machine other than other reversible counter machines < 1532693717 916872 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I've been working on a high-level (as esolangs go) language to bridge the gap < 1532693728 964470 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but it's probably going to need an IDE to be effectively able to program in < 1532693732 668671 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :hi ais523 < 1532693741 547784 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :hi < 1532693745 370697 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I have a theory question, not specifically for you, but for anyone here < 1532693810 523232 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :it's well-known that a finite state machine with two-stacks using some finite alphabet in the stacks, with UB on stack underflow, is Turing-complete, and you can simulate a one-tape Turing-machine on that, right? < 1532693816 413633 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :but I want a variant of this < 1532693901 693422 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes, the well-known variant is TC assuming sufficiently powerful control flow < 1532693927 796796 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oh, you also need the alphabet to contain at least one character < 1532693936 254627 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :err, at least two, if underflow is UB < 1532693948 889601 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(you use one as an EOF character and the other as a counter) < 1532693961 940798 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :what's your variant? < 1532693978 928576 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :The control is that the program has any finite number of states, and each state that pops has different followup states for each possible letter it can pop. < 1532693998 500364 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :The alphabets are large enough, you could say the program tells how large, but finite. < 1532694017 275337 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :The separate alphabets for both stacks are large enough but finite that is. < 1532694074 388339 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that's TC so far (e.g. you can implement StackFlow in it) < 1532694097 234522 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I know it's TC. What I'm saying is that it's also well-known to be TC. < 1532694104 451634 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes < 1532694111 900784 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :For my variant, what I need to be well-known is that it can simulate a Turing-machine with an oracle, where the program can interactively query the oracle for a string from an alphabet, and get a yes or no answer, and the program can call the oracle any number of times. < 1532694143 108123 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you want a stack machine with an oracle? < 1532694150 32481 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :And the machine I want to use for this is the two-stack machine, except it has a special state when it queries the oracle, with two followup states, and importantly, the entire first stack is the input to the oracle. < 1532694157 827274 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :ooh! I see < 1532694198 482919 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :So what I want well-known is that the machine can temporarily save all its state to its second stack, not using the first stack or the control state, and continue, and call the oracle with arbitrary input strings from the alphabet this way. < 1532694204 443433 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I'm not sure if it's well-known, but it's true < 1532694232 485362 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :The oracle input may need to be in a specific format, and can't have extra leading or trailing symbols or anything. < 1532694251 827767 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes, that's not a problem < 1532694310 469384 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I could relax the requirement about the control state, but using only one stack temporarily and a specific format on the first stack is mandatory for my proof. < 1532694329 885591 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the way to think about it is that if you have one stack (as opposed to a queue or a tape), the thing restricting you from TCness is that you have nowhere to store the top elements of your stack while you read the bottom ones < 1532694341 909487 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :And I also want this to run this with a reasonable speed, with at most polynomial slowdown in the number of steps. < 1532694346 689411 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so you have to throw them away (a PDA) or else store them elsewhere, and a second stack is sufficient to store them elsewhere < 1532694372 355439 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but you can use the second stack for other things while you don't need it as a temporary < 1532694408 300383 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :if you want to switch into "oracle mode", you do shuffling around to effectively put a sequence of imperative commands onto the main stack (each of these corresponds to a state that runs the command in question) < 1532694426 890863 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :It's like the problem with those string replacement languages: you have to move the oracle input from somewhere on the second stack to the first stack, and only that input, with some letter swaps, which requires a lot of states but who cares. < 1532694430 371108 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :"push symbol X on oracle stack", "pop oracle stack", "run oracle", "go to state Y" < 1532694458 3176 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :then you switch to a state that simply repeatedly pops from the main stack and runs the appropriate command < 1532694458 821269 :trout!~variable@freebsd/developer/variable JOIN :#esoteric < 1532694467 425871 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :Yeah. < 1532694488 92041 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(if the oracle is outputting in state form, you need two states to continue running the program after it returns, one for true, one for false, so that you use the state as a temporary to remember the oracle's answer) < 1532694508 17656 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this should be an O(n) slowdown where n is the size of the stack, so if the program was polynomial it'll stay polynomial < 1532694537 246377 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :interestingly, I have something like this as a primitive that I put in higher-level stack-based languages < 1532694586 991091 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :How I'm trying to use this is that the oracle is going to be a random-access disk storing an infinity of bits, and you give the address to read or write in (say) binary to the oracle, plus tell it whether to write zero, write one, or read. < 1532694604 411577 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :it's the opposite of "infra" from Joy, so I call it "ultra"; what it does is converts the entire stack into a single function, which when executed pushes the data in question back onto the stack < 1532694608 351216 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :Also, for reasons, the disk requires you to write a bit before you read it, otherwise it's UB. < 1532694645 365978 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :And this way a stack machine with that disk as oracle can "efficiently" simulate a RAM machine or a heap cons allocation machine, where the slowdown is a polylog factor of the runtime. < 1532694651 631555 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :if you're trying to implement it in a language that doesn't have it, you normally need to alter commands to ones that record the stack height, but apart from that it isn't terrible < 1532694671 789895 :variable!~variable@freebsd/developer/variable QUIT :Ping timeout: 255 seconds < 1532694709 2122 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :hmm, looks like I have an implementation lying around: (~aa(n:^)~*(*)*^)n:^ < 1532694721 748402 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(this is Underload + a primitive n for determining whether the stack is empty) < 1532694744 16470 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you do need to know where the end of the main stack is but in this construction, you can just use a separate symbol for it < 1532694776 46183 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :of course, the stack model you're using doesn't allow for arbitrarily complex elements < 1532694793 221833 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :although, hmm, I wonder if you could use something with paired ( and ) characters to delimit the elements < 1532694829 726151 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :no, I definitely need a finite alphabet < 1532694833 48726 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that'd work better in a three-stack system than a two-stack system, though (one for holding the program, one for holding the data, one for parsing the data) < 1532694841 167386 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :for the arbitrarily complex data, I store it in the disk oracle < 1532694856 273070 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :yes, but I can't afford three stacks. I need two stacks for this proof. < 1532694865 53742 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :wob_jonas: what you've got me thinking about is an Underload variant that runs on a finite-alphabet stack machine without a separate encoding layer < 1532694879 598090 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :it's easily doable in three < 1532694881 604522 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :two might be possible though < 1532694882 406195 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I could get a bit more relaxed with states, like, I don't insist on only one oracle state, but two stacks is important. < 1532694894 725406 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :via using the state machine to store data < 1532694996 3480 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :This is for the proof of how powerful Consumer Society is, although for practical programs you don't need all this complexity, you can get away with a simpler construction that lets you access a huge but finite amount of data. < 1532695031 69586 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :ugh, you do need three, so this approach won't work < 1532695057 826682 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :why do I need three? < 1532695063 411058 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :no, not your approach < 1532695066 304586 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :mine for solving your problem < 1532695078 795819 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :oh, the "underload with finite-alphabet stack" < 1532695089 441361 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I don't even understand what that would supposed to be look like < 1532695111 583615 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :['(',':','a','S','S',')',':','a','S','S'] < 1532695119 446687 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :i.e. the parentheses are elements in the alphabet < 1532695142 457730 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :what's with 'S','S' < 1532695149 601974 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :^ul (:aSS):aSS < 1532695149 618497 :fungot!~fungot@momus.zem.fi PRIVMSG #esoteric :(:aSS):aSS < 1532695156 95157 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :oh < 1532695157 932744 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I was just picking a well-known Underload program < 1532695171 24615 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :a quine < 1532695174 63195 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes < 1532695216 326441 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so the problem with stack machines is that they're bad at copying data < 1532695224 151218 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :of arbitrary size < 1532695242 725222 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :yes, or rearranging data < 1532695252 74551 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :but yes, copying is bad too < 1532695270 801271 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :even without supporting nested parentheses, Underload's ':' seems difficult (impossible?) to implement without the help of a third stack or a separate encoding layer < 1532695294 864525 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :like, let's pose this as a problem: suppose you have a stack of 'a' and 'b', and an EOF character (say '$') < 1532695320 279717 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :suppose you allow any finite number of additional characters, and you have a second stack that starts empty < 1532695329 863946 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :can you duplicate the contents of the stack in polynomial time? < 1532695374 763751 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I think so. it would be quadratic < 1532695389 610791 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :first you change each a to ac and each b to bd < 1532695396 566660 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :in one pass < 1532695404 303852 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :and then you bubble-sort < 1532695409 23608 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :then you do a bubble sort to bubble up the c and d < 1532695410 164312 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :yes < 1532695412 426091 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :right < 1532695425 51347 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :should be quadratic even on two stacks < 1532695434 274579 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :you just need a larger alphabet and enough states < 1532695435 672456 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this is possibly the first serious use of bubble sort I've seen :-D < 1532695457 475313 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :actually I think this gives a general method for implementing two stacks with three < 1532695463 827725 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :err, implementing three stacks with two < 1532695464 727460 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :you need to encode in the state whether you need another pass of the sort < 1532695480 212249 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :or in fact any number of stacks with two < 1532695498 855542 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :use one stack that simply contains an arbitrary interleaving of all but one of the rest (using different symbols for the various stacks) < 1532695502 826051 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :ais523: yes, I had some sort of question similar to that earlier < 1532695514 292960 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1532695565 108191 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :actually you don't even need a bubble sort for this, just move all the information onto your temp stack until you find an element of the stack you're looking for < 1532695573 604519 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :delete it, encode it in the state, and move all the information back again < 1532695590 886760 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :sure, then it's cubical time < 1532695591 190453 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this should also serve as a proof that you can keep one stack with entirely arbitrary information, because all the stacks you're using for computation are encoded on the other < 1532695619 581361 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this is only an O(n) slowdown, I think? accessing any element of any stack takes a length of time bounded by the total number of elements in all stacks < 1532695621 516932 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :yes, that works < 1532695627 198408 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :um < 1532695657 357616 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :o(n) multiplicative factor sslowdown < 1532695678 370838 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :so like O(n**2) slowdown < 1532695697 287238 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :if the program was running in O(a) space and O(b) time, it now runs in O(a) space and O(ab) time < 1532695702 891035 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :yeah < 1532695713 693243 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :which is actually a fairly good complexity result < 1532695723 366137 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :which is actually important, to track the space and time separately < 1532695726 33978 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :given that space complexities are normally smaller than time complexities < 1532695730 458211 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :exactly < 1532695745 321268 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(with some definitions they're always smaller because it takes time to fill all that space) < 1532695771 216230 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :the space here is going to be only polylog of the time, because the space will only be used to keep a bounded number of addresses on the disk, as many addresses as the simulated machine has registers, plus a few temporaries < 1532695787 600561 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the simulated machine is sub-TC? < 1532695802 177990 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :no, the simulated machine is TC < 1532695805 856830 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :it's a cons heap machine < 1532695813 300074 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :and I care about efficient runtime < 1532695815 794205 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :that was the point < 1532695818 321099 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oh, the addresses get arbitrarily large < 1532695822 200153 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :yes < 1532695838 586702 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :but only logarithmically large, because they're in binary and I allocate them sequentially < 1532695850 361837 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I don't care about garbage collection < 1532695855 468517 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so yes, this runs with polylog slowdown I think < 1532695860 962253 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :right < 1532695868 853914 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :that's all I want to prove < 1532695994 350340 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :this will prove that Consumer Society is efficient in theory, as efficient as, say, SKI calculus or whatever reasonable computational model with unbounded memory size, up to polylog slowdown < 1532696029 312570 :trout!~variable@freebsd/developer/variable QUIT :Ping timeout: 265 seconds < 1532696039 446319 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :and I can separately prove that it's also sort of efficient in practice if you only need compile time bounded sized memory, although not really so efficient that you'd want to run real programs in it, just eso-efficient < 1532696067 729371 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :and that part is easier to program by far, no need to swap symbols from an alphabet on two stacks or such crazy stuff all the time < 1532696076 120459 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :well, I admit to being guilty of writing languages that run in double exponential time before now… < 1532696116 542079 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :although the reason my TCness proof of 3* stalled out is that I wanted to make a more efficient version of the proof < 1532696120 616163 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :Amycus implemented the naive way is much worse than double-exponential < 1532696123 546731 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :involving a more efficient cyclic tag < 1532696127 276024 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :with integers that is < 1532696133 660931 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :that's why I describe how to implement it properly < 1532696184 344693 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :there's no point in having complexity classes beyond double-exponential because they're all far too slow to even comprehend < 1532696188 705868 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :let alone attempt to run programs in < 1532696203 975725 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(this includes double-exponential as one of the classes that's too slow to comprehend) < 1532697424 537960 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :hmm < 1532698446 210070 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532698710 217772 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 256 seconds < 1532698907 969936 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :wob_jonas: it's surprisingly bothering to see someone say nothing for 15 minutes, say "hmm" once, then go silent for another 15 minutes < 1532698948 502491 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :I was just thinking about this disk model a bit more < 1532699692 826576 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1532699815 121827 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1532699949 519510 :int-e!~noone@int-e.eu PRIVMSG #esoteric :hmm < 1532700020 591139 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :hello int-e < 1532700042 473461 :ais523!~ais523@unaffiliated/ais523 QUIT :Excess Flood < 1532700117 430510 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1532700205 532622 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1532700218 641734 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1532701597 726707 :SopaXorzTaker!~SopaXorzT@unaffiliated/sopaxorztaker JOIN :#esoteric < 1532701626 310091 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532701916 292781 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 265 seconds < 1532702440 593015 :S_Gautam!uid286066@gateway/web/irccloud.com/x-pavkxobmfolgdats QUIT :Quit: Connection closed for inactivity < 1532703134 292569 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 265 seconds < 1532703820 214017 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :`olist 1130 < 1532703820 881378 :HackEso!~h@techne.zem.fi PRIVMSG #esoteric :olist 1130: shachaf oerjan Sgeo FireFly boily nortti b_jonas < 1532704827 398793 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532705089 434254 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 248 seconds < 1532706396 314395 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 QUIT :Quit: http://www.kiwiirc.com/ - A hand crafted IRC client < 1532707995 260823 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532708284 252638 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 260 seconds < 1532709035 424102 :sftp!~sftp@unaffiliated/sftp JOIN :#esoteric < 1532709528 263218 :Decim_The_Dark!~yourname@27.97.161.44 JOIN :#esoteric < 1532709576 129098 :Decim_The_Dark!~yourname@27.97.161.44 NICK :Decim_ < 1532709670 318111 :Decim_!~yourname@27.97.161.44 PART :#esoteric < 1532712255 217160 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1532712327 688517 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1532713055 596561 :ais523!~ais523@unaffiliated/ais523 QUIT :Quit: quit < 1532713566 159541 :arseniiv!~arseniiv@95.105.66.57 JOIN :#esoteric < 1532714324 639409 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532714561 262222 :S_Gautam!uid286066@gateway/web/irccloud.com/x-jddwcozvbtxbqvqq JOIN :#esoteric < 1532714638 653375 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 268 seconds < 1532715182 292653 :Phantom_Hoover!~phantomho@unaffiliated/phantom-hoover JOIN :#esoteric < 1532715820 671993 :sebbu!~sebbu@unaffiliated/sebbu QUIT :Ping timeout: 256 seconds < 1532716077 319943 :sebbu!~sebbu@unaffiliated/sebbu JOIN :#esoteric < 1532716132 567387 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532716743 48163 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection > 1532716802 236117 PRIVMSG #esoteric :14[[07Brainfuck in Python14]]4 N10 02https://esolangs.org/w/index.php?oldid=57062 5* 03Kaa-kun 5* (+1212) 10Brainfuck in Python > 1532716890 41554 PRIVMSG #esoteric :14[[07Brainfuck in Python14]]4 10 02https://esolangs.org/w/index.php?diff=57063&oldid=57062 5* 03Kaa-kun 5* (+124) 10Correction > 1532717343 275449 PRIVMSG #esoteric :14[[07Esolang talk:Community portal14]]4 10 02https://esolangs.org/w/index.php?diff=57064&oldid=55607 5* 03Kaa-kun 5* (+432) 10/* Important message from Carbuncle */ new section < 1532722074 962046 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :My high score so far in "Into the Blue" is 36690 points. Did you play that game? It is like a cross between Panel de Pon and 15 Puzzle. < 1532722374 250124 :arseniiv!~arseniiv@95.105.66.57 QUIT :Ping timeout: 256 seconds < 1532722641 415776 :SopaXorzTaker!~SopaXorzT@unaffiliated/sopaxorztaker QUIT :Quit: Leaving > 1532724359 919745 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Sylwester 5* 10New user account < 1532725047 690430 :impomatic!~digital_w@host86-189-136-223.range86-189.btcentralplus.com QUIT :Ping timeout: 240 seconds < 1532725181 769439 :zzo38!~zzo38@24-207-47-161.eastlink.ca QUIT :Ping timeout: 255 seconds < 1532725512 763999 :zzo38!~zzo38@24-207-47-161.eastlink.ca JOIN :#esoteric < 1532727667 429106 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1532727937 473468 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 248 seconds < 1532729776 437034 :erkin!~erkin@unaffiliated/erkin QUIT :Quit: Ouch! Got SIGIRL, dying... < 1532732119 395412 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1532732959 301501 :MDude!~MDude@c-73-187-225-46.hsd1.pa.comcast.net QUIT :Ping timeout: 260 seconds < 1532735891 142220 :MDude!~MDude@c-73-187-225-46.hsd1.pa.comcast.net JOIN :#esoteric