00:13:42 <esolangs> [[Trianguish]] N https://esolangs.org/w/index.php?oldid=117278 * Ais523 * (+34807) documenting someone else's language + TCness proof
00:46:10 -!- Lord_of_Life_ has joined.
00:46:13 -!- Lord_of_Life has quit (Ping timeout: 255 seconds).
00:47:30 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
00:56:39 -!- A_Dragon has changed nick to DemonDerg.
01:31:27 <esolangs> [[Language list]] https://esolangs.org/w/index.php?diff=117279&oldid=117183 * Ais523 * (+17) /* T */ +[[Trianguish]]
02:10:55 <esolangs> [[A Queue which can't grow]] https://esolangs.org/w/index.php?diff=117280&oldid=113346 * Kaveh Yousefi * (+279) Introduced an examples section comprehending two initial members, one being a counter, the other an adder.
02:12:53 <esolangs> [[A Queue which can't grow]] https://esolangs.org/w/index.php?diff=117281&oldid=117280 * Kaveh Yousefi * (+205) Added a hyperlink to my implementation of the A Queue which can't grow language on GitHub and changed the category tag Unimplemented to Implemented.
04:23:41 <esolangs> [[Pairpointing]] https://esolangs.org/w/index.php?diff=117282&oldid=117211 * Fazaazafg * (+1760) /* Examples */
04:24:55 <esolangs> [[Pairpointing]] https://esolangs.org/w/index.php?diff=117283&oldid=117282 * Fazaazafg * (-9) /* Examples */
04:37:27 <esolangs> [[99 bottles of beer]] https://esolangs.org/w/index.php?diff=117284&oldid=116320 * Fazaazafg * (+1763) /* List of implementations */
04:38:47 <esolangs> [[Pairpointing]] https://esolangs.org/w/index.php?diff=117285&oldid=117283 * Fazaazafg * (-8)
04:44:11 -!- razetime has joined.
04:44:17 -!- ais523 has quit (Quit: quit).
04:51:02 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=117286&oldid=117214 * BoundedBeans * (+18)
04:51:35 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=117287&oldid=117286 * BoundedBeans * (-18)
05:16:23 <esolangs> [[Omam]] M https://esolangs.org/w/index.php?diff=117288&oldid=66990 * PythonshellDebugwindow * (+155) /* Implementation */ Categories
05:19:08 <esolangs> [[FunctionsFTW/Cat]] M https://esolangs.org/w/index.php?diff=117289&oldid=108711 * PythonshellDebugwindow * (+23) Back
05:50:55 -!- razetime has quit (Remote host closed the connection).
05:51:21 -!- razetime has joined.
06:06:53 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=117290&oldid=117287 * Esolanger12345 * (-1)
06:06:56 -!- razetime has quit (Ping timeout: 255 seconds).
06:16:00 -!- razetime has joined.
07:13:37 -!- tromp has joined.
07:37:32 -!- tromp has quit (Read error: Connection reset by peer).
07:39:33 -!- cpressey has joined.
07:45:48 <esolangs> [[Talk:Broken Calculator]] M https://esolangs.org/w/index.php?diff=117291&oldid=117174 * Europe2048 * (+32)
08:03:55 <cpressey> I have an idea for how to help ensure that grammars in my formalism describe CSLs. Every time a symbol is consumed from input, accumulate some fixed amount of "fuel". Every time new storage is allocated, expend some fixed amount of "fuel". --> The storage used is proportional to the length of the input.
08:08:10 <cpressey> http://esolangs.org/wiki/Linear_bounded_automaton
08:15:06 -!- razetime has quit (Ping timeout: 272 seconds).
09:34:48 <esolangs> [[A Queue which can't grow]] https://esolangs.org/w/index.php?diff=117292&oldid=117281 * Kaveh Yousefi * (+65) Added further page categories and amended a few orthographic mistakes.
09:35:33 <cpressey> There's a sort of Buridan's-ass problem with having a wide range of interests: you can't focus on any one interest enough to do anything significant with it, without neglecting all the other interests.
10:08:08 -!- Sgeo has quit (Read error: Connection reset by peer).
10:14:20 <esolangs> [[Category:Sandies]] N https://esolangs.org/w/index.php?oldid=117293 * Lilchiky * (+0) Created blank page
10:15:38 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=117294&oldid=117290 * Lilchiky * (+22)
10:17:06 <esolangs> [[Category:Sandies]] M https://esolangs.org/w/index.php?diff=117295&oldid=117293 * Lilchiky * (+26)
10:24:30 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=117296&oldid=117294 * Lilchiky * (+120)
10:26:47 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=117297&oldid=117296 * Lilchiky * (+36) /* you can't see me */
10:31:09 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=117298&oldid=117297 * Lilchiky * (+104) /* i is ghost */
10:34:24 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=117299&oldid=117298 * Lilchiky * (+15) /* ghost */
10:40:50 -!- raz3time has joined.
10:41:25 -!- raz3time has quit (Client Quit).
11:49:16 -!- Koen has joined.
12:12:27 <esolangs> [[Chicken]] M https://esolangs.org/w/index.php?diff=117300&oldid=117269 * None1 * (+9) /* undefined */
12:44:49 <esolangs> [[Template:Wrongname]] N https://esolangs.org/w/index.php?oldid=117301 * Lilchiky * (+155) /* this is a joke, just like Template:Sus */
12:46:08 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=117302&oldid=117299 * Lilchiky * (+33)
12:48:33 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=117303&oldid=117302 * Lilchiky * (+5) /* Play Area (Don't clear after use!) */
12:49:38 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=117304&oldid=117303 * Lilchiky * (+52) /* (The Limit)+1 */
13:11:45 -!- arseniiv has joined.
14:17:11 -!- arseniiv_ has joined.
14:21:19 -!- arseniiv has quit (Ping timeout: 264 seconds).
14:31:12 <esolangs> [[Bawkbawk]] M https://esolangs.org/w/index.php?diff=117305&oldid=117257 * Lilchiky * (+116) Truth machine gets an upgrade!
14:31:44 <esolangs> [[Bawkbawk]] M https://esolangs.org/w/index.php?diff=117306&oldid=117305 * Lilchiky * (+2) Adding some appropriate bullet points
14:32:06 <esolangs> [[Bawkbawk]] M https://esolangs.org/w/index.php?diff=117307&oldid=117306 * Lilchiky * (-1) bullet point went wrong
14:32:23 <esolangs> [[Bawkbawk]] M https://esolangs.org/w/index.php?diff=117308&oldid=117307 * Lilchiky * (+1) went wrong again
14:35:21 <esolangs> [[Bawkbawk]] M https://esolangs.org/w/index.php?diff=117309&oldid=117308 * Lilchiky * (+0) /* again */
14:36:42 <esolangs> [[Truth-machine]] M https://esolangs.org/w/index.php?diff=117310&oldid=117225 * Lilchiky * (+7) /* Bawkbawk */
14:37:09 <esolangs> [[Bawkbawk]] M https://esolangs.org/w/index.php?diff=117311&oldid=117309 * Lilchiky * (+2) /* missing one character */
14:44:03 -!- ais523 has joined.
15:00:31 -!- razetime has joined.
15:00:53 -!- cpressey has quit (Quit: Client closed).
15:35:54 <ais523> an observation I made recently: the primary difference between https://esolangs.org/wiki/Spiral_Rise and a tag system is that tag systems push onto the end of the queue, whereas Spiral Rise pushes onto a known location that might be before or after the end of the queue
15:36:41 <ais523> apart from that, it's basically just Genera Tag where all the symbols have the same production map, but can have different widths (not quite the same because the way the position wraps is different)
15:37:51 <ais523> meanwhile, Genera Tag with all the productions padded to the same length has the same behaviour for the end of the queue – the queue length increases by a constant on every step, so you can find the location to push to via just increasing the location by a constant (as in Spiral Rise) rather than looking for where the end of the queue is
15:39:22 <ais523> so, the question: is Genera Tag Turing-complete under the restrictions that a) all symbols have the same production map, differing only in width; b) that map maps all positions but 0 to the same single symbol, with the production for 0 being different?
15:39:46 <ais523> the resulting language is basically the common subset of Genera Tag and Spiral Rise, which is really interesting to me because I didn't even realise those languages had a common subset until just now
15:41:39 <ais523> fwiw, this is making me think of a generalisation of Spiral Rise where productions can move the "tail of the queue" pointer a different distance from the amount that they write to that pointer
15:43:31 <ais523> and if you write onto the same cell twice, the symbols "add" in some sense (at least obeying the rule 0 + x = x)
15:43:52 <ais523> * a generalisation of Genera Tag
15:43:54 <ais523> although I guess it's both
15:48:31 -!- razetime has quit (Quit: Go back to your cringe 9 to 5. I'll be gaming.).
15:56:31 <esolangs> [[Prime numbers generator]] M https://esolangs.org/w/index.php?diff=117312&oldid=97085 * PythonshellDebugwindow * (+9) Stub
15:58:40 <esolangs> [[Meta Memes]] M https://esolangs.org/w/index.php?diff=117313&oldid=96948 * PythonshellDebugwindow * (+24) Category
16:07:18 -!- Koen has quit (Remote host closed the connection).
16:10:41 -!- Koen has joined.
16:31:34 -!- tromp has joined.
16:33:16 -!- ais523 has quit (Ping timeout: 248 seconds).
16:50:01 -!- Thelie has joined.
17:13:51 -!- ais523 has joined.
17:15:15 -!- cpressey has joined.
17:28:33 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
17:31:07 -!- tromp has joined.
17:53:36 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
18:30:58 -!- tromp has joined.
18:52:04 -!- Thelie has quit (Remote host closed the connection).
18:52:11 <esolangs> [[Special:Log/newusers]] create * WaywardFractal * New user account
19:03:27 <esolangs> [[Esolang:Introduce yourself]] M https://esolangs.org/w/index.php?diff=117314&oldid=117151 * WaywardFractal * (+102) Said hi
19:05:24 <cpressey> Showing that some given thing is Turing-complete (or more generally foo-complete) is a common activity in this community.
19:09:33 <ais523> I find TCness proofs to be a good way to improve the language that you're compiling from / interpreting in order to prove the TCnes
19:10:08 <ais523> if you have a lot of proofs of languages A, B, C, etc. by compiling from X, you can then look at your implementations of X in A, B, C, and think, what other languages could I also implement using these same implementations?
19:10:30 <ais523> and is there a change to X that would simplify all the original programs, and would X still be TC after that change?
19:11:15 <ais523> and then maybe you come up with Y, which is an improved version of X, in that it has more power in ways that don't make it harder to implement, and is easier to implement in ways that don't make it less powerful
19:18:00 <esolangs> [[Deadfish++]] M https://esolangs.org/w/index.php?diff=117315&oldid=117262 * Europe2048 * (+1)
19:43:27 <esolangs> [[NASAL]] https://esolangs.org/w/index.php?diff=117316&oldid=109306 * Kaveh Yousefi * (+614) Added a hyperlink to my implementation of the NASAL programming language on GitHub and supplemented two page category tags.
19:46:01 <esolangs> [[NASAL]] https://esolangs.org/w/index.php?diff=117317&oldid=117316 * Kaveh Yousefi * (+368) Introduced an examples section comprehending two initial members: one demonstrating the while loop in conjunction with the pop operation, the other the same iterative facility with rearrangements.
19:48:46 <esolangs> [[NASAL]] https://esolangs.org/w/index.php?diff=117318&oldid=117317 * Kaveh Yousefi * (+0) Rectified the BitBrain equivalency entry for the start of the program, as the same lacked the zero-valued integer argument and instead employed m instructions.
19:56:30 -!- arseniiv_ has quit (Quit: gone too far).
20:08:45 -!- Sgeo has joined.
20:49:38 <esolangs> [[The Waterfall Model]] https://esolangs.org/w/index.php?diff=117319&oldid=115309 * Ais523 * (+207) add See also section, and a little discussion of the Flooding variant
20:54:08 <cpressey> I was thinking that most of these proofs are bisimulation proofs, or rather compiler correctness proofs. You have the language of foo, you have a compiler from foo to bar (call it foobar), and you show that, for all x, foo(x) ~ bar(foobar(x)). Where ~ means "equivalent to" and includes non-termination.
20:55:11 <cpressey> I was going to say "language of Turing machines" instead of "language of foo", but I think in practice there are very few TCness proof that refer directly to Turing machines. I think most go back to a language that has already been established to be Turing-complete.
20:55:30 <b_jonas> I don't see why you'd want foo(x) ~ bar(foobar(x)) directly
20:55:41 <ais523> the most recent proof where I did Turing machines directly was https://esolangs.org/wiki/Addition_Automaton and that was only because it was trivially easy
20:56:26 <ais523> Turing machines are unnatural in a way because they move along a tape but have to eject the same amount of tape on one side that they consume on the other
20:56:47 <ais523> which means that you can't store arbitrary data in arbitrary parts of the tape, you have to go all the way to the end to find new memory to write to
20:57:28 <ais523> I agree with cpressey that the way you formalise an "X is TC" proof is to prove that Y is TC and to prove that a compiler from Y to X is correct
20:57:33 <b_jonas> usually you instead naturally simulate two stacks
20:58:02 <ais523> I am increasingly coming to believe that tarpits basically fall into two categories, queue machines and counter machines
20:58:10 <ais523> and anything else is insufficiently restrictive to be a tarpit
20:58:45 <b_jonas> the Blindfolded arithmetic proof naturally gives you three stacks; two different Consumer Society proofs give you two stacks directly (though you can go faster than with a two-stack machine, which is why Consumer Society is more of a language of my style than the tarpits)
20:59:14 <ais523> the two-variable blindfolded arithmetic proof is a counter machine rather than stack machine
21:00:07 <ais523> it only gets one number to store data in because the other is needed as a temporary, so it uses the "product of prime powers" technique to store arbitrarily many counters (and from there I implemented The Waterfall Model, which in this context is basically a special case of FRACTRAN)
21:00:52 <ais523> the speed question has been intriguing me to some extent: it's why I created https://esolangs.org/wiki/Esimpl
21:01:06 <ais523> which is as fast as a Turing machine, or if restricted to queues only, as fast as a queue automaton
21:01:22 <ais523> that said, I think "as fast as a Turing machine" is beatable by things that aren't Turing machines
21:01:43 <b_jonas> is there a way to distinguish between "as fast as a Turing machine" and "as fast as a two-stack machine"?
21:02:43 <b_jonas> I know there's a distinction between two-stack machine and three-stack machine because the two-stack machine can't reverse (or sort) a list of bits quickly
21:02:51 <ais523> a Turing machine can implement an n-stack machine with only a constant factor slowdown
21:03:06 <ais523> I got confused with something else
21:03:15 <ais523> I think it probably is possible to distinguish
21:03:52 <b_jonas> I think a Turing-machine is as fast as brainfuck, within constant factor
21:04:17 <b_jonas> (where the constant factor might depend on the program)
21:04:31 <ais523> for non-bignum brainfuck, you can compile brainfuck into a Turing machine directly
21:04:42 <ais523> bignum brainfuck is substantially different though I think
21:05:21 <b_jonas> yes, I was thinking of brainfuck with 8-bit cells
21:05:59 <ais523> Esimpl can do bignum brainfuck, implementing all the commands in O(1) apart from < and > which are O(log n) of the value on the cell
21:06:05 <ais523> which is actually probably faster than a Turing machine
21:06:24 <ais523> unless there's some clever encoding I haven't thought of
21:06:41 <ais523> or, actually, no, + and - are also O(log n)
21:07:05 <b_jonas> I wonder if turing machine can actually simulate two-stack with constant slowdown with some clever amortized copying solution
21:07:10 <ais523> amortized O(1) is possible for + and - I think, but would add a bunch of complexity
21:07:51 <ais523> (while retaining O(log n) < and >)
21:09:30 <ais523> b_jonas: a two-stack machine can sort a list of bits quickly: you do a radix sort with the 0s in 1 stack and the 1s in the other stack
21:09:39 <ais523> * 0s in one stack and 1s in the other stack
21:10:23 <ais523> oh, you're assuming that the list of bits starts on one of the stacks, so you only get the other one to work with
21:10:30 <b_jonas> another question is how you measure the difference between a three-stack machine and a more powerful machine, like one with pointers (a machine with finite control, a bunch of pointer registers, and it can cons and setcar) or one on a tree-shaped memory of cells (like Treehugger but with finite control)
21:10:34 <esolangs> [[Not Python]] M https://esolangs.org/w/index.php?diff=117320&oldid=117275 * PythonshellDebugwindow * (+0) /* Syntactic extensions */ Fix capitalisatoin
21:11:00 <b_jonas> ais523: yes, I phrased that in a silly way, sorting bits is easy because you can just count the number of 0s and 1s
21:11:18 <ais523> one of the things that I feel like I've been fighting against recently is the assumption that programs have an arbitrary FSM available to control them
21:11:21 <b_jonas> I should say sorting a list of words of arbitrary lengths
21:11:23 <ais523> and just need to do the data storage
21:12:06 <ais523> in practice, implementing the control part of a language can be just as hard as implementing the data part, and most of my recent languages have been trying to find ways to make the control and data the same thing
21:12:27 <esolangs> [[Not Python]] M https://esolangs.org/w/index.php?diff=117321&oldid=117320 * PythonshellDebugwindow * (+1) /* Comparison */
21:12:41 <b_jonas> that's kind of the point of Blindfolded arithmetic
21:12:49 <ais523> e.g. tag systems don't have an FSM, if they did they would be queue automata instead
21:13:26 <ais523> if you are programming in a tag system, you have to resign yourself to the fact that the position in which a symbol is interpreted is based on the sum of widths of everything to its left
21:13:39 <ais523> which were determined on the generation before
21:14:19 <ais523> so, any sort of communication from one symbol to another a) has a time delay and b) affects a segment of the tape up to the symbol that cancels it again
21:15:33 <b_jonas> isn't that only true for a restricted tag system that consumes input in fixed width chunks?
21:15:39 <ais523> there are some minor modifications to tag systems that would avoid this problem, e.g. imagine a tag system symbol that causes the next symbol to also be produced from if this symbol is produced from (rather than skipping the next m-1 symbols as usual)
21:15:53 <b_jonas> the time delay comes from the queue, it's not specific to tag systems
21:16:34 <ais523> b_jonas: no, for me it's true by definition for tag systems, as in I define whether something is a tag system variant or not by whether a symbol can have a "local" effect on the symbols near it or on whether it can only affect the far end of the queue
21:16:55 <ais523> a queue automaton can, say, scan a queue and output all the symbols that immediately follow a given symbol X
21:17:09 <ais523> thus, e.g., "ABXCDEXFXG" would output "CFG"
21:17:25 <ais523> in a tag system, you can't do that all, not even if X is a different width from the other symbols
21:17:54 <ais523> the input would need to look more like "ABXCYDEXFYXGY", i.e. with a separate symbol to say "stop outputting here"
21:18:51 <ais523> an interesting side effect is that tag systems are bad at interpreting queue-based languages (including interpreting other tag systems), they are better at interpreting counter-based languages
21:19:05 <ais523> …which is also why tag system TCness is normally proved using compilers rather than intepreters
21:21:44 <esolangs> [[]] N https://esolangs.org/w/index.php?oldid=117322 * BoundedBeans * (+6996) Created page with " is an esolang by [[User:BoundedBeans]] intended to achieve a certain visual appearance, and to use a lot of his favorite symbol. ==Syntax== Every line should have exactly 20 regular characters and 20 combining diacritical marks. They should be paired up in such a way th
21:21:57 <b_jonas> that's even if you allow a large number of symbols for the tag system, right?
21:22:15 <ais523> assuming you need to be able to handle arbitrarily long strings
21:23:31 <esolangs> [[Language list]] https://esolangs.org/w/index.php?diff=117323&oldid=117279 * BoundedBeans * (+11)
21:23:43 <ais523> "print the first character of this string" is possible in tag systems in O(log n) time, which is better than I initially expected but still slower than a queue automaton
21:24:01 <esolangs> [[User:BoundedBeans]] https://esolangs.org/w/index.php?diff=117324&oldid=116395 * BoundedBeans * (+10)
21:25:04 <ais523> (you can find every character in a position that's 1 mod 2, then every character in a position that's 2 mod 4, then 4 mod 8, etc., until eventually only the character in position 0 has been found)
21:25:29 <ais523> err, only the character in position 0 has been unfound, and then it knows it's the character in position 0
21:26:30 <ais523> huh, does this work for AORS too? if so then it might be possible to get a sub-exponential TCness proof (but still not linear)
21:26:59 <ais523> the difference is that in a tag system, the string is capable of knowing for itself when the last character has been found, but in AORS some external thing to the left would need to have an idea of how long the string is
21:27:18 <ais523> which it can't know exactly in general, but it's possible to get an estimate that's always exactly right or too high, never too low
21:28:05 <ais523> so I guess the problem reduces to "what's the slowest-growing increasing function that you can calculate in AORS" which is non-obvious
21:33:47 <esolangs> [[Cammy/Hives]] https://esolangs.org/w/index.php?diff=117325&oldid=117025 * Corbin * (+1065) /* Encoding of v2 Hives */ Flesh out the rest of the current hive functionality.
21:53:03 -!- cpressey has quit (Ping timeout: 245 seconds).
23:59:48 -!- Koen has quit (Quit: Leaving...).