< 1546474301 466750 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric : where your primitives are a * : ^ ! (a) (*) (:) (^) (!) <-- you only need ^ without parens, i'm sure this variant has been discussed before... < 1546474381 352753 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :in the context of "underload" with only finitely many basic commands < 1546474523 462499 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oerjan: this isn't an attempt at TCness, but an attempt at implementing full Underload via string rewrites < 1546474549 563540 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :not generalized string rewrites either, literal "search for all instances of string X and replace them with string Y" < 1546474766 245305 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :code like (:)^ will probably need an unescaped : in the internal state at some point… < 1546474927 973938 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1546474976 620063 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :you seem to have dropped ~ although that's theoretically expressible < 1546474980 711396 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :hm very laggy < 1546474991 322186 :ineiros!ineiros@kapsi.fi JOIN :#esoteric < 1546475091 42855 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :actually I've moved back towards including ~ over ^, and adding an additional primitive < which is equivalent to a*^ < 1546475347 521884 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :something I've noticed with both 7 and now this is that the outermost level of escaping seems to act differently from the others in Underload-alikes < 1546475429 662124 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :say, (~) doesn't act much like ~ but does act a lot like ((~)), and you can freely exchange escaping levels and as except at the outermost level; (((~))), ((~))a, (~)aa are all equivalent, but ~aaa isn't < 1546475476 661830 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so you can deal with highly escaped primitives by storing them internally in the (~)aa form but you still need a separate ~ primitive < 1546475589 719913 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :if i didn't already know this is TC in a different way (because of :()^), i'd suspect you'd hit "cn't get more than a PDA" problems < 1546475646 191388 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I think I have a workable solution already, it's just really ugly; I'm going to try to implement it and see if it works < 1546475779 125723 :oerjan_!bc715ce1@gateway/web/freenode/ip.188.113.92.225 JOIN :#esoteric < 1546475821 7044 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :hm < 1546475868 397607 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :not sure whether to keep the webchat open or not, this connection is still horribly laggy < 1546475935 414814 :oerjan_!bc715ce1@gateway/web/freenode/ip.188.113.92.225 QUIT :Client Quit < 1546476012 989121 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :anyway, i don't think a PDA can swap two large sections of stack < 1546476060 415333 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this is more like a cellular automaton than a PDA, though < 1546476066 730550 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :replacements don't have to happen at the rightmost end of the string < 1546476106 700153 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :right. but swapping two large sections is still awkward, i'd thikn you need something simulating a counter < 1546476821 905706 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes, I think you need that too < 1546476947 241834 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :ah The Whiteboard comic asks the inevitable question < 1546476987 631662 :int-e!~noone@int-e.eu PRIVMSG #esoteric :http://paste.debian.net/1058394/ is a potential swapping mechanism that uses a copy of the string alphabet in order to be cute. < 1546477019 670077 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(and... uh I should probably not reuse | like that in the end) < 1546477078 155133 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :i'm not sure, but i have a kind of impression that ais523 wants all the tokens to be a tleast nominally equivalent to underload programs < 1546477080 610376 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(I suspect this is awkward to set up) < 1546477106 768244 :int-e!~noone@int-e.eu PRIVMSG #esoteric :uh, no extra symbols at all? < 1546477113 472403 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you need extra symbols < 1546477118 449859 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :oh ok < 1546477131 117364 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :(i guess it's just me, then :P) < 1546477131 163829 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but ideally I'd like to keep things fully concatenative < 1546477142 740798 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so it's basically just "Underload with a bunch of extra symbols that mean Underloadish things" < 1546477147 185379 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :like < for example < 1546477187 72480 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :http://nethack4.org/pastebin/20.txt < 1546477193 52231 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :probably contains mistakes < 1546477275 73404 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :x and y are placeholders for any Underload primitive; | is the counter (and the only not-fully-concatenative primitive); [x] is equivalent to (x)~ < 1546477316 190975 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :also ("))S is an abomination but there's no way to write "output a closing parenthesis" in Underload :-) (also that line's wrong because it outputs the opening parenthesis too early) < 1546477678 527572 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :you can't really do S as a side effect in a parallel string rewriting regime... < 1546477706 969696 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :you need to collect them until the end, or the like < 1546477745 343488 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes, collect them at the left end I think < 1546477758 896071 :int-e!~noone@int-e.eu PRIVMSG #esoteric :but maybe you can make things simpler by adopting a leftmost strategy < 1546477847 621455 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(and I suspect it's still hard enough *with* such concessions) < 1546478037 993199 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(I write "I suspect" because Underload is a language I've avoided looking into so far.) < 1546478290 435784 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :this makes my head hurt. maybe later. < 1546478625 959322 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :int-e: the problem is that Underload's "natural" evaluation order is outermost, with leftmost as a tiebreak < 1546478647 993843 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :if you go purely leftmost, programs like ((:^):^)! which should be no-ops will get stuck in an infinit eloop < 1546478665 547170 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but "outermost" is hard to define in a pure string rewriter < 1546478926 622777 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :well you aren't putting inner levels explicitly in this syntax, so they shouldn't match anyway < 1546479007 36634 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :in this syntax it'd be (:)(^)*a(:)*(^)*!, so yes, no match < 1546479200 415139 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1546481098 861705 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546481259 348506 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :my internet connection sucks today :( < 1546482721 62564 :ais523!~ais523@unaffiliated/ais523 QUIT :Quit: quit < 1546483229 801763 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :*S should be [S]_< < 1546491712 841146 :oerjan!oerjan@hagbart.nvg.ntnu.no PRIVMSG #esoteric :i'm so lagged tmux misinterpreted my arrow keys < 1546491905 674289 :Cale!~cale@2607:fea8:995f:fb71:f4a1:f816:c4a5:776e JOIN :#esoteric < 1546492586 991911 :Sgeo__!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546492776 396364 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 250 seconds < 1546493809 432031 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546494002 960199 :Sgeo__!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 246 seconds < 1546495246 556171 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :I dreamt of a particular topological schema for computation, where the state space of a model of computation is modeled as a particular surface, and an individual computation is a walk/trajectory along that surface. < 1546495446 976805 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :OK, do you have a detail? < 1546495542 968351 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :not particularly. the dream didn't include the method. < 1546495655 829172 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :OK < 1546495664 991008 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :Now you should try to make up the method. < 1546500485 120731 :arseniiv!~arseniiv@94.41.79.143.dynamic.ufanet.ru JOIN :#esoteric < 1546500983 79595 :oerjan!oerjan@hagbart.nvg.ntnu.no QUIT :Quit: Nite < 1546501971 110890 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection < 1546501985 308084 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric < 1546504740 450676 :uplime!~nchambers@learnprogramming/staff/nchambers QUIT :Quit: WeeChat 2.2 < 1546509156 392173 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 250 seconds < 1546509879 840669 :AnotherTest!~turingcom@ptr-82l26zcjpltykrbgmmx.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546510137 845524 :AnotherTest!~turingcom@ptr-82l26zcjpltykrbgmmx.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 252 seconds < 1546512581 637121 :myname!~myname@ks300980.kimsufi.com JOIN :#esoteric < 1546513917 690179 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be JOIN :#esoteric < 1546514801 663630 :AnotherTest!~turingcom@d51A4B8E1.access.telenet.be QUIT :Ping timeout: 250 seconds < 1546516505 253189 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 JOIN :#esoteric < 1546516522 623786 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :ais523: or you could implement a small one-tape turing machine instead < 1546516551 525816 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 PRIVMSG #esoteric :postfix Underload => isn't 7 trying to be that? < 1546517227 642328 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546517479 663940 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 250 seconds < 1546518005 972125 :arseniiv!~arseniiv@94.41.79.143.dynamic.ufanet.ru QUIT :Ping timeout: 246 seconds < 1546519141 428134 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Read error: Connection reset by peer < 1546519165 512065 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546519992 608306 :Essadon!~Essadon@81-225-32-185-no249.tbcn.telia.com JOIN :#esoteric < 1546520015 421131 :Essadon!~Essadon@81-225-32-185-no249.tbcn.telia.com QUIT :Max SendQ exceeded < 1546522119 998151 :xkapastel!uid17782@gateway/web/irccloud.com/x-dmcjvuplulkklfik QUIT :Quit: Connection closed for inactivity < 1546523346 681578 :Sgeo!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546523586 547646 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 250 seconds < 1546525032 724462 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546525305 630225 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 250 seconds < 1546527306 134121 :xkapastel!uid17782@gateway/web/irccloud.com/x-bdyispdlihwimfuo JOIN :#esoteric < 1546527766 622014 :uplime!~nchambers@learnprogramming/staff/nchambers JOIN :#esoteric < 1546530318 720140 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 JOIN :#esoteric < 1546530512 850640 :sleepnap!~thomas@2603:3015:260e:1900:8319:87ab:f00:d5de JOIN :#esoteric < 1546530540 758863 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 QUIT :Ping timeout: 272 seconds < 1546530541 172728 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 NICK :Lord_of_Life < 1546530908 862372 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546531429 666361 :arseniiv!~arseniiv@94.41.79.143.dynamic.ufanet.ru JOIN :#esoteric < 1546532259 947641 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1546533583 456376 :uplime!~nchambers@learnprogramming/staff/nchambers NICK :Sherlocklime < 1546533950 396890 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546533994 451509 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`ysaclist 83 < 1546533995 427282 :HackEso!~h@techne.zem.fi PRIVMSG #esoteric :ysaclist 83: boily shachaf < 1546534171 644199 :Sgeo!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 250 seconds < 1546534300 821799 :Sherlocklime!~nchambers@learnprogramming/staff/nchambers NICK :Sherlime < 1546534758 573824 :wob_jonas!25bf3cd1@gateway/web/cgi-irc/kiwiirc.com/ip.37.191.60.209 QUIT :Quit: http://www.kiwiirc.com/ - A hand crafted IRC client < 1546535070 679924 :Sgeo__!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546535247 288962 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 240 seconds < 1546536121 994591 :oren!~oren@ec2-18-212-11-99.compute-1.amazonaws.com PRIVMSG #esoteric :god the internet at work today is fucked beyond belief, is San Francisco literally on fire rn?! < 1546536196 8591 :oren!~oren@ec2-18-212-11-99.compute-1.amazonaws.com PRIVMSG #esoteric :I'm getting massive packet loss and I'm pretty sure it's not our fault < 1546538396 943107 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 246 seconds < 1546538397 348803 :hexfive!~hexfive@50.35.94.36 JOIN :#esoteric < 1546539272 722258 :Sherlime!~nchambers@learnprogramming/staff/nchambers NICK :uplime < 1546540604 798998 :Phantom_Hoover!~phantomho@unaffiliated/phantom-hoover JOIN :#esoteric < 1546540905 632357 :arseniiv!~arseniiv@94.41.79.143.dynamic.ufanet.ru QUIT :Ping timeout: 250 seconds < 1546540977 128180 :arseniiv!~arseniiv@94.41.79.143.dynamic.ufanet.ru JOIN :#esoteric < 1546541730 741042 :arseniiv!~arseniiv@94.41.79.143.dynamic.ufanet.ru QUIT :Quit: gone completely :o < 1546543974 264904 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric < 1546544275 439311 :MDude!~MDude@71.50.218.48 QUIT :Quit: Going offline, see ya! (www.adiirc.com) < 1546545039 163184 :uplime!~nchambers@learnprogramming/staff/nchambers QUIT :Quit: WeeChat 2.2 < 1546545124 286896 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1546545786 838808 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1546545788 781800 :MDude!~MDude@71.50.218.48 JOIN :#esoteric < 1546545859 309879 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1546545868 285937 :MDude!~MDude@71.50.218.48 QUIT :Client Quit < 1546545975 874669 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 252 seconds < 1546546160 844572 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1546546234 70232 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1546546911 419827 :Sgeo_!~Sgeo@ool-18b98dd9.dyn.optonline.net JOIN :#esoteric < 1546547058 513249 :nfd9001!~nfd9001@c-73-157-90-101.hsd1.wa.comcast.net QUIT :Ping timeout: 244 seconds < 1546547119 647908 :Sgeo__!~Sgeo@ool-18b98dd9.dyn.optonline.net QUIT :Ping timeout: 250 seconds < 1546547933 835269 :imode!~imode@unaffiliated/imode JOIN :#esoteric < 1546548012 647615 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1546548087 51109 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1546549562 146428 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be JOIN :#esoteric < 1546549837 176870 :AnotherTest!~turingcom@ptr-82l26ze7mm4q737w3j4.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 268 seconds < 1546550054 828021 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 250 seconds < 1546550557 87401 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu JOIN :#esoteric < 1546550608 346709 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :ais523: I have a question about that reduction thing where you try to find some underload-like or 7-like thing with a limited number of elemnents < 1546550617 458055 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :I mean a limited number of possible values < 1546550645 865611 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :go on < 1546550671 551799 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :also, 7 has a similar inspiration but a rather different set of primitives < 1546550692 745494 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :@messages- < 1546550692 822474 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :oerjan said 18h 38m 41s ago: see logs for a couple errors < 1546550699 324803 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :if those values are ones like you listed, where the parenthisized ones only have one element in the parenthesis, then wouldn't that mean you can only ever have one element on the right stack (code stack), and so you can't be TC, but only as powerful as a one-stack machine? < 1546550737 716351 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :I think you need at least one value that has two things in a parenthesis < 1546550737 716425 :ais523!~ais523@unaffiliated/ais523 QUIT :Remote host closed the connection < 1546550750 950502 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1546550760 589978 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :Underload's stack elements have internal structure < 1546550779 644629 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :"PDAs are not Turing-complete" is only correct in cases where there are a finite number of possible elements in each stack slot < 1546550814 571601 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :also, I don't understand why you want underload-like in first place, when you already know small complete one-tape turing machines < 1546550815 631532 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :although in cases where you have infinitely many choices for a stack slot, the power of the language depends on which operations you have for manipulating stack elements < 1546550829 602241 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :b_jonas: remember the discussion about combinator calculus on Wang tiles a few days ago? < 1546550831 537239 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I was inspired by that < 1546550834 776200 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :yes < 1546550899 54596 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :those wang tiles are almost exactly the same as 1-D non-deterministic Cellular automaton with the neighborhood where every cell is depends on two past cells (eg. the same one in the past and the one to its left in the past) < 1546550931 4957 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :and from two-past cell cellular automata it's trivial to produce three-past-cell cellular automata < 1546550938 660411 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :it's not exacly the same because the boundary conditions differ, plus there's more than one question you can ask about the Wang tiles and more than one question you can ask about a CA, with different boundary conditions, and the two don't map nicely < 1546550954 790121 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the nondeterminism is interesting, but I don't know of any languages which are TC /because/ they're nondeterministic (maybe there is one though?) < 1546550960 5823 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :but they are basically 1-D non-deterministic CA with the alphabet and evolution rules of your choice < 1546550973 620138 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :actually, Prolog-without-recursion is I think only TC due to nondeterminism < 1546550995 398739 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :or, hmm < 1546550997 25751 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :anyway, these can emulate any 1-tape Turing machine easily, so you shouldn't feel like you're restricted to underload-like constructs < 1546551003 509774 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :/is/ it TC? < 1546551004 51474 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :haven't you done research on small Turing machines? < 1546551010 992086 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes < 1546551051 777811 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :several weeks ago I was looking into trying to make a new record for Turing machines that are universal starting from a finitely initialized tape (i.e. infinite seas of symbol 0 either side of an arbitrarily initialized section) < 1546551059 782475 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that's where https://esolangs.org/wiki/Echo_Tag came from < 1546551176 16649 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :I don't know when the nondeterminism helps in being turing-complete. obviously it can help make your program exponentially more efficient, and it can also help you reduce the alphabet a bit if you want a small machine < 1546551296 535202 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you can imagine a Prolog-alike that uses some nondeterminism implementation other than backtracking, and has no predicates; if you give it bignums and arithmetic on them, then it's TC, but wouldn't be without the nondeterminism < 1546551317 680142 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :basically for the same reason that Diophantine equations are TC < 1546551331 67587 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this doesn't seem like a very easy computational model to implement on Wang tiles, though < 1546551569 101510 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :hmm, maybe it's not exactly the same < 1546551585 3182 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :but still, you can implement a nondeterministic 1-D CA in Wang tiles < 1546551605 93764 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :they're close enough in power < 1546551753 383420 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :let's say they bitranslae with only polynomial blowup in program size < 1546551756 1886 :xkapastel!uid17782@gateway/web/irccloud.com/x-bdyispdlihwimfuo QUIT :Quit: Connection closed for inactivity < 1546551788 303023 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I think the blowup is constant, not even linear < 1546551815 404179 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oh, program size, not program speed/memory usage < 1546551826 129585 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :in that case, yes, polynomial < 1546551854 913833 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :probably quadratic? < 1546551888 507645 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :oh, and you still have only two stacks: the nondeterminism doesn't help you copy or swap or reverse or sort or merge vectors, you have to solve crossing with meticulous pairs of swapping rules for every possible pair of values on the left and right < 1546551973 638503 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :yes < 1546551987 927239 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :ais523: I care about program size. eg. see how I wrote my compilation rules to Blindfolded arithmetic such that they avoid exponentially long sequences of a=a+1 < 1546552009 490636 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you can probably get only a linear blowup via encoding data in binary as it moves < 1546552047 906893 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :mind you, it's a cellular automata, so it's parallel, so you can swap or reverse or merge vectors in linear time, not quadratic, and sort vectors in linear time in an easy way too < 1546552048 1759 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :because then the "every pair of possible values" has only 0 and 1 to consider as one of the possible pair elements < 1546552071 65536 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :sort quickly because it's nondeterministic: keep swapping then verify that it's sorted < 1546552096 441621 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the fastest known parallel sorts, even deterministic ones, are O(log n) < 1546552110 288774 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but a cellular automaton is limited by speed of light, thus is O(n) < 1546552112 276561 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :ais523: not on one tape < 1546552116 89650 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :yes, that < 1546552119 98030 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :it has a speed of light < 1546552123 258925 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :which is why it's linear < 1546552157 340966 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :it's just that the sort code gets pretty eays < 1546552234 952436 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that reminds me of https://esolangs.org/wiki/Precognition < 1546552248 165625 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I wrote some sorting code in that (although it sorted an array as it was produced, not an input array) < 1546552577 176000 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :hmm, I guess the algorithm using there is best described as quantum bogosort! < 1546552594 289488 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(it retroactively cancels out the current branch of program execution if the array isn't sorted) < 1546553231 61038 :ais523!~ais523@unaffiliated/ais523 QUIT :Quit: reloading my desktop environment < 1546553249 554269 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric < 1546553311 312465 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :I think you could start from a one-tape turing machine, or two-stack machine with finite control, and translate it to an underload program in such a way that only a finite set of values is possible. but you don't need that translation to just get a 1-D CA or Wang tiles. < 1546553368 809031 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :So in some sense, when you asked for underload with finitely many possible values, that is rather general. Of course it doesn't allow CA-like parallelism or nondeterminism, but it's not more restricted than two-stack state machines. < 1546553396 38227 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the ():^ TCness construction for Underload uses only a finite set of possible values (unsurprisingly, as you need * or a to create new values) < 1546553421 790488 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :what I was thinking more of was a construction that worked for full Underload directly (say, via string substitution) < 1546553435 247681 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :ais523: yeah, that's true < 1546553447 424963 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :um < 1546553473 162405 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you could convert ( to (), a to (a)*, : to (:)*, …, ) to *a* < 1546553477 71946 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :this is basically what 7 does < 1546553478 31895 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :just to make sure, is it still finitely different values if you want to give it input? < 1546553492 675622 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :well Underload doesn't take input < 1546553496 407565 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :yeah < 1546553504 855928 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :that's why this is a problem < 1546553511 560157 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :you need to embed the input to the program < 1546553524 28435 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but it's a counter machine construction so you could give the input by initializing one of the counters to, say, 9 to the power of the input < 1546553527 684190 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :and I don't know how that's represented in the program after the translation to ():^ < 1546553539 19898 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :after the translation, will you get all the input in a huge parenthesis? can you avoid that? < 1546553555 863638 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :even if it's a counter, that question stands < 1546553559 351057 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the translation is from a counter machine, in that case, you need to encode the input into the initial value of one of hte counters < 1546553596 229393 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :one of the counters is a string of ^ in the program < 1546553609 857070 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the length determines the counter value < 1546553634 619254 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the other counter is stored by the number of times a particular element appears on the stack, again it's repeated a number of times equal to the counter value < 1546553657 748499 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so there's no huge parenthesis involved, just a single predetermined element written multiple times < 1546553671 188857 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :ok good < 1546553706 91612 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :then you can do that too instead of translating a finite state two stack machine < 1546553710 672600 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :with input on a stack < 1546553717 935799 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :um < 1546553725 81307 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :input on the left stack < 1546553737 696718 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :that's where everything goes if you don't want the big parenthesis < 1546553740 695809 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you don't need to go via Underload at all for this though < 1546553744 754265 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :just translate the counter machine directly < 1546553748 166172 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :yes, that's what I said above < 1546553771 405725 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :in this case I think you'd probably prefer the two stack machine, though, it's more efficient < 1546553776 608008 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :in fact, a Turing machine would work even better < 1546553777 251660 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :you can translate any tape machine directly to a CA, without underload < 1546553792 731639 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :and you can even translate two stacks to a nondet CA with a host of extra rules for shifting elements away < 1546553796 234690 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :to gain space < 1546553812 507725 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :it can be done deterministically too if you want < 1546553826 712240 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :it just gets slightly bigger that way < 1546553876 631391 :sleepnap!~thomas@2603:3015:260e:1900:8319:87ab:f00:d5de PART :#esoteric < 1546555955 57122 :fungot!~fungot@2a01:4b00:82bb:1341::2 QUIT :Quit: Coyote finally caught me < 1546555976 400436 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :(There's going to be an unfortunate fungot outage for the next day or so.) < 1546556002 967821 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :oh no < 1546556090 967694 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :our hon. and learned friend fungot is entitled for a short rest once in a while < 1546556143 601668 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :disagree < 1546556338 87449 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :as long as he works 21% of all times it's fine < 1546556350 523932 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`? fungot < 1546556351 676200 :HackEso!~h@techne.zem.fi PRIVMSG #esoteric :fungot is our beloved channel mascot and voice of reason. < 1546557492 384552 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :so there's a sweet interval between --04-26 and --05-10 inclusive where it's safe to put state holidays, because it can collide with neither easter or whit sunday. that explains why --05-01 was chosen as a spring holiday with various random meanings. < 1546557556 378963 :b_jonas!~x@catv-176-63-13-156.catv.broadband.hu PRIVMSG #esoteric :mind you, you can go a few days over the edges as long as you make sure that the collision won't happen in your lifetime < 1546558422 944477 :Phantom_Hoover!~phantomho@unaffiliated/phantom-hoover QUIT :Remote host closed the connection < 1546559293 205874 :zzo38!~zzo38@24-207-47-161.eastlink.ca PRIVMSG #esoteric :I don't like the blank tiles in the Scrabble game are same on both sides. If you mark "0" on the corner then you can avoid this. < 1546559988 933715 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Remote host closed the connection