< 1546214467 858481 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :yes, cache is one of the reasons why you want to make context switches rare in first place, not more frequent, even if they're within one user space. but that doesn't answer your question I think. < 1546214505 416697 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I don't see how any stack arrangement really fixes that. < 1546214540 795120 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :Obviously you can make it worse by a really bad scheme, but still. < 1546214626 325328 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Well, imagine you had no compiler support. < 1546214651 437514 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :The straightforward thing you'd do is define a struct for all the asynchronous state you need, including an "instruction pointer". < 1546214679 152916 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :We already have some amount of compiler support. < 1546214733 910850 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :And cpu arch support too, for that matter. It took me some time to figure that out. < 1546214738 988574 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :? < 1546214855 350927 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: you know when x86_64 added the AVX instructions, thus extending 128-bit XMM registers to 256-bit YMM registers, right? The existing XMM registers are aliased to the bottom halves of the YMM registers. < 1546214865 562695 :int-e!~noone@int-e.eu PRIVMSG #esoteric :wait, which do you want... coroutines or userspace threads? < 1546214889 63060 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :They seem like the same kind of thing? < 1546214892 498974 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :what's the difference? < 1546214898 501323 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :how exactly do you define them < 1546214919 460227 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :also the real question is, what you want, since you asked the question in first place < 1546214939 673944 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I want a convenient and efficient way to write code that does asynchronous operations. < 1546214976 498219 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: well, that's somewhat of a different applications then. so coroutines or user-space threads or whatever, but applied to asynchronious IO in particular? < 1546215015 754743 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Coroutines are invoked explicitly (for example, when you hand control off to a generator), which is amenable to static analysis (though obviously only to the extend that function pointers are amenable to static analysis). < 1546215041 67402 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :(Cooperative) userspace threads are coroutines that are invoked by some scheduler. < 1546215107 632841 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :So anyway, when x86_64 did that, they made it so that all existing instructions that modified an XMM register never changed the upper halves of the YMM register. This has the disadvantage that whenever you have libraries compiled to SSE2 and libraries compiled to AVX in the same userspace, and you call between them, then either you have zero all the upper halves, or the cpu has to deal with stashing < 1546215114 34889 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :away the upper halves when it does YMM registers, < 1546215158 361074 :int-e!~noone@int-e.eu PRIVMSG #esoteric :So coroutines often are coordinated in a predictable way. Threads usually aren't coordinated; they are scheduled but do unrelated work. < 1546215162 126393 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Let's imagine I don't care about XMM < 1546215165 340488 :nchambers!~nchambers@learnprogramming/staff/nchambers QUIT :Quit: WeeChat 2.2 < 1546215186 231841 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :or otherwise most SSE2 instructions would suddenly get an extra input, because they have to merge the old value of the output YMM register into the YMM register. The cpu allows both of these: the code explicitly zeroing the YMM registers or the cpu stashing the top halves. < 1546215192 351064 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :But nevertheless, this seems inefficient. < 1546215214 687816 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: you don't care about XMM? but you want efficient code with compiler support? do you want to use a new cpu architecture too? < 1546215220 969614 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Now sure, you can build a scheduler on top of a coroutine mechanism, but any static analysis for coroutines is bound to fail. < 1546215243 201659 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :So for a while I wondered why x86_64 was designed to work that way, instead of all SSE2 instructions just zeroing the top halves of any YMM register that they store into. < 1546215246 714858 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :int-e: OK, then I'll say that I care about cooperative userspace threads. < 1546215270 184308 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Then I'll say that you're in for a lot of trouble. :P < 1546215303 891277 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :But it turns out that that would have been bad, because you couldn't do user-space coroutine switching correctly, which would be a worse cost than the one we have to pay now. < 1546215338 845465 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :amd64 registers are so complicated < 1546215362 855245 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes they are. but if you are asking for efficient code with compiler support, you have to deal with that. < 1546215393 679591 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :For example storing into the lower 32-bits zeroes the upper 32-bits, but storing into the lower 16-bits doesn't zero the upper 16-bits < 1546215418 685774 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes, and that is for exactly the same reason as with the XMM registers < 1546215421 812547 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :well, sort of < 1546215422 733067 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :not quite < 1546215450 868200 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Anyway, what about the specific case of userspace threads ignoring SIMD registers for the moment? < 1546215464 942723 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :back then in the 386, the extra input dependency didn't matter, so that was a sane design choice < 1546215476 440700 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :today it's much more strange, and has a much more obscure reason < 1546215486 327525 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :There's an obvious thing you can do, which is just allocate a stack for each thread and switch out rsp and rip (and the callee-save registers) on context switch. < 1546215491 815540 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: again, then you're losing more than you gain with userspace threads < 1546215516 728757 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :um yes, except you have to save much more than that, specifically all the callee-saved registers < 1546215551 847944 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :The callee-saved registers are not much more than the callee-save registers. < 1546215602 26951 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :um huh? < 1546215613 546621 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :oh < 1546215626 211299 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I mean, you have to save more than just rsp and rip, because there are more callee-saved registers than that < 1546215633 178101 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Hence the word "and" < 1546215654 427774 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :There are six others in System V amd64 ABI < 1546215670 710902 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Saving a few registers is not really the big bottleneck here. < 1546215718 96440 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :the sad part is that you usually have to save both floating point control registers (the x87 one and the SSE2 one), AND the signal mask (not technically a register, but you do have to save it), despite that most of the time they aren't actually changed in the program < 1546215734 342849 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :but it's hard to make sure that no library linked into your program ever changes them, so you have to save them < 1546215745 702153 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :You can just make sure that no library every changes them. < 1546215775 258260 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Changing the signal mask is ridiculous, you have to do a system call per context switch. < 1546215832 747718 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes, that's sad, but you have to do it. the good news is that system calls like that are very fast. < 1546215843 892016 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :sometimes they can even execute purely in userspace. < 1546215854 686827 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :without switching to kernel mode that is. by magic. < 1546215885 294161 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I don't know if the signal mask thing can do that, but the point is, it doesn't have to do IO or anything, it just has to change some flags and check some other flags for pending signals. < 1546215889 446337 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :No, you don't have to do it, because you're writing a program and you know what your program is doing. < 1546215907 527380 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Ah words, my eternal nemeses. I could've saved a lot of typing by just writing that coroutines are much more tightly coupled than threads (userspace or otherwise). < 1546215935 512830 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes, see above what I said about how recompiling all the libraries you link in, including all the nasty parts of glibc, does help, but in practice it's harder than what you might expect by "compiler support" < 1546215983 497043 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :and the signal mask is one you can get away the easiest, because the program has more control over it, but there's no way you can optimize away the two floating point control registers < 1546215995 594313 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :Let me check the source code to see what else I forget that have to be saved < 1546215996 460531 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Maybe your program doesn't do floating point operations. < 1546216020 149656 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: maybe, but it's very unlikely that even all the libraries including libc never do any < 1546216029 386856 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :it's pretty unlikely in fact < 1546216054 378536 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I don't think saving registers is the big bottleneck here anyway. < 1546216118 251139 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :wait, there's some additional crazy stuff here I think < 1546216122 550162 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :something that I forgot about < 1546216123 945442 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I think a much bigger problem with the system I described is that every time you do a stack witch, the entire stack is out of the cache. < 1546216168 734538 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: I don't see why it would be "the entire stack", and I don't see why it's the stack in particular that you care about < 1546216197 640646 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :whenever you use more data than fits in your cache, most of the old data will be out of the cache < 1546216202 239333 :int-e!~noone@int-e.eu PRIVMSG #esoteric :`grWp \bwitch < 1546216208 227428 :HackEso!~h@techne.zem.fi PRIVMSG #esoteric :apt:APT is a technical term in cyber witchcraft, short for "adequate pernicious toe-rags". \ peace witch:Peace witches do alchemy: they turn mundane building material to gold. They're in the same universe where Bowser turned peaceful citizens of the Mushroom Kingdom to building material. < 1546216209 894995 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :it doesn't matter much if it's stack or not < 1546216240 569567 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :if you access very few data during when a coroutine executes, then the other data isn't out of the stack. if you use a lot, then it's out of the stack. < 1546216259 930431 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :What do you mean? < 1546216263 681114 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :sure, there are some fine details going on there because caches are complicated < 1546216272 422681 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :but why is the stack in particular important? < 1546216295 914230 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Because you could do a stack switch and then call a function that uses a bunch of stack space but doesn't do any context switch. < 1546216306 777159 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :And all that memory is not in the cache. < 1546216316 360927 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :I have thought to instead design the instruction set without automatic cache control and instead you must specify your own controls < 1546216460 553715 :int-e!~noone@int-e.eu PRIVMSG #esoteric :. o O ( there's an easy way out... just don't do a context switch. ) < 1546216464 672443 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :zzo38: you know that already gets very hairy, but if you also do user-space coroutine switches, then it gets really horrible < 1546216470 153965 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :int-e: yeah, that's what I said above. < 1546216495 709047 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Or do the transputer thing (3 registers, was it? sweet for context switching!) < 1546216526 510293 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :int-e: OK, what's your alternative? < 1546216540 961167 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I'm not really tied to threads here, I'd like any sort of way to express these asynchronous things nicely. < 1546216669 540108 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I guess I'm not sure why you want to switch away out of the middle of a heavy computation in the first place; that sounds like a job for a proper OS thread to me. < 1546216704 136398 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :A computation doesn't have to be very heavy to suffer from cache misses. < 1546216717 681496 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I'd like to measure this, admittedly. < 1546216731 991213 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I imagine you also have something event-driven where nothing ever takes long, which can all be handled by a single event-driven thread. < 1546216767 287569 :int-e!~noone@int-e.eu PRIVMSG #esoteric :
ACTION shrugs.
< 1546216769 623978 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Sure, and then you'd make structs that correspond more or less to the contents of the stack for the threads, right? < 1546216789 114485 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :YES! < 1546216794 289886 :int-e!~noone@int-e.eu PRIVMSG #esoteric :If they carry state... yes. < 1546216801 283792 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :sorry, that was unrelated to the couroutine thing < 1546216837 370003 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Sure, they carry state. They do a moderately complicated thing. < 1546216863 357016 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: and sometimes the compiler helps you with maintaining those structs implicitly < 1546216908 97428 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :in the first stage by supporting closures; < 1546216961 617742 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :and in the second stage by allowing the programmer to mark functions as "async", and those functions are compiled so that they or other async functions they call can have yield points where they save their state and IP into a struct and pick up from there when you continue them. < 1546216968 145564 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :compilers can actually do both these days. < 1546216984 260484 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Sure, that's one of the schemes I'm describing. < 1546217004 212117 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :the drawback is that you can't do a stackless yield through a function that isn't compiled async, even when it calls your function back, < 1546217021 858588 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :but compiling every function that has callbacks async can cost a lot. < 1546217029 86226 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: I wonder, because you have partially applied arguments, if it's possible to refactor that queue automata you had such that it doesn't do subterm copying. your state tables would balloon but I don't think it'd be _that_ much of an increase. < 1546217053 132845 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :so user-space context switches are easier if you have unpredictable yields from deep inside functions, but generally you want to avoid that. < 1546217095 657664 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I think requiring the user to mark async functions is reasonable. < 1546217100 409724 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes, that's what you said, I just wanted to explicitly tell how it works < 1546217124 137112 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: I don't know what you mean by "partially applied arguments" but any kind of graph reduction requires a representation of references and I'm not going there on this level of non-abstraction. < 1546217127 24255 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes, but the user also needs to learn how to write code efficiently. that is, of course, ALWAYS the case when you want efficient code, because compilers can't just do magic. < 1546217147 55686 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes. The question is how you can help a user who knows what they're doing, of course. < 1546217183 904737 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :both that, and what is it that the user should do exactly < 1546217189 703706 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: `sk results in a unique object that represents the partial application of S to K. further applications produce new, unique objects. I'm asking if it's possible to strip away the states you use to copy subterms around. < 1546217204 446196 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: (the point of graph reduction is that one can share subterms which is what you seem to be suggesting) < 1546217211 222311 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not at all. < 1546217216 729042 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not interested in graphs. < 1546217226 759348 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: in my automaton `sk is just that. < 1546217262 609164 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: It's an application of s to k. There is nothing "partial" about it, it's just not a redex. < 1546217263 956165 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :let me rephrase: I'm wondering if it's possible to eliminate #, %, & and @. < 1546217332 280588 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :it is a partial application... S takes 3 arguments, you've converted it to something that takes 1 and applied it to a single argument. < 1546217341 640446 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :rather, 1 at a time. < 1546217368 831290 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: Yeah, no, that's not the way I see it. ` takes 2 arguments; S and K take none. < 1546217453 149820 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: I'm viewing this as first-order term rewriting. Terms are built from s, k and `; no partial applications. There are rules ``k -> and ```s -> ```. I implement leftmost outermost reduction for these two rules. < 1546217461 819499 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: you know that you almost certainly need at least one data structure that has two child. in this case it's the S2 closure. you can choose different primitives, but you'd have to get REALLY far from combinatorial calculus before you get something with only list-like structures, no tree-like ones. < 1546217497 172522 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: right, and in your execution, you're skipping/moving over subterms. I'm asking you if it's possible to remove those. < 1546217507 387095 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :your state table would grow. < 1546217596 339638 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: I don't see how to do that with finitely many states. And copying is unavoidable if I want to implement ```s -> ``` without changing the term representation. < 1546217670 271409 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :something tells me it's possible to do that with finitely many states, but _not_ generally: you'd need to generate the state tables for any particular term tree. < 1546217899 372257 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :https://ptpb.pw/-OCf/text something like the following. I'm curious if it's poossible to avoid the explosion. < 1546217952 668106 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :whup, one of those rules is wrong. < 1546217984 626515 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: the thing is, to skip over a subterm without using auxiliary symbols, you have to keep track of how many ` you have seen (since when you have to skip n subterms, after seeing a ` you have to skip n+1 subterms), and there is no bound on that number, even for a fixed starting term. < 1546218050 542054 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :int-e: yes, there's no shortcut because you can't avoid a tree-like structure < 1546218055 144075 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: correct. what I'm proposing isn't using a head-based evaluation method but running over the string using basic substitution rules. < 1546218057 647357 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you can't make it just lists nested to a limited depth < 1546218065 538727 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: oh now you have many more markers: (, S, K, ) < 1546218087 210718 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah but (SK) and such can be converted into single symbol markers. < 1546218131 946792 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :just went for a walk earlier and thought of a possible reduction from SK to Thue. < 1546218133 148404 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: so now *you* have partial applications which I have avoided. < 1546218138 969281 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :correct. < 1546218192 620636 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :my thought is that there's a finite set of objects and a finite set of application rules that leads to an evaluator for combinatory logic. < 1546218221 454005 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :I would like to understand the problem you are working on better < 1546218238 216357 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :it is related to SK combinators implemented with string rewriting < 1546218244 281794 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yup. < 1546218257 853435 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :and you use auxilliary characters to represent tape head, guide the evaluation and want to reduce them < 1546218262 195209 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: So... hmm. No, that won't end up being finite. I can produce a starting term that will evolve all off S, (SS), (SSS), (SSSS), ... for example. (It's not even hard if you know how to do abstraction elimination, since you can just iterate \x -> (x S) starting with S. < 1546218271 603899 :int-e!~noone@int-e.eu PRIVMSG #esoteric :s/off/of/ < 1546218313 47135 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I realize that. there's an encoding I've been trying to study/mull over of SK encoded in terms of wang tiles. < 1546218313 554346 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: It's also completely contrary to what I intended to do... namely, find a sweet tradeoff between the number of states required, simplicity, and number of extra symbols. < 1546218324 243307 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :you pasted code before with the # % stuff, can we see it again < 1546218324 477844 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :think I linked it yesterday. < 1546218336 338317 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: do BCKW instead of SK! :-) < 1546218345 355041 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :it doesn't really help, but still < 1546218354 327517 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :heh. < 1546218370 139976 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :http://ceur-ws.org/Vol-1032/paper-01.pdf < 1546218377 78577 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :see https://esolangs.org/wiki/Combinatory_logic < 1546218388 634046 :int-e!~noone@int-e.eu PRIVMSG #esoteric :rain1: if you're wondering about context, the #, %, &, @ refer to states in http://paste.debian.net/1057921/ < 1546218402 297348 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :ah queue automaton < 1546218455 859450 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :ok how about this idea: find a much simpler queue automaton which isalso turing complete and S,K can be macro expressed into in a simple way < 1546218469 480933 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :perhaps that could reduce the rewrite system a bit < 1546218481 550411 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: they give a sample reduction on page 9. < 1546218514 324891 :int-e!~noone@int-e.eu PRIVMSG #esoteric :rain1: it it would be trivial to implement any particular bitwise cyclic tag program. < 1546218530 23739 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :rain1: yes, you do that by making an interpreter for one of those low-powered languages that ais523 likes < 1546218532 176850 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :which involves a finite amount of objects with a finite amount of rewrite rules. it's specific, however, to that particular subterm, I think. < 1546218545 329481 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :such as counter machine stuff < 1546218545 719276 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :yeah but it would be difficult to express SK into cyclic tag wouldn't it? < 1546218555 919592 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :very restricted ones < 1546218558 941790 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :could we find something a bit more powerful than cyclic tag that's still very minimal < 1546218560 727187 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :rain1: yes, it would be < 1546218570 543850 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :anyway just one idea < 1546218578 192630 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you can't just get around that < 1546218583 312550 :int-e!~noone@int-e.eu PRIVMSG #esoteric :rain1: (meaninq BCT is trivial to compile to a queue automaton; in fact it would be fair to say that it *is* a queue automaton) < 1546218628 196296 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah. they encode subterms as specific objects, T0 through T7. < 1546218644 812099 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so you can generate a set of tilings for _that particular_ string of applications. < 1546218668 120294 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :or perhaps one of those 1-dimensional cellular automata thingies that ais523 used to consider earlier could be better than a counter-machine based approach < 1546218680 235097 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you know, the really small universal 1-dimensional CAs < 1546218696 381046 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :I suppose the fundamental difficulty arises from the fact you are processing a linear string, but it represents a tree < 1546218713 564682 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :rain1: yes, and it's a provable performance hit too < 1546218714 389712 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :so tree parsing is mixed up with evaluation - that is what you were discussing before I interrupted < 1546218723 202527 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :b_jonas: you can generate a CA to evaluate a particular term. < 1546218725 818467 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :I think I am up to speed now < 1546218748 169277 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :and if you simulate the CA, you can also easily add various extension rules < 1546218757 777153 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :as in, periodic background patterns < 1546218770 213838 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :which sort of count as cheats for pure CAs, but not here < 1546218789 671654 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so, what's interesting about that is that you can generate a CA from a CL term that's an interpreter of CL terms. < 1546218816 730823 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :oh that is interesting but I imagine the result will bea large CA < 1546218841 682926 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :and it will operated on a SK representation of SK combinators, which introduces overhead < 1546218841 951292 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that honestly depends on your combinator basis. < 1546218844 609260 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: no. I don't think that's true. the interesting about it is that there are very small universal CAs, so you can emulate them easily in a cyclic queue machine. < 1546218852 88646 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :we can switch to the X single combinator basis < 1546218860 68508 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :b_jonas: what's not true? < 1546218870 169725 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: it's not true that you can easily generate a CA from a CL term < 1546218902 852987 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :did you read the PDF I linked. < 1546218905 257384 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :they give a schema for it. < 1546218907 82404 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :no < 1546218918 496422 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :http://ceur-ws.org/Vol-1032/paper-01.pdf page 6 through 9. < 1546218937 685929 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :isn't that wang tiles rather than a CA < 1546218940 864989 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :gives the general method for generating a tileset from a particular term tree within a combinator basis. < 1546218954 60241 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :b_jonas: One of the things that a compiler can do that doesn't happen in a struct is liveness analysis. < 1546218962 360410 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :rain1: a CA is just a wang tileset that discards its history. < 1546218976 279686 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :If you only need some subset of the fields for each state, a compiler can figure that out automatically. < 1546218977 48018 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :a wang tiling can be seen as a representation of the history of a CA. < 1546218997 882665 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :it's trivial to map a 2D wang tiling to a 1D CA, and they give an encoding of CL as a 2D wang tiling. < 1546219061 344741 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: I don't really understand that. if the compiler has the support for compiling async (yieldable) functions in a way that they suspend to a struct, then it can also do liveness analysis on it < 1546219084 115189 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes, sure, I mean compared to a manual struct. < 1546219085 176355 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :is there some difference between that case and the case when you do user-space context switches? < 1546219091 789871 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :i think that is a limited view of wang tiles < 1546219095 879062 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :but I get what you mean < 1546219106 395761 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I mean this is another reason you might want to have compiler support. < 1546219115 550106 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :a 3D wang tiling generates a 2D CA, for example. < 1546219132 55557 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :there are also mappings between 2D wang tilings and 2D CAs. < 1546219153 842936 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: not really. a programmer can also figure out which variables they changed, and store only those, or load only the ones they use < 1546219155 1692 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :you just have a large number of states. < 1546219178 125678 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Sure, but then it's not really a struct anymore. < 1546219189 150464 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Certainly you can do it. < 1546219190 866388 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :don't you agree there are wang tile sets that don't relate to CA? < 1546219201 197912 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: heck, even the compiler can figure out most of that from just the individual, what's it called, primitive block? whatever you call a section of the code with only one entry point and ends at yields < 1546219215 594197 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :rain1: can you show me an example of one? < 1546219225 283883 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :basic block < 1546219270 767931 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: wtf is that paper... < 1546219271 952580 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: um, I mean, if you always reuse the same struct for the storage of the same coroutine, mutating it in place < 1546219280 995298 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: a wild ride. < 1546219287 698602 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :which of course works that simple only if you don't have deep call stacks < 1546219289 791738 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :but still < 1546219300 560681 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :heck, even without that it still works < 1546219303 388119 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :even in a non-mutating way < 1546219313 929241 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :sorry, the in-place store isn't very relevant < 1546219317 167939 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: it starts going wrong when it tries to treat SKI as a monoid. That would require b = I b = K I a b = K a b = a < 1546219331 257487 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :so no, I just don't get the point < 1546219356 807370 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(monoids are associative) < 1546219400 357178 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :int-e: wait, a monoid with respect to composition? HAHAHAHA < 1546219449 681645 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I mean, you might have an operation that does steps A, then B, then C. < 1546219460 336585 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :"Wang Tiles is a monoid, on Tiles as terms, with Wang-arrangement as the only operation." < 1546219464 464327 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: it's also cute how it builds full SKI reduction into the tiles ("Connection Tiles"). < 1546219496 129798 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :You can write the state as struct { enum IP { Start, A, B, C, Done }; AState a; BState b; CState c; }; or something. < 1546219497 855509 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: and the claim that you end up with a finite set of tiles in the end... I don't see where this is proved (which is no surprise because it's necessarily false) < 1546219509 954011 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But in fact you only need enough memory for one of those. < 1546219526 22333 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :(In this case you can just use a union. But in general you might share some state between some steps and so on.) < 1546219527 865618 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: if you look at page 9, you can see an example breakdown: what they've done is map a particular term to a particular set of tiles. < 1546219537 376596 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: sure, you make it a tagged union instead. < 1546219545 937895 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :possibly sharing some common state that is not often modified < 1546219553 656297 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :such as the caller pointer < 1546219553 982400 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so you don't end up with a _general_ set of evaluation rules for SKI in wang tiles, but you have a schema for _converting_ arbitrary SKI terms to wang tiles. < 1546219572 750594 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: infinitely many of them, and SKI reduction is built into the tile set. < 1546219591 175419 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Sure, you can do all that, but liveness analysis does it automatically for you, is all I'm saying. < 1546219593 889957 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :no, not infinitely many. < 1546219602 543202 :int-e!~noone@int-e.eu PRIVMSG #esoteric :even if they don't actually treat it as a monoid (but I think they do) this is utter trash. < 1546219617 12450 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :you're not getting what I'm saying: they build a tileset for evaluating _one_ specific SKI term. < 1546219620 170535 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not the whole space of them. < 1546219628 45146 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :and there's a schema for generating those tilesets. < 1546219630 224511 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: if it has a normal form < 1546219636 305186 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: the scopes of variables in the code, before compiling to an async function, is mostly tree-like, that is, with any two variables, either the first lives longer or the second lives longer, the scope of one contains the other, < 1546219637 157701 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :you do not need infinitely many tiles. < 1546219668 242580 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: and that implies that if you turn it to a struct, you always get a properly nested union-struct, with copies/moves necessary only when the orignal code copies/moves a value. < 1546219729 340082 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :if this paper is bullshit then supercombinators are bullshit. :P < 1546219792 786589 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: For every reduction step, the full redex must be captured in a Wang tile (Fig. 2 is the only place where reductions happen), so all we need is a starting term with unbounded redex size. < 1546219810 599491 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: Really, this is nonsense. I'm sorry to have seen this paper. < 1546219825 415918 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I mean, write up a response to it with proofs. < 1546219855 226268 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I think hasty dismissal isn't a good way of doing things. < 1546219860 740845 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :two-dimension might help to represent a tree structure, because you can put each child expression of the tree one row below the parent, so it's easier to skip the expression by just skipping through markers in the row above, without having to count parenthesis < 1546219861 247879 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :oh < 1546219869 758215 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :I see int-e's point < 1546219885 23920 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :it would require infinitely many tiles < 1546219886 756098 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I mean, if you want to simulate evaluating combinatorial logic with a two-dimensional CA < 1546219890 907181 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :but a wang tileset should be finite < 1546219892 527651 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :of course with just wang tiles it won't help, < 1546219903 406676 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :because with wag tiling you need the second dimension for time < 1546219908 396721 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :(it may be parallel, but still) < 1546219995 242046 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :bear in mind there are also other versions of this paper that go a little more in depth with actual proofs. < 1546219998 880547 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :let me find one. < 1546220058 770023 :int-e!~noone@int-e.eu PRIVMSG #esoteric :"22nd International Workshop on Concurrency, Specification and Programming" ... sad. < 1546220340 734678 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :I can see that some wang tilings are like CAs < 1546220348 585470 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :but I don't see that all wang tilings are CAs < 1546220353 774434 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :I can't give an example < 1546220381 919436 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :it seems like the constructed tilesets have been built with a uniqueness property where the next row/col can be determined by the current one < 1546220413 88274 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :or would it be that each cell is determined by the 3 above it? < 1546220444 540973 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :rain1: of course not. they're more powerful than CAs, because they can do time travel loops, which gets it PSPACE-complete or something. < 1546220457 908272 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :thank you < 1546220463 118684 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :that's the key i was missing < 1546220480 212401 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :pardon me? < 1546220487 707854 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :b_jonas: got a proof for that? lmao. < 1546220513 832908 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: well, they're actually uncomputable, because the space is unbounded < 1546220519 675389 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :so PSPACE-complete is not really true < 1546220524 369388 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :they're not limited to PSPACE < 1546220531 256817 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you know how they're uncomputable, right? < 1546220553 516226 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yes... very much aware. < 1546220558 838048 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: Wang tiles *can* implement string rewrite systems, using an approach like that. But it turns out that combinatory logic is not a string rewrite system, and you actually need to put in some effort (which the authors haven't done) to treat it by string rewriting) < 1546220562 171362 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you can just simulate any nondeterministic turing-machine with one tape < 1546220577 903090 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :the key point is that it allows any nondeterminism < 1546220582 621626 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :which is why you can go back in time < 1546220588 492704 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :i don't like the way imode responsd < 1546220615 243004 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :b_jonas: how does nondeterminism allow you to go backwards in time? < 1546220632 97008 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :rain1: what's that supposed to mean? < 1546220636 859594 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: crucially, the objects of string rewriting (i.e., strings) do have a monoidal structure. < 1546220678 751056 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: you can send information back in time by nondeterministically guessing the information back in the past, sending that information to the future, then making the solution impossible in the future if the information you want to send back isn't the one that you got from the past < 1546220727 951251 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: usually it's told the other way, as in, time travel allows arbitrary nondeterminism, in the TCS sense, but it works backwards too < 1546220732 132019 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :you've lost me, but I don't think that's how nondeterministic execution works. < 1546220755 27669 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: how does it work then? < 1546220755 970107 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: and also crucially, the redexes for any given SRS have bounded size. < 1546220820 196852 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :b_jonas: Sometimes (often?) a variable is declared early and then stops being used in the middle of a block. < 1546220896 684017 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: can you explain to me how they got their results, then? why is it that they were able to compile a particular term down to wang tilings? I don't quite buy the argument that the compiled terms are required to have normal forms. < 1546220923 412929 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: paper is incredibly patient. you can write anything you like. < 1546220925 885820 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :b_jonas: you have multiple possible choices per computation steps, and thus multiple possible paths. < 1546220931 280560 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes. then it's not really strictly tree-like. but note that that only matters if there's a yield in between when it's stopped using and when another variable is started to use. it doesn't matter if you just compute a different new variable from the old one in one step without yield, which is very common. < 1546220938 481354 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 244 seconds < 1546220939 683100 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: there are no results. there are unsubstantiated claims. < 1546220940 969067 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: yes. that's the guessing part. < 1546220957 639342 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: and yet they were able to show a particular reduction... < 1546220959 914329 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you guess by starting a possible choice for each possible value the information you're guessing can have. < 1546220965 12734 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :b_jonas: Why doesn't it matter? < 1546220995 45593 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: because where there's no yield, you don't have to save or load the values to the state struct. < 1546221000 96270 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: help me out here, what's the problem? can you show me a combinatory term that's not able to be translated (using this schema) to wang tiles? < 1546221009 232818 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Sure, in that case. < 1546221014 925825 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: yes, you can write down any finite reduction in that fashion. but it doesn't generalize to infinite reductions, and the system is not sound (it allows you to write down non-reductions that have wrong results, like the a = b chain above) < 1546221072 755916 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes, I admit that in some cases it's not strictly tree-like, and you will definitely get such a case when eg. you have a server that's handling a hundred requests asynchroniously and each can take different amount of waiting to another party. < 1546221095 493005 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :one moment, gotta walk the dog. highlight me and I'll read back. < 1546221122 998307 :int-e!~noone@int-e.eu PRIVMSG #esoteric :same here, sans dog < 1546221329 96224 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :int-e: well, technically you may need a more complicated a=b chain than the one above, because if you don't have S in your expression, then you can always just restrict the rules to do evaluation steps only when the argument is an atom. you need something with parenthesis required in it. < 1546221344 891970 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :but yeah, that if a is a parenthisized expression. < 1546221356 327280 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :hmm no, I'm stupid < 1546221382 184302 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you do have parenthesis, where you write I b = K (I a) b = K I a b = K a b < 1546221389 809963 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :it's the middle step there that's wrong < 1546221421 393655 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :so yeah, I guess you might not need parenthesis < 1546221571 182954 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :um < 1546221574 103858 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I guess you might not need S < 1546221578 753210 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you do need the parens < 1546221889 531390 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :back. < 1546221972 685345 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: ignore what I said while I was gone, that's nonsense. listen to int-e, he's got it right. < 1546221992 11931 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so, here's my reasoning: if you look on page 9 of that paper, the list of "Subterms", they've taken a particular combinatory term and knocked it down to a particular set of objects which they map using a schema to a particular set of tiles, and the tiling of those tiles produces the result. even if you had something like the Y combinator written down, when applied to a particular combinator term, _you would < 1546221992 131829 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :still_ be able to generate a finite amount of tiles, but your tiling would be infinite. < 1546222105 64391 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I agree that the paper is somewhat underspecified but I don't see the damning evidence that it's all trash. < 1546222186 564231 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I'm also not too keen on insulting people's work after a quick glance at it, but that's just my approach. < 1546222229 209095 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :still trying to find that alternate version of said paper. < 1546222785 452064 :nchambers!~nchambers@learnprogramming/staff/nchambers JOIN :#esoteric < 1546222799 520935 :nchambers!~nchambers@learnprogramming/staff/nchambers NICK :uplime < 1546222968 849910 :john_metcalf!~digital_w@host86-191-16-140.range86-191.btcentralplus.com QUIT :Ping timeout: 272 seconds < 1546223083 873488 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :http://ceur-ws.org/Vol-1269/paper34.pdf found this one. it details the same stuff but also includes an implementation of a general CL interpreter within wang tiles by way of a turing machine encoding, similar to your's, int-e. < 1546223147 803298 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so to me it details two approaches: compiling CL terms to their corresponding tilesets, and interpreting an encoding of CL with a single tileset. < 1546223193 15529 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the latter is obvious. the former not so much, but I don't see why it isn't a possible thing. perhaps there even exists an implementation to go along with the paper. I'll try to track one down. < 1546224229 230527 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :Hm, wang tiles correspond quite closely to 1-d nondet cellular automata. I'm not sure if I realized that yet or not. That actually explains why wang tiles are considered powerful, in the sense that they can do hard to predict things with just few different tiles. The tiles correspond to the states of the CA, the CA has that neighborhood where each cell depends on only two cells in the past (not three), < 1546224242 887752 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :only the border conditions of Wang tiles are rather strange, very different from what we're used to with CAs. < 1546224283 989797 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I'm not sure if I had realized that before about Wang tiles or not. < 1546224318 57970 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I think I missed it because I learned about Wang tiles and then mostly forgot about it, and only later learned about how even deterministic 1D CA are so powerful. < 1546224357 863207 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah. there are multiple possible tilings, and it's actually pretty cool to watch a backtracking solver (starting from a seed tile) try to work out a tile by spiralling out. < 1546224389 165016 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :it is possible to make fully deterministic tilings, though, which correspond to fully deterministic 1D CAs. < 1546224400 92282 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the specific literature eludes me at the moment. < 1546224473 79429 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: sure, because a nondet CA is strictly more powerful than a deterministic CA < 1546224485 125205 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :that's usually the way we define nondeterminisitc variants of things < 1546224503 897573 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :what? < 1546224513 724057 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that's not at all true. < 1546224527 967619 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :um, example? < 1546224546 607748 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the fact that a nondeterministic TM can be simulated within a deterministic TM and vice versa. < 1546224551 730411 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the same goes for CAs. < 1546224564 336820 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :no no < 1546224567 188778 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :that's not what I'm saying < 1546224568 462021 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :nondeterministic TMs are not more powerful than deterministic TMs. < 1546224579 309827 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :I'm only saying one dimension < 1546224580 888572 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :um < 1546224582 368331 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :one direction < 1546224596 293966 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :elaborate? < 1546224603 169601 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :that the deterministic thingy can be translated to a nondeterministic thingy easilyi < 1546224606 251543 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :not backwards < 1546224646 292238 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :nondeterministic TMs can be pretty easily converted to deterministic TMs. < 1546224661 939391 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: no, that's backwards < 1546224712 228521 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :how is that backwards. < 1546224837 417533 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: um, there's probably some terminology problem here < 1546224844 96546 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :nondeterministic TMs can be converted to deterministic TMs via dovetailing, which isn't that hard of a thing to do. they can be seen simply as a class of machines that utilize the dovetailing technique. < 1546224878 622737 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I can sort of see what you mean if you say that nondeterministic TMs can be seen as taking deterministic TMs as a subset. < 1546224891 237572 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :but I can invert that and say that nondeterministic TMs are really just a specific subclass of TMs. < 1546224902 307617 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :s/subclass of TMs./subclass of deterministic TMs. < 1546224972 742426 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: um yes, but the dovetailing is still much harder in general than converting the other way, from a determinisitc TM to a nondeterministic TM, for which you don't need dovetailing, only some trivial transformation < 1546225008 434877 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :the specific transformation of course depends on how exactly you define the TM, but then so does the other direction < 1546225018 760918 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :(how you define TM, and how you define nondeterministic TM) < 1546225020 71693 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :like I said, I can invert the relation and say that nondeterministic TMs are just classes of deterministic TMs in which you want to phrase parallel computations. < 1546225028 917990 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :or pseudorandom choice. < 1546225036 597532 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :between multiple branches. < 1546225059 649348 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :it's more 1-D cellular automata than turing-machines that matter here, and the "dovetailing" part actually gets much easier there, mind you < 1546225068 915971 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :because the CAs are naturally parallel < 1546225101 291062 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :the hard part is just making sure that the memory of each simluated copy grows fast enough, which is what remains of the dovetailing < 1546225101 645660 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I'm not sure they are, but they _do_ lend themselves pretty naturally to parallel evaluation methods. < 1546225138 412065 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :like I get what you're saying: nondeterministic TMs are harder to phrase as deterministic TMs because of the extra overhead. < 1546225156 122221 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :but I can make the same argument that simulating a game of chess is hard on a deterministic TM rather than a gameboard with a couple of pieces and some parallel rewrite rules. < 1546225180 358610 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :it's not a fault of the concept of deterministic TMs, but it's just a class of machines. < 1546225286 974928 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :your choice of model defines what kinds of computations are easy and what kinds are hard. < 1546225501 770510 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: wait, are you saying that the paper that translates the combinatorial logic evaluation to Wang tiles uses such a transformation that can make the Wang tile pattern infinite in some significant way (not periodic, nor even some more complicated pattern that's easy to describe in a finite way), even if the evaluation tree of the combinatorial logic is finite? < 1546225551 655658 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not sure what'cha mean, could you rephrase that? having a hard time parsing stuff. < 1546225633 853671 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: um, if you have a set of Wang tiles, there are at least two questions you can ask. (1) one question is whether they can tile a rectangle with adjacent edges identified (eg. a flat torus), which is more or less the same as asking whether it tiles the plane in a periodic way; < 1546225651 726253 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :(2) the other question is whether the tiles tile the plane, not necessarily in a periodic way. < 1546225789 205485 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ah. what I was really just saying is that, using their scheme, it's possible to generate a set of Wang tiles that correspond to terms and subterms (and applications of them) within a certain system of combinators. so small applications of combinators generate other small applications of combinators. these are always finite: one particular string of combinator applications generates another string of < 1546225789 465443 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :combinator applications, and each string can be taken as a single object or multiple objects being applied to eachother. < 1546225791 27185 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :these two questions are essentially different: the first one is computable with the wang tiles as input, the second one is not. < 1546225813 369841 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :this is magic that depends on the periodic bounding combinations. whether the wang tiles tile a rectangle with all zero edges isn't computable. < 1546225819 90812 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :if I understand correctly. < 1546225833 592447 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :so I guess maybe there are three different questions, not two. < 1546225834 478620 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :whether there exists tilings at all for certain tilesets is undecidable, yeah. < 1546225881 328194 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so, the key here is this: we can represent subterms like (SKK) as single terms. any particular combinatory term is guaranteed to generate some particular set of subterms, and we can consider this set finite and use it to build up other terms. < 1546225907 495462 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :so my question is essentially, if the combinatorial logic expression has a finite evaluation, then what kind of tiling do you get from that, if you translate it using what the article does? a tiling of the torus, of the plane, of a rectangle with zero borders, or something else? < 1546225917 52036 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :for any combinatory logic formula, we can generate a set of wang tiles from it such that the tiling of those Wang tiles matches up with the reduction of _that single particular combinatory logic formula_. < 1546225938 366024 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :well, that's the thing. the tiling varies based on the expression you wanna evaluate. < 1546225942 847586 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :and of course whether this transformation is one for which you don't need to compute the entire evaluation tree in advance. < 1546225948 512067 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :because the tiles change from expression to expression. < 1546225958 691789 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :(SKK)S has a different set of tiles, for example, than (SKK)K. < 1546225993 338352 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :but the set of tiles is finite. and even if you include something like the Y combinator, or expressions that don't reduce to normal form, _you still have a finite set of tiles_. < 1546226028 682496 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: wait, so it's a "cheating" transformation that does the turing-complete step of evaluating the term in advance? < 1546226058 186104 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not exactly, no. unless you consider a C compiler reducing things down to assembly a cheating transformation. < 1546226075 932057 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that's essentially their method. < 1546226110 134337 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :no reductions are being performed beforehand. < 1546226121 444795 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :as in, do they basically take the infinite tileset of all possible combinators, or perhaps all possible combinators with a normal form or some such, and then if there's a finite evaluation, then obviously there's only finitely many combinators that appear in that evaluation, but you have to do the full evaluation first to determine that set. < 1546226129 615 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :? < 1546226156 843706 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :you don't have to do the full evaluation to determine the set from what I can see. < 1546226166 935977 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :like, look at page 9. < 1546226177 14088 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :page 9 of which pdf < 1546226220 369086 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :sorry, let me relink you. < 1546226222 465131 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :you mentioned at least two < 1546226227 976657 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :thanks < 1546226240 269652 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :http://ceur-ws.org/Vol-1032/paper-01.pdf < 1546226244 193179 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :though I'll have to go to bed very soon, but we'll have the logs < 1546226244 430732 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :this one. < 1546226249 188086 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :gotcha. < 1546226263 681596 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so, they broke down a particular combinatory term, (((K(S(KK)(S(KK)I))a)b)c)d, into subterms. < 1546226276 872988 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :much like you'd break down a particular textual term into a graph of subterms, right? < 1546226328 33520 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :T6, for example, is KK, and there are two places in that formula where KK is located. < 1546226414 547695 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :you can then show, by way of the schema on page 6 (which I am still studying on how to use properly), that each subterm corresponds to a set of introductions, folds, unfolds, connections (which propagate terms forward) and terminals (which represent the end of a computation). < 1546226481 265437 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: but that's one particular term. isn't this something that should apply to any combinatorial logic expression? < 1546226509 567986 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :correct, but you need to generate a _new tileset_ for every expression you want to evaluate. < 1546226559 570840 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :page 9 seems uninformative, most of it is a huge figure, but let me look at before that too < 1546226570 135439 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the _second_ version of the paper I linked shows a _general_ CL interpreter, which employs the use of a turing machine. < 1546226578 793357 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :which can work for any CL expression. < 1546226638 631001 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :http://ceur-ws.org/Vol-1269/paper34.pdf the second version. < 1546226671 788415 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :so they effectively describe two approaches: one in which you compile a particular CL formula down to a set of wang tiles, and then use the tiling to compute the result of the reduction of that formula... < 1546226706 816167 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :and the other in which you have to start with an interpreter of CL within Wang tiles encoded as a turing machine evaluating CL terms. < 1546226739 210320 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :from pages 5 and 6, I think the error in the paper (or one significant error, at least) is exactly what int-e said < 1546226754 225118 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :which would be? < 1546226768 428610 :int-e!~noone@int-e.eu PRIVMSG #esoteric :yeah and it doesn't work because the reduction isn't prepared to deal with arguments that are longer than a single character. < 1546226777 250581 :int-e!~noone@int-e.eu PRIVMSG #esoteric :("it" being the Turing Machine) < 1546226811 288618 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not sure where you're getting that, int-e. < 1546226815 781884 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :int-e: either that, or it is prepared to deal with it by creating new tiles for each reduction of combinatorial terms that ever occurs in the evaluation < 1546226817 157742 :int-e!~noone@int-e.eu PRIVMSG #esoteric :These people don't know what they're doing at the theoretical end of their work. They *may* know something about DNA computing and Wang tiles though I'm skeptical about that. < 1546226834 346923 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :y'know, why don't you try backing up your statements instead of needlessly bashing people. < 1546226845 697560 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :if they're wrong, diagram it in clear wording. < 1546226858 939308 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: I'm looking at page 6 and there's no bracket handling in the reduction for K, I or S, except that S *inserts* brackets somewhere. < 1546226874 414445 :uplime!~nchambers@learnprogramming/staff/nchambers QUIT :Ping timeout: 250 seconds < 1546226895 180294 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :they don't require bracket handling because they're not reducing a textual form of a CL expression. < 1546226911 423319 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: I'm suspicious about the DNA computing too. that's like the people who claim that soap bubbles or protein folding can efficiently solve NP problems, because *in practice* the possible results of protein folding or soap bubbles can be guessed well from a minimization problem < 1546226916 155364 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :they've extracted common subterms (like you would using graph reduction). < 1546226916 421583 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :um < 1546226918 439727 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :int-e: ^ < 1546226930 395703 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: All you have to do is try running the TM on K(KI)K and see that it gets stuuck in state TK. < 1546226945 917466 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: can you provide an example tileset which shows that? < 1546226961 523339 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :they're not encoding a TM, by the by. < 1546226971 783639 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :well, in the first paper, and in the first section of the second. < 1546226975 691416 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :heck, int-e is probably right, those tiles do seem to explicitly assume that the application is associative, even if each of those colors can represent complicated terms < 1546227022 65433 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: (\f. f f) (\f x p. p x (f f (S x))) S will require an infinite tile set. have fun doing the abstraction elimination... < 1546227023 371450 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :yeah, what he said < 1546227025 95822 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :b_jonas: DNA computing in this regard builds Wang tiles out of DNA molecules. < 1546227034 873623 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I'm DONE. Good night. < 1546227037 737193 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :and has actually been demonstrated. not a fan of the approach. < 1546227049 27485 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: gooodnight. you've provided nothing. < 1546227063 647798 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :o/ < 1546227085 899212 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :imode: right, but the real DNA won't actually compute full non-deterministic problems, just like how the reil proteins won't magically fold into the optimal energy arrangements < 1546227106 736875 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu PRIVMSG #esoteric :good night < 1546227109 622619 :b_jonas!~x@catv-176-63-14-51.catv.broadband.hu QUIT :Quit: leaving < 1546227154 873273 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :lots of hostility with a lack of evidence. for a place where unconventional computing methods are accepted, there's quite a bit of hostility. < 1546227767 319874 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 QUIT :Ping timeout: 240 seconds < 1546227904 471068 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 JOIN :#esoteric < 1546227983 781550 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :. o O ( must resist temptation to look at the pdf to find out if imode or int-e is right ) < 1546228255 558092 :FreeFull!~freefull@defocus/sausage-lover QUIT : < 1546228630 50395 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :imode: just from viewing the discussion here, i suspect int-e is at the point where he considers the error so obvious that it feels like an insult to expect him to write out the counterexample in detail. < 1546228673 545831 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :as in, he has a general idea why it _cannot_ work but it's a pain to write out. < 1546228688 755223 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :then there's nothing more to discuss, as noted by him. < 1546228692 786726 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :
ACTION shrugs.
< 1546228749 386890 :int-e!~noone@int-e.eu PRIVMSG #esoteric :To add insult to the injury: if you restrict the redexes of SKI calculus to a finite set then you get a ground term rewrite system, for which reachability is decidable; hence it's no longer Turing complete. < 1546228812 268772 :uplime!~nchambers@learnprogramming/staff/nchambers JOIN :#esoteric < 1546228815 57865 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :if you're not going to go into any further detail I'm pretty much done as well. < 1546228827 2 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :no need to watch people trash other people's work. < 1546228858 339961 :danieljabailey!~danieljab@cpc75709-york6-2-0-cust725.7-1.cable.virginm.net JOIN :#esoteric < 1546228879 721363 :int-e!~noone@int-e.eu PRIVMSG #esoteric :But yes, I'm totally unwilling to work out the counterexample in any detail because Wang tiles are not the right level of abstraction to work on. I've given the high-level reason further above: Since the full redex is encoded in a Wang tile, and there are reductions for which there are infinitely many distinct redexes, a finite set cannot be enough. < 1546228912 1765 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :a full redex _is not_ encoded in a wang tile. complexes and subredexes are. < 1546228940 306871 :int-e!~noone@int-e.eu PRIVMSG #esoteric :You're wrong. ("redex" refers to the subterm that is headed by the K or S being contracted) < 1546228955 924727 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :"You're wrong." "That's trash." < 1546228968 916588 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I mean, are you going to go into any kind of detail whatsoever. < 1546228995 870593 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Yeah. I'm angry at this point, because you have shown no evidence of actually doing any fucking work yourself. < 1546229003 322144 :int-e!~noone@int-e.eu PART :#esoteric < 1546229029 290646 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :how someone can get so emotional over something so irrelevant is beyond me. hope he's alright. < 1546229061 774853 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :like, if I'm wrong, perfect, I didn't write the damn paper. < 1546229108 613490 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :hell I'm even trying to work out a tileset for his counterexample, which seems like a reasonable approach. < 1546229119 515444 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :hope he feels better when he comes back. < 1546229200 766287 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :if he's right then evaluation should get stuck when one of those newly constructed redexes (that aren't represented in the tiles) has to be reduced. < 1546229304 436317 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I agree with him. I'm trying to follow the methods they used for constructing factorial near the bottom of the paper. < 1546229418 500429 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :they give a series of tuples where each tuple corresponds to a wang tile. each side of a tile corresponds to a subterm, and from what I saw, subterms can be shared. I'm not sure how K(KI)K leads to a redex that can't be represented (or hasn't been generated) as a tile. < 1546229423 793873 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :or as a series of tiles. < 1546229497 695985 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :the K(KI)K example was meant for the TM construction, i suspect < 1546229510 436807 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ah. I don't really care about that bit. < 1546229534 821265 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :it's not really interesting. the compilation bit, now _that's_ interesting. < 1546229582 662916 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I'll have to draw out the factorial tiles tomorrow. < 1546229614 298348 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :they introduce extra convenience combinators related to pairs and naturals, but give no tiles that correspond to them. < 1546229667 566986 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :ahhh, nevermind, those are schemes, not actual tilesets. < 1546229686 75403 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :meaning you stick whatever numbers you want in the subscripts and out pop your tiles. _that_ makes sense. < 1546229698 897357 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :i think the (\f. f f) (\f x p. p x (f f (S x))) S example was for the compilation thing, although i suspect p is unnecessary here... < 1546229716 168026 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :so (\f. f f) (\f x. x (f f (S x))) S < 1546229748 884253 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :is the gist just "generate an infinite series of applications like S(S(S..."? < 1546229776 442675 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :or am I missing something. < 1546229804 684340 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :because from what I can see, there's no issue in doing something like that. < 1546229814 897242 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :well also to do it in such a way that the arguments passed to functions have to grow. < 1546229844 442507 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :there's nothing in here that says that you have to represent things like that as a single tile: in fact, that's not the case at all. < 1546229849 510992 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :so that they cannot be something that is already encoded as a single tile < 1546229888 442157 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :correct: the structure of the terms is incidental, based on how the terms pair. you're not shoving entire trees into single tiles, otherwise you _would_ need infinite tiles. < 1546229908 26328 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :but you _can_ extract commonly found subtrees and use them to form larger applications. < 1546229936 240973 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :which if I'm drawing this correctly, the addition example does. < 1546229959 882195 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :imode: ok, but can it reduce something like S x y z, where x,y and z are _not_ subterms of the original expression? < 1546229985 822939 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yes, because you can construct the subterms that _aren't_ in the original expression _from_ subterms in the original expression. < 1546230003 548947 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :at least from what I can see. < 1546230058 533881 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :like their tiles and reductions reflect subterm sharing. < 1546230064 288294 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :imode: you can construct them, but does reduction work for them? < 1546230076 168780 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :yeah, looks like it. otherwise naturals would break down almost instantly. < 1546230088 845680 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :hm < 1546230138 669204 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :http://ceur-ws.org/Vol-1032/paper-01.pdf trying to draw out and navigate page 13 of this PDF. < 1546230202 928059 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the footnote on that page details that n and m are essentially "pre-selected numbers", so fill in the naturals and generate your tiles from this schema. < 1546233110 866236 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :imode: ok i browsed through some of the pdf. assuming you're not meant to "evaluate ahead" to find tile colors, as far as i can see, there is no way to reduce S x y z unless at least _one_ of S x y, z, or S x y z is a tile color. Constructing an SKI expression that eventually reduces S x y z where none of x, y or z occur in the original expression is left as an exercise. < 1546233431 509267 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :or more generally, you cannot ever reduce an application if it is not equivalent to an original tile color or the application of a pair of tile colors. < 1546233474 621243 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that sounds about right to me. < 1546233477 146595 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :which means you cannot, say, construct an infinite list of numbers. < 1546233519 892575 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :(say, lazy list of factorials) < 1546233531 111750 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I'll have to try that. < 1546233672 655563 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :that monoid thing also looks a bit grating - it seems to me that you could easily get into a situation where evaluation confuses a b (c d) with a (b c) d < 1546233699 744264 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I tried diving down the rabbit hole with that. < 1546233850 222428 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :although i'm a little unsure whether the "sound computation grid" property is supposed to help with that < 1546233986 240634 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :hm actually it _does_ seem to be intended to do that < 1546234068 903040 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :essentially it enforces a kind of parenthesization by dividing up the grid into non-interacting parts. < 1546234196 325808 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :(how they expect DNA to enforce that property i dunno ;P) < 1546234267 987124 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the DNA stuff is actually plausible: you can form small DNA tiles by forming two DNA strands in such a way that the base pairs encode the colors of the edges, and only bind to base pairs. < 1546234276 880592 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :that ironically is the most plausible point of this, because it's been done. < 1546234383 689880 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :yes, i mean the sub-grid property, not the individual tiles < 1546234388 132243 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :oh. < 1546234397 732955 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :sorry, reading comprehension failed me. < 1546239599 427123 :oerjan!oerjan@hagbart.nvg.ntnu.no QUIT :Quit: Nite < 1546240406 684958 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :Now in this GURPS I can tell who is the shapeshifter because they have "X" on their forehead. Next, I have to stop them from writing "X" on everyone else's forehead too! < 1546244808 484566 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546250523 747449 :AnotherTest!~turingcom@d51a4b8e1.access.telenet.be JOIN :#esoteric < 1546250794 728208 :AnotherTest!~turingcom@d51a4b8e1.access.telenet.be QUIT :Ping timeout: 250 seconds < 1546251416 521013 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :after some careful consideration that paper was full of shit. < 1546251441 967423 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I tried working some of the tilings out and yeah, the people above me were right. < 1546251463 638823 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :oh well! < 1546252388 182259 :int-e!~noone@int-e.eu JOIN :#esoteric < 1546252427 363732 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1546252439 249746 :arseniiv!~arseniiv@94.41.6.191.dynamic.ufanet.ru JOIN :#esoteric < 1546252830 409392 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546253919 846721 :int-e!~noone@int-e.eu PRIVMSG #esoteric :imode: Three remarks about why I might core than I maybe should. a) this is essentially in my current area of research (term rewriting, tree automata (which feature in decidability results for ground term rewrite systems; http://tata.gforge.inria.fr/ may be the best available source on that topic)) b) I hate to see people wasting their time with wrong claims c) it becomes frustrating when I fail... < 1546253925 856696 :int-e!~noone@int-e.eu PRIVMSG #esoteric :...to convey that information efficiently, ending up wasting even more time rather than helping. < 1546253939 834570 :AnotherTest!~turingcom@ptr-82l26zcjpltykrbgmmx.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546253982 388736 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :int-e: it's fine, you're good! I concluded independently that it's not a good paper. < 1546254025 877001 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :there's some woeful underspecification or lack of understanding on their part. < 1546254178 317664 :derpy_!~quassel@ppp-62-216-204-119.dynamic.mnet-online.de QUIT :Ping timeout: 245 seconds < 1546254206 752724 :derpy!~quassel@ppp-62-216-204-248.dynamic.mnet-online.de JOIN :#esoteric < 1546254222 837424 :AnotherTest!~turingcom@ptr-82l26zcjpltykrbgmmx.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 252 seconds < 1546254980 824260 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 250 seconds < 1546256962 236383 :arseniiv!~arseniiv@94.41.6.191.dynamic.ufanet.ru QUIT :Ping timeout: 246 seconds < 1546260159 775682 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu JOIN :#esoteric < 1546260199 917463 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: it doesn't get stuck on (KI). there are tiles to open the parenthesis. anywhere, even in a left term. they really seem to believe that the application is associative. < 1546260251 727060 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: also, not only do they add a color for every combinator calculus term, but also a tile for every combinator calculus reduction. not just one step reduction, but any reduction. so you can do any finite computation in one tile. < 1546260292 743362 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :that latter part is a fixable bug, but I think it illustrates how the authors don't understand what they're talking about. < 1546260299 144944 :int-e!~noone@int-e.eu PRIVMSG #esoteric :b_jonas: as oerjan suggested, that was for the Turing Machine in the second paper. < 1546260358 353510 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: that may make a bit more sense, because a TM can actually be simluated as a 1-D CA in a more straightforward way than the, uh, monoid of combinator calculus < 1546260384 434535 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :the "monoid" thing confused me because they don't explicitly state what operation it's a monoid over, but it does become clear by page 6 < 1546260416 894164 :int-e!~noone@int-e.eu PRIVMSG #esoteric :("that" referring to the K(KI)) < 1546260512 293826 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: and yes, I agree that you can't work out a proper counterexample, because the paper is vague enough without precise definitions and proofs that you can't point out more specifically than that where the error is < 1546260643 638994 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: the part where they have single-tile reduction for every calculation is great, because if they actually implemented that, it would let them get the right result in a randomized imlementation that looks for random small tilings, as opposed to a true nondeterministic implementation, so the DNA computation would run trivially with just one transformation from the input to the result and a lot of < 1546260649 754348 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :unused stuff < 1546260768 515638 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :wtf, now even oerjan looked at it? why? < 1546260777 632496 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :(still looking at the logs) < 1546260836 570093 :int-e!~noone@int-e.eu PRIVMSG #esoteric :`? cdop < 1546260838 34590 :HackEso!~h@techne.zem.fi PRIVMSG #esoteric :CDOP is OCPD, except with the letters in the *proper* order. < 1546260925 178657 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Put differently, he probably reached the point where he had to find out what all the ruckus was about. < 1546260989 253794 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: also, I verified that for both of those disconnected polyminos, there's essentially one tiling that is invariant to translation (0,8) and translation (8,0), and I know the tilings I had back when I first tried this were invariant to those. that imples that the tilings you show on grid6.png are the ones I found. < 1546261052 136129 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :int-e: these polyminos are significant because I think, but I'm not sure, that they're the only polyminos of 4 squares that can't tile the plane with just translations and horizontal and vertical mirrors and 180 deg rotations, you really need a 90 deg rotation or diagonal mirror < 1546261061 863406 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu PRIVMSG #esoteric :there was an article on that, let me check < 1546262451 940465 :arseniiv!~arseniiv@94.41.6.191.dynamic.ufanet.ru JOIN :#esoteric < 1546264724 945918 :arseniiv!~arseniiv@94.41.6.191.dynamic.ufanet.ru QUIT :Ping timeout: 246 seconds < 1546265331 315844 :arseniiv!~arseniiv@94.41.6.191.dynamic.ufanet.ru JOIN :#esoteric < 1546268796 731893 :uplime!~nchambers@learnprogramming/staff/nchambers QUIT :Ping timeout: 272 seconds < 1546269197 496243 :Essadon!~Essadon@81-225-32-185-no249.tbcn.telia.com JOIN :#esoteric < 1546269241 418940 :Essadon!~Essadon@81-225-32-185-no249.tbcn.telia.com QUIT :Max SendQ exceeded < 1546269267 311062 :Essadon!~Essadon@81-225-32-185-no249.tbcn.telia.com JOIN :#esoteric < 1546269347 828443 :b_jonas!~x@catv-176-63-13-166.catv.broadband.hu QUIT :Quit: leaving < 1546269508 131191 :AnotherTest!~turingcom@ptr-82l26zcjpltykrbgmmx.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546269784 128268 :AnotherTest!~turingcom@ptr-82l26zcjpltykrbgmmx.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 268 seconds < 1546270536 374073 :AnotherTest!~turingcom@d51a4b8e1.access.telenet.be JOIN :#esoteric < 1546270950 311137 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 JOIN :#esoteric < 1546271100 496037 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 QUIT :Ping timeout: 250 seconds < 1546271104 770610 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 NICK :Lord_of_Life < 1546271360 988737 :AnotherTest!~turingcom@d51a4b8e1.access.telenet.be QUIT :Ping timeout: 246 seconds < 1546271490 602317 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :it was good < 1546272859 948582 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be JOIN :#esoteric < 1546273481 972695 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be QUIT :Ping timeout: 246 seconds < 1546274247 302502 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 240 seconds < 1546276458 5020 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Read error: Connection reset by peer < 1546276484 982057 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546277977 817636 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be JOIN :#esoteric < 1546279202 51009 :S_Gautam!uid286066@gateway/web/irccloud.com/x-rcdntxetziqdjvqc JOIN :#esoteric < 1546279467 233938 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`olist 1150 < 1546279468 192188 :HackEso!~h@techne.zem.fi PRIVMSG #esoteric :olist 1150: shachaf oerjan Sgeo FireFly boily nortti b_jonas < 1546279991 992240 :oerjan!oerjan@hagbart.nvg.ntnu.no JOIN :#esoteric < 1546281188 728669 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be QUIT :Ping timeout: 250 seconds < 1546281223 699665 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu JOIN :#esoteric < 1546281360 780173 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :private fireworks are going strong < 1546281458 451550 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546281493 444014 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric < 1546281752 726442 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :here too < 1546281779 151476 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :@time < 1546281781 826637 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :Local time for shachaf is Mon Dec 31 10:42:59 2018 < 1546281887 934126 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :hm xkcd's consensus new year was about a quarter hour ago < 1546281904 237537 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :so happy new year, i guess! < 1546282653 235843 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :it's not yet new year, but happy new year to you as well < 1546282654 55470 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :b_jonas: that crap paper actually has a kind of solution to the monoid confusion in the "sound computation grid" section. however, the fact that every reduction result needs to be represented on a tile clearly blows it for any expression that constructs infinitely something like the lazy list of factorials i suggested. < 1546282679 367417 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :oerjan: ok < 1546282707 434573 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :b_jonas: see xkcd hth < 1546282861 912673 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :and yeah, i had to see if the problem with the paper was as obvious as int-e implied. < 1546282868 56180 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :oerjan: yes, I've seen it < 1546282873 985023 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :(plus, i didn't like the animosity) < 1546282966 383354 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1546282988 287818 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be JOIN :#esoteric < 1546283003 257797 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :happy new year's eve. < 1546283012 538223 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :hip hip < 1546283044 772332 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :new year starts in less than four hours by the way < 1546283050 598557 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :let's celebrate < 1546283740 486179 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :is freenode doing that newyears thing again? < 1546283789 998192 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :imode: I'm not sure what counts as a "that newyears thing" specifically. there's a #freenode-newyears linked from the topic of #freenode , but then, irc channels are cheap once you have a network up < 1546283803 121571 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :imode: do you mean sending wallops? < 1546283809 968783 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :or global notices or whatever? < 1546283832 154212 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :the channel was what I was referring to. < 1546284056 242129 :arseniiv_!~arseniiv@46.191.210.13 JOIN :#esoteric < 1546284253 250512 :arseniiv!~arseniiv@94.41.6.191.dynamic.ufanet.ru QUIT :Ping timeout: 245 seconds < 1546284595 823960 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :what? < 1546284603 90566 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :I'm confused now < 1546284622 750249 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :it's a common human state hth < 1546284650 65814 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :in NES Super Mario Bros, how many fireballs does it take to kill Bowser (without jumping on him)? I thought it took six, but https://www.youtube.com/watch?v=xJcAPGf0Z6A says five. < 1546284762 529165 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :I may be mixing it up with GB Super Mario Land, in that one it takes six fireballs to kill most of the bosses (the castle bosses are immune, and the witch is possible to kill but very hard because she despawns immediately after a hit) < 1546284887 275089 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be QUIT :Ping timeout: 240 seconds < 1546287052 617079 :uplime!~nchambers@learnprogramming/staff/nchambers JOIN :#esoteric < 1546287246 938302 :AnotherTest!~turingcom@d51a4b8e1.access.telenet.be JOIN :#esoteric < 1546287265 650999 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :in girl genius, maxim's nose seems to be growing lately. < 1546287744 811374 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Hmm private fireworks are illegal in the city this year... still hearing stuff though. People don't know or don't care. < 1546287762 24030 :AnotherTest!~turingcom@d51a4b8e1.access.telenet.be QUIT :Ping timeout: 246 seconds < 1546287800 50170 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :int-e: they are legal here with strong restrictions, but most of how people use them are illegal and sometimes dangerous < 1546287803 570136 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :so be careful < 1546287830 750573 :int-e!~noone@int-e.eu PRIVMSG #esoteric :But I guess it's quieter than last year. < 1546288003 851420 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :i think they're allowed in the suburbs here but not the city center < 1546288230 714224 :int-e!~noone@int-e.eu PRIVMSG #esoteric :it's per muncipality, and I guess it's allowed outside of cities where it's not a fire hazard. < 1546288396 986584 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :forbidden inside the red stippled line, allowed 18:00 - 2:00 outside https://www.tbrt.no/images/artikkelbilder/ForbudssoneforfyrverkeriiTrondheim.jpg < 1546288446 966968 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :
ACTION isn't even on that map, but a bit further east
< 1546288512 398511 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :(there are municipal fireworks inside the zone though) < 1546288613 340930 :int-e!~noone@int-e.eu PRIVMSG #esoteric :b_jonas: hah. "experts warn of illegal firecrackers" < 1546288666 666603 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I'm used to that warning. It hasn't changed in the past 30 years. < 1546288725 155905 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(and personally I don't even like the legal ones) < 1546288788 484149 :arseniiv_!~arseniiv@46.191.210.13 PRIVMSG #esoteric :oerjan> hm xkcd's consensus new year was about a quarter hour ago => wow, pretty close to mine! (UTC+5) < 1546288886 138773 :arseniiv_!~arseniiv@46.191.210.13 NICK :arseniiv < 1546288888 702956 :int-e!~noone@int-e.eu PRIVMSG #esoteric :hmm, average time zones by person? so india and china have a huge influence? < 1546288900 941547 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :int-e: median < 1546288906 621082 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(I had not seen the xkcd yet) < 1546288930 335171 :int-e!~noone@int-e.eu PRIVMSG #esoteric :right, median makes more sense actually < 1546289189 952152 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1546289357 513854 :arseniiv!~arseniiv@46.191.210.13 PRIVMSG #esoteric :ah, not that close, it’s 6:30 UTC, not what I thought, so not that significant. Or contrary, more significant, as it’s further from the median and so rarer(?) < 1546289453 924943 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :average would be a bad idea, it may be skewed by the few people who live in mediaeval theme parks that are in timezones several centuries before most of the earth < 1546289463 365537 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :ok, maybe not that skewed, but still < 1546289704 826309 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :The red line doesn't seems to enclose anything. < 1546290145 726495 :77FABDJ8V!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546290580 328965 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :zzo38: the fjord is not very flammable and so considered obviously not included hth < 1546290614 395312 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :i suppose you could ask how far from shore a boat must be < 1546290903 50215 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :Yes, so they should make the line enclosed so that you can know. < 1546290929 901412 :77FABDJ8V!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1546292052 205658 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :"You must not set off fireworks between 11pm and 7am, except for: -- New Year’s Eve -- when the cut off is 1am" < 1546292116 621407 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :There were a few pops when there was still daylight, which is a bit odd. < 1546292221 562556 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :fizzie: sure. a lot of the illegal explosives go for the sound and blowing off stupid people's hands, not for the sight. < 1546292246 951936 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :it's traditional for a few people to blow their own hands off every New Year < 1546292321 978534 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :people are discouraged from that both because the kinds of explosives used for that are illegal and if you blow your hand off you're almost certainly discovered, and because spending New Year in the hospital is unpleasant, but people still do it < 1546292355 259182 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :There's far more fireworks here on Bonfire Night (aka Guy Fawkes Night) than on New Year's. < 1546292821 427907 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :Anyone in the +0200 timezone (Finland or Romania)? Should we do a small countdown then? < 1546293025 302213 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546293099 423033 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :Because if not, then I'll reserve the celebration for the +0100 and leave some for the +0000, -0500, -0800 ones. < 1546293116 743141 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :Anyway, I'll prepare the New Year sausages. < 1546293292 251382 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 246 seconds < 1546293611 636142 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :For anyone with +0100 timzone offset, happy New Year! < 1546293764 326975 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :. o O ( i think you're off by one again ) < 1546293885 936356 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :yeah darn +0200 < 1546294042 216147 :int-e!~noone@int-e.eu PRIVMSG #esoteric :. o O ( CET+1 ) < 1546294182 523774 :S_Gautam!uid286066@gateway/web/irccloud.com/x-rcdntxetziqdjvqc QUIT :Quit: Connection closed for inactivity < 1546294422 425503 :uplime!~nchambers@learnprogramming/staff/nchambers QUIT :Ping timeout: 250 seconds < 1546294728 776130 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546297067 414894 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1546297177 324653 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :And now the New Year is coming up in our timezone offset, the actual +0100 (France, Germany, Poland, Norway, Hungary) < 1546297183 350693 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :Just a few minutes. < 1546297190 370508 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :And now the New Year is coming up in our timezone offset very soon, the actual +0100 (France, Germany, Poland, Norway, Hungary) < 1546297208 677997 :int-e!~noone@int-e.eu PRIVMSG #esoteric :BOOM. < 1546297303 763245 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :happy new year! < 1546297337 834929 :int-e!~noone@int-e.eu PRIVMSG #esoteric :
ACTION listens to money going up in smoke.
< 1546297448 495896 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :Happy New Year! < 1546297479 73358 :int-e!~noone@int-e.eu PRIVMSG #esoteric :oh sirens < 1546297832 272932 :sprocklem!~sprocklem@unaffiliated/sprocklem JOIN :#esoteric < 1546298224 142018 :uplime!~nchambers@learnprogramming/staff/nchambers JOIN :#esoteric < 1546299021 239995 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546299277 223650 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 246 seconds < 1546300293 574192 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :In the +0000 timezone offset (UK), New Year will start in about 9 minutes. < 1546300329 940777 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :Not much action on the fireworks front. < 1546300569 322074 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :There was more half an hour ago. Maybe everyone's watching the official ones. < 1546300583 523191 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :(Sadly our windows are to the wrong direction.) < 1546300711 183638 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :less than 90 seconds < 1546300729 206390 :b_jonas!~x@catv-176-63-14-142.catv.broadband.hu PRIVMSG #esoteric :fizzie: use the power of the internet to watch the official ones! < 1546300763 453144 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric