←2019-01-02 2019-01-03 2019-01-04→ ↑2019 ↑all
00:11:41 <oerjan> <ais523> where your primitives are a * : ^ ! (a) (*) (:) (^) (!) <-- you only need ^ without parens, i'm sure this variant has been discussed before...
00:13:01 <oerjan> in the context of "underload" with only finitely many basic commands
00:15:23 <ais523> oerjan: this isn't an attempt at TCness, but an attempt at implementing full Underload via string rewrites
00:15:49 <ais523> not generalized string rewrites either, literal "search for all instances of string X and replace them with string Y"
00:19:26 <ais523> 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 <oerjan> you seem to have dropped ~ although that's theoretically expressible
00:23:00 <oerjan> hm very laggy
00:23:11 -!- ineiros has joined.
00:24:51 <ais523> actually I've moved back towards including ~ over ^, and adding an additional primitive < which is equivalent to a*^
00:29:07 <ais523> 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 <ais523> 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 <ais523> 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 <oerjan> 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 <ais523> 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 <oerjan> hm
00:37:48 <oerjan> 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 <oerjan> anyway, i don't think a PDA can swap two large sections of stack
00:41:00 <ais523> this is more like a cellular automaton than a PDA, though
00:41:06 <ais523> replacements don't have to happen at the rightmost end of the string
00:41:46 <oerjan> right. but swapping two large sections is still awkward, i'd thikn you need something simulating a counter
00:53:41 <ais523> yes, I think you need that too
00:55:47 <oerjan> ah The Whiteboard comic asks the inevitable question
00:56:27 <int-e> 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 <int-e> (and... uh I should probably not reuse | like that in the end)
00:57:58 <oerjan> 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 <int-e> (I suspect this is awkward to set up)
00:58:26 <int-e> uh, no extra symbols at all?
00:58:33 <ais523> you need extra symbols
00:58:38 <oerjan> oh ok
00:58:51 <oerjan> (i guess it's just me, then :P)
00:58:51 <ais523> but ideally I'd like to keep things fully concatenative
00:59:02 <ais523> so it's basically just "Underload with a bunch of extra symbols that mean Underloadish things"
00:59:07 <ais523> like < for example
00:59:47 <ais523> http://nethack4.org/pastebin/20.txt
00:59:53 <ais523> probably contains mistakes
01:01:15 <ais523> 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 <ais523> 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 <oerjan> you can't really do S as a side effect in a parallel string rewriting regime...
01:08:26 <oerjan> you need to collect them until the end, or the like
01:09:05 <ais523> yes, collect them at the left end I think
01:09:18 <int-e> but maybe you can make things simpler by adopting a leftmost strategy
01:10:47 <int-e> (and I suspect it's still hard enough *with* such concessions)
01:13:57 <int-e> (I write "I suspect" because Underload is a language I've avoided looking into so far.)
01:18:10 <oerjan> this makes my head hurt. maybe later.
01:23:45 <ais523> int-e: the problem is that Underload's "natural" evaluation order is outermost, with leftmost as a tiebreak
01:24:07 <ais523> if you go purely leftmost, programs like ((:^):^)! which should be no-ops will get stuck in an infinit eloop
01:24:25 <ais523> but "outermost" is hard to define in a pure string rewriter
01:28:46 <oerjan> well you aren't putting inner levels explicitly in this syntax, so they shouldn't match anyway
01:30:07 <ais523> 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 <oerjan> my internet connection sucks today :(
02:32:01 -!- ais523 has quit (Quit: quit).
02:40:29 <oerjan> *S should be [S]<S, i think
02:44:22 <oerjan> a~ should be [~[a]<
02:44:33 <oerjan> argh stipud lag
02:44:41 <oerjan> ~[a]<
02:46:11 <oerjan> @tell ais523 see logs for a couple errors
02:46:11 <lambdabot> 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 <oerjan> 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 <oerjan> OAOA
05:01:08 <oerjan> OB>_<
05:01:52 <oerjan> 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 <imode> 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 <zzo38> OK, do you have a detail?
06:05:42 <imode> not particularly. the dream didn't include the method.
06:07:35 <zzo38> OK
06:07:44 <zzo38> 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 <wob_jonas> ais523: or you could implement a small one-tape turing machine instead
11:55:51 <wob_jonas> 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 <shachaf> `ysaclist 83
16:46:35 <HackEso> 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 <oren> god the internet at work today is fucked beyond belief, is San Francisco literally on fire rn?!
17:23:16 <oren> 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 <b_jonas> 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 <b_jonas> I mean a limited number of possible values
21:24:05 <ais523> go on
21:24:31 <ais523> also, 7 has a similar inspiration but a rather different set of primitives
21:24:52 <ais523> @messages-
21:24:52 <lambdabot> oerjan said 18h 38m 41s ago: see logs for a couple errors
21:24:59 <b_jonas> 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 <b_jonas> 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 <ais523> Underload's stack elements have internal structure
21:26:19 <ais523> "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 <b_jonas> 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 <ais523> 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 <ais523> b_jonas: remember the discussion about combinator calculus on Wang tiles a few days ago?
21:27:11 <ais523> I was inspired by that
21:27:14 <b_jonas> yes
21:28:19 <b_jonas> 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 <ais523> and from two-past cell cellular automata it's trivial to produce three-past-cell cellular automata
21:28:58 <b_jonas> 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 <ais523> 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 <b_jonas> but they are basically 1-D non-deterministic CA with the alphabet and evolution rules of your choice
21:29:33 <ais523> actually, Prolog-without-recursion is I think only TC due to nondeterminism
21:29:55 <ais523> or, hmm
21:29:57 <b_jonas> 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 <ais523> /is/ it TC?
21:30:04 <b_jonas> haven't you done research on small Turing machines?
21:30:10 <ais523> yes
21:30:51 <ais523> 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 <ais523> that's where https://esolangs.org/wiki/Echo_Tag came from
21:32:56 <b_jonas> 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 <ais523> 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 <ais523> basically for the same reason that Diophantine equations are TC
21:35:31 <ais523> this doesn't seem like a very easy computational model to implement on Wang tiles, though
21:39:29 <b_jonas> hmm, maybe it's not exactly the same
21:39:45 <b_jonas> but still, you can implement a nondeterministic 1-D CA in Wang tiles
21:40:05 <b_jonas> they're close enough in power
21:42:33 <b_jonas> 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 <ais523> I think the blowup is constant, not even linear
21:43:35 <ais523> oh, program size, not program speed/memory usage
21:43:46 <ais523> in that case, yes, polynomial
21:44:14 <ais523> probably quadratic?
21:44:48 <b_jonas> 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 <ais523> yes
21:46:27 <b_jonas> 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 <ais523> you can probably get only a linear blowup via encoding data in binary as it moves
21:47:27 <b_jonas> 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 <ais523> 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 <b_jonas> sort quickly because it's nondeterministic: keep swapping then verify that it's sorted
21:48:16 <ais523> the fastest known parallel sorts, even deterministic ones, are O(log n)
21:48:30 <ais523> but a cellular automaton is limited by speed of light, thus is O(n)
21:48:32 <b_jonas> ais523: not on one tape
21:48:36 <b_jonas> yes, that
21:48:39 <b_jonas> it has a speed of light
21:48:43 <b_jonas> which is why it's linear
21:49:17 <b_jonas> it's just that the sort code gets pretty eays
21:50:34 <ais523> that reminds me of https://esolangs.org/wiki/Precognition
21:50:48 <ais523> I wrote some sorting code in that (although it sorted an array as it was produced, not an input array)
21:56:17 <ais523> hmm, I guess the algorithm using there is best described as quantum bogosort!
21:56:34 <ais523> (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 <b_jonas> 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 <b_jonas> 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 <ais523> 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 <ais523> what I was thinking more of was a construction that worked for full Underload directly (say, via string substitution)
22:10:35 <b_jonas> ais523: yeah, that's true
22:10:47 <b_jonas> um
22:11:13 <ais523> you could convert ( to (), a to (a)*, : to (:)*, …, ) to *a*
22:11:17 <ais523> this is basically what 7 does
22:11:18 <b_jonas> just to make sure, is it still finitely different values if you want to give it input?
22:11:32 <ais523> well Underload doesn't take input
22:11:36 <b_jonas> yeah
22:11:44 <b_jonas> that's why this is a problem
22:11:51 <b_jonas> you need to embed the input to the program
22:12:04 <ais523> 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 <b_jonas> and I don't know how that's represented in the program after the translation to ():^
22:12:19 <b_jonas> after the translation, will you get all the input in a huge parenthesis? can you avoid that?
22:12:35 <b_jonas> even if it's a counter, that question stands
22:12:39 <ais523> 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 <ais523> one of the counters is a string of ^ in the program
22:13:29 <ais523> the length determines the counter value
22:13:54 <ais523> 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 <ais523> so there's no huge parenthesis involved, just a single predetermined element written multiple times
22:14:31 <b_jonas> ok good
22:15:06 <b_jonas> then you can do that too instead of translating a finite state two stack machine
22:15:10 <b_jonas> with input on a stack
22:15:17 <b_jonas> um
22:15:25 <b_jonas> input on the left stack
22:15:37 <b_jonas> that's where everything goes if you don't want the big parenthesis
22:15:40 <ais523> you don't need to go via Underload at all for this though
22:15:44 <ais523> just translate the counter machine directly
22:15:48 <b_jonas> yes, that's what I said above
22:16:11 <ais523> in this case I think you'd probably prefer the two stack machine, though, it's more efficient
22:16:16 <ais523> in fact, a Turing machine would work even better
22:16:17 <b_jonas> you can translate any tape machine directly to a CA, without underload
22:16:32 <b_jonas> and you can even translate two stacks to a nondet CA with a host of extra rules for shifting elements away
22:16:36 <b_jonas> to gain space
22:16:52 <b_jonas> it can be done deterministically too if you want
22:17:06 <b_jonas> 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 <fizzie> (There's going to be an unfortunate fungot outage for the next day or so.)
22:53:22 <shachaf> oh no
22:54:50 <b_jonas> our hon. and learned friend fungot is entitled for a short rest once in a while
22:55:43 <shachaf> disagree
22:58:58 <b_jonas> as long as he works 21% of all times it's fine
22:59:10 <shachaf> `? fungot
22:59:11 <HackEso> fungot is our beloved channel mascot and voice of reason.
23:18:12 <b_jonas> 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 <b_jonas> 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 <zzo38> 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).
←2019-01-02 2019-01-03 2019-01-04→ ↑2019 ↑all