00:11:41 where your primitives are a * : ^ ! (a) (*) (:) (^) (!) <-- you only need ^ without parens, i'm sure this variant has been discussed before... 00:13:01 in the context of "underload" with only finitely many basic commands 00:15:23 oerjan: this isn't an attempt at TCness, but an attempt at implementing full Underload via string rewrites 00:15:49 not generalized string rewrites either, literal "search for all instances of string X and replace them with string Y" 00:19:26 code like (:)^ will probably need an unescaped : in the internal state at some point… 00:22:07 -!- tromp has quit (Remote host closed the connection). 00:22:56 you seem to have dropped ~ although that's theoretically expressible 00:23:00 hm very laggy 00:23:11 -!- ineiros has joined. 00:24:51 actually I've moved back towards including ~ over ^, and adding an additional primitive < which is equivalent to a*^ 00:29:07 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 00:30:29 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 00:31:16 so you can deal with highly escaped primitives by storing them internally in the (~)aa form but you still need a separate ~ primitive 00:33:09 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 00:34:06 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 00:36:19 -!- oerjan_ has joined. 00:37:01 hm 00:37:48 not sure whether to keep the webchat open or not, this connection is still horribly laggy 00:38:55 -!- oerjan_ has quit (Client Quit). 00:40:12 anyway, i don't think a PDA can swap two large sections of stack 00:41:00 this is more like a cellular automaton than a PDA, though 00:41:06 replacements don't have to happen at the rightmost end of the string 00:41:46 right. but swapping two large sections is still awkward, i'd thikn you need something simulating a counter 00:53:41 yes, I think you need that too 00:55:47 ah The Whiteboard comic asks the inevitable question 00:56:27 http://paste.debian.net/1058394/ is a potential swapping mechanism that uses a copy of the string alphabet in order to be cute. 00:56:59 (and... uh I should probably not reuse | like that in the end) 00:57:58 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 00:58:00 (I suspect this is awkward to set up) 00:58:26 uh, no extra symbols at all? 00:58:33 you need extra symbols 00:58:38 oh ok 00:58:51 (i guess it's just me, then :P) 00:58:51 but ideally I'd like to keep things fully concatenative 00:59:02 so it's basically just "Underload with a bunch of extra symbols that mean Underloadish things" 00:59:07 like < for example 00:59:47 http://nethack4.org/pastebin/20.txt 00:59:53 probably contains mistakes 01:01:15 x and y are placeholders for any Underload primitive; | is the counter (and the only not-fully-concatenative primitive); [x] is equivalent to (x)~ 01:01:56 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) 01:07:58 you can't really do S as a side effect in a parallel string rewriting regime... 01:08:26 you need to collect them until the end, or the like 01:09:05 yes, collect them at the left end I think 01:09:18 but maybe you can make things simpler by adopting a leftmost strategy 01:10:47 (and I suspect it's still hard enough *with* such concessions) 01:13:57 (I write "I suspect" because Underload is a language I've avoided looking into so far.) 01:18:10 this makes my head hurt. maybe later. 01:23:45 int-e: the problem is that Underload's "natural" evaluation order is outermost, with leftmost as a tiebreak 01:24:07 if you go purely leftmost, programs like ((:^):^)! which should be no-ops will get stuck in an infinit eloop 01:24:25 but "outermost" is hard to define in a pure string rewriter 01:28:46 well you aren't putting inner levels explicitly in this syntax, so they shouldn't match anyway 01:30:07 in this syntax it'd be (:)(^)*a(:)*(^)*!, so yes, no match 01:33:20 -!- imode has joined. 02:04:58 -!- tromp has joined. 02:07:39 my internet connection sucks today :( 02:32:01 -!- ais523 has quit (Quit: quit). 02:40:29 *S should be [S] a~ should be [~[a]< 02:44:33 argh stipud lag 02:44:41 ~[a]< 02:46:11 @tell ais523 see logs for a couple errors 02:46:11 Consider it noted. 03:13:41 -!- oerjan has quit (Quit: Lost terminal). 03:14:15 -!- oerjan has joined. 03:15:29 -!- Essadon has quit (Quit: Qutting). 03:15:33 silly me, killed the wrong tmux process 03:19:11 * oerjan restarted the router to see if it helps connection - nah. 03:45:33 -!- FreeFull has quit. 03:48:16 -!- Lord_of_Life has quit (Ping timeout: 272 seconds). 03:48:21 -!- Lord_of_Life_ has joined. 03:49:30 -!- Lord_of_Life_ has changed nick to Lord_of_Life. 04:52:11 -!- Cale has quit (Ping timeout: 260 seconds). 04:59:27 OAOA 05:01:08 OB>_< 05:01:52 i'm so lagged tmux misinterpreted my arrow keys 05:05:05 -!- Cale has joined. 05:16:26 -!- Sgeo__ has joined. 05:19:36 -!- Sgeo_ has quit (Ping timeout: 250 seconds). 05:36:49 -!- Sgeo_ has joined. 05:40:02 -!- Sgeo__ has quit (Ping timeout: 246 seconds). 06:00:46 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. 06:04:06 OK, do you have a detail? 06:05:42 not particularly. the dream didn't include the method. 06:07:35 OK 06:07:44 Now you should try to make up the method. 07:28:05 -!- arseniiv has joined. 07:36:23 -!- oerjan has quit (Quit: Nite). 07:52:51 -!- tromp has quit (Remote host closed the connection). 07:53:05 -!- tromp has joined. 08:39:00 -!- uplime has quit (Quit: WeeChat 2.2). 09:52:36 -!- imode has quit (Ping timeout: 250 seconds). 10:04:39 -!- AnotherTest has joined. 10:08:57 -!- AnotherTest has quit (Ping timeout: 252 seconds). 10:49:41 -!- myname has joined. 11:11:57 -!- AnotherTest has joined. 11:26:41 -!- AnotherTest has quit (Ping timeout: 250 seconds). 11:55:05 -!- wob_jonas has joined. 11:55:22 ais523: or you could implement a small one-tape turing machine instead 11:55:51 postfix Underload => isn't 7 trying to be that? 12:07:07 -!- AnotherTest has joined. 12:11:19 -!- AnotherTest has quit (Ping timeout: 250 seconds). 12:20:05 -!- arseniiv has quit (Ping timeout: 246 seconds). 12:39:01 -!- Sgeo_ has quit (Read error: Connection reset by peer). 12:39:25 -!- Sgeo_ has joined. 12:53:12 -!- Essadon has joined. 12:53:35 -!- Essadon has quit (Max SendQ exceeded). 13:28:39 -!- xkapastel has quit (Quit: Connection closed for inactivity). 13:49:06 -!- Sgeo has joined. 13:53:06 -!- Sgeo_ has quit (Ping timeout: 250 seconds). 14:17:12 -!- AnotherTest has joined. 14:21:45 -!- AnotherTest has quit (Ping timeout: 250 seconds). 14:55:06 -!- xkapastel has joined. 15:02:46 -!- uplime has joined. 15:45:18 -!- Lord_of_Life_ has joined. 15:48:32 -!- sleepnap has joined. 15:49:00 -!- Lord_of_Life has quit (Ping timeout: 272 seconds). 15:49:01 -!- Lord_of_Life_ has changed nick to Lord_of_Life. 15:55:08 -!- AnotherTest has joined. 16:03:49 -!- arseniiv has joined. 16:17:39 -!- imode has joined. 16:39:43 -!- uplime has changed nick to Sherlocklime. 16:45:50 -!- Sgeo_ has joined. 16:46:34 `ysaclist 83 16:46:35 ysaclist 83: boily shachaf 16:49:31 -!- Sgeo has quit (Ping timeout: 250 seconds). 16:51:40 -!- Sherlocklime has changed nick to Sherlime. 16:59:18 -!- wob_jonas has quit (Quit: http://www.kiwiirc.com/ - A hand crafted IRC client). 17:04:30 -!- Sgeo__ has joined. 17:07:27 -!- Sgeo_ has quit (Ping timeout: 240 seconds). 17:22:01 god the internet at work today is fucked beyond belief, is San Francisco literally on fire rn?! 17:23:16 I'm getting massive packet loss and I'm pretty sure it's not our fault 17:59:56 -!- imode has quit (Ping timeout: 246 seconds). 17:59:57 -!- hexfive has joined. 18:14:32 -!- Sherlime has changed nick to uplime. 18:36:44 -!- Phantom_Hoover has joined. 18:41:45 -!- arseniiv has quit (Ping timeout: 250 seconds). 18:42:57 -!- arseniiv has joined. 18:55:30 -!- arseniiv has quit (Quit: gone completely :o). 19:32:54 -!- FreeFull has joined. 19:37:55 -!- MDude has quit (Quit: Going offline, see ya! (www.adiirc.com)). 19:50:39 -!- uplime has quit (Quit: WeeChat 2.2). 19:52:04 -!- ais523 has joined. 20:03:06 -!- ais523 has quit (Remote host closed the connection). 20:03:08 -!- MDude has joined. 20:04:19 -!- ais523 has joined. 20:04:28 -!- MDude has quit (Client Quit). 20:06:15 -!- AnotherTest has quit (Ping timeout: 252 seconds). 20:09:20 -!- ais523 has quit (Remote host closed the connection). 20:10:34 -!- ais523 has joined. 20:21:51 -!- Sgeo_ has joined. 20:24:18 -!- nfd9001 has quit (Ping timeout: 244 seconds). 20:25:19 -!- Sgeo__ has quit (Ping timeout: 250 seconds). 20:38:53 -!- imode has joined. 20:40:12 -!- ais523 has quit (Remote host closed the connection). 20:41:27 -!- ais523 has joined. 21:06:02 -!- AnotherTest has joined. 21:10:37 -!- AnotherTest has quit (Ping timeout: 268 seconds). 21:14:14 -!- imode has quit (Ping timeout: 250 seconds). 21:22:37 -!- b_jonas has joined. 21:23:28 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 21:23:37 I mean a limited number of possible values 21:24:05 go on 21:24:31 also, 7 has a similar inspiration but a rather different set of primitives 21:24:52 @messages- 21:24:52 oerjan said 18h 38m 41s ago: see logs for a couple errors 21:24:59 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? 21:25:37 I think you need at least one value that has two things in a parenthesis 21:25:37 -!- ais523 has quit (Remote host closed the connection). 21:25:50 -!- ais523 has joined. 21:26:00 Underload's stack elements have internal structure 21:26:19 "PDAs are not Turing-complete" is only correct in cases where there are a finite number of possible elements in each stack slot 21:26:54 also, I don't understand why you want underload-like in first place, when you already know small complete one-tape turing machines 21:26:55 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 21:27:09 b_jonas: remember the discussion about combinator calculus on Wang tiles a few days ago? 21:27:11 I was inspired by that 21:27:14 yes 21:28:19 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) 21:28:51 and from two-past cell cellular automata it's trivial to produce three-past-cell cellular automata 21:28:58 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 21:29:14 the nondeterminism is interesting, but I don't know of any languages which are TC /because/ they're nondeterministic (maybe there is one though?) 21:29:20 but they are basically 1-D non-deterministic CA with the alphabet and evolution rules of your choice 21:29:33 actually, Prolog-without-recursion is I think only TC due to nondeterminism 21:29:55 or, hmm 21:29:57 anyway, these can emulate any 1-tape Turing machine easily, so you shouldn't feel like you're restricted to underload-like constructs 21:30:03 /is/ it TC? 21:30:04 haven't you done research on small Turing machines? 21:30:10 yes 21:30:51 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) 21:30:59 that's where https://esolangs.org/wiki/Echo_Tag came from 21:32:56 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 21:34:56 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 21:35:17 basically for the same reason that Diophantine equations are TC 21:35:31 this doesn't seem like a very easy computational model to implement on Wang tiles, though 21:39:29 hmm, maybe it's not exactly the same 21:39:45 but still, you can implement a nondeterministic 1-D CA in Wang tiles 21:40:05 they're close enough in power 21:42:33 let's say they bitranslae with only polynomial blowup in program size 21:42:36 -!- xkapastel has quit (Quit: Connection closed for inactivity). 21:43:08 I think the blowup is constant, not even linear 21:43:35 oh, program size, not program speed/memory usage 21:43:46 in that case, yes, polynomial 21:44:14 probably quadratic? 21:44:48 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 21:46:13 yes 21:46:27 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 21:46:49 you can probably get only a linear blowup via encoding data in binary as it moves 21:47:27 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 21:47:28 because then the "every pair of possible values" has only 0 and 1 to consider as one of the possible pair elements 21:47:51 sort quickly because it's nondeterministic: keep swapping then verify that it's sorted 21:48:16 the fastest known parallel sorts, even deterministic ones, are O(log n) 21:48:30 but a cellular automaton is limited by speed of light, thus is O(n) 21:48:32 ais523: not on one tape 21:48:36 yes, that 21:48:39 it has a speed of light 21:48:43 which is why it's linear 21:49:17 it's just that the sort code gets pretty eays 21:50:34 that reminds me of https://esolangs.org/wiki/Precognition 21:50:48 I wrote some sorting code in that (although it sorted an array as it was produced, not an input array) 21:56:17 hmm, I guess the algorithm using there is best described as quantum bogosort! 21:56:34 (it retroactively cancels out the current branch of program execution if the array isn't sorted) 22:07:11 -!- ais523 has quit (Quit: reloading my desktop environment). 22:07:29 -!- ais523 has joined. 22:08:31 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. 22:09:28 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. 22:09:56 the ():^ TCness construction for Underload uses only a finite set of possible values (unsurprisingly, as you need * or a to create new values) 22:10:21 what I was thinking more of was a construction that worked for full Underload directly (say, via string substitution) 22:10:35 ais523: yeah, that's true 22:10:47 um 22:11:13 you could convert ( to (), a to (a)*, : to (:)*, …, ) to *a* 22:11:17 this is basically what 7 does 22:11:18 just to make sure, is it still finitely different values if you want to give it input? 22:11:32 well Underload doesn't take input 22:11:36 yeah 22:11:44 that's why this is a problem 22:11:51 you need to embed the input to the program 22:12:04 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 22:12:07 and I don't know how that's represented in the program after the translation to ():^ 22:12:19 after the translation, will you get all the input in a huge parenthesis? can you avoid that? 22:12:35 even if it's a counter, that question stands 22:12:39 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 22:13:16 one of the counters is a string of ^ in the program 22:13:29 the length determines the counter value 22:13:54 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 22:14:17 so there's no huge parenthesis involved, just a single predetermined element written multiple times 22:14:31 ok good 22:15:06 then you can do that too instead of translating a finite state two stack machine 22:15:10 with input on a stack 22:15:17 um 22:15:25 input on the left stack 22:15:37 that's where everything goes if you don't want the big parenthesis 22:15:40 you don't need to go via Underload at all for this though 22:15:44 just translate the counter machine directly 22:15:48 yes, that's what I said above 22:16:11 in this case I think you'd probably prefer the two stack machine, though, it's more efficient 22:16:16 in fact, a Turing machine would work even better 22:16:17 you can translate any tape machine directly to a CA, without underload 22:16:32 and you can even translate two stacks to a nondet CA with a host of extra rules for shifting elements away 22:16:36 to gain space 22:16:52 it can be done deterministically too if you want 22:17:06 it just gets slightly bigger that way 22:17:56 -!- sleepnap has left. 22:52:35 -!- fungot has quit (Quit: Coyote finally caught me). 22:52:56 (There's going to be an unfortunate fungot outage for the next day or so.) 22:53:22 oh no 22:54:50 our hon. and learned friend fungot is entitled for a short rest once in a while 22:55:43 disagree 22:58:58 as long as he works 21% of all times it's fine 22:59:10 `? fungot 22:59:11 fungot is our beloved channel mascot and voice of reason. 23:18:12 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. 23:19:16 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 23:33:42 -!- Phantom_Hoover has quit (Remote host closed the connection). 23:48:13 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. 23:59:48 -!- tromp has quit (Remote host closed the connection).