00:06:14 -!- FreeFull has quit.
00:22:03 -!- Lord_of_Life has quit (Ping timeout: 268 seconds).
00:22:25 -!- Lord_of_Life has joined.
00:33:45 -!- b_jonas has quit (Ping timeout: 268 seconds).
00:55:09 -!- b_jonas has joined.
01:16:25 -!- sprock has joined.
01:23:52 <esolangs> [[BrainSoup]] https://esolangs.org/w/index.php?diff=89350&oldid=89343 * PixelatedStarfish * (+0)
01:25:58 -!- earendel has quit (Quit: Connection closed for inactivity).
02:44:02 -!- dutch has quit (Quit: WeeChat 3.3).
02:45:30 -!- dutch has joined.
03:42:11 -!- monoxane has joined.
05:00:37 <int-e> tromp: Ah, Sx(Kz)y = xyz is kind of neat
05:27:34 <int-e> tromp: F = \x\y.y; toChurch = \n\f\z. let A = \p. p (\a\b\_\p. p a (f b)) z in n A A F;
05:34:58 -!- oerjan has quit (Quit: Nite).
05:42:26 -!- tm512 has quit (Ping timeout: 260 seconds).
05:43:27 <int-e> based on S x A B = x B (A B), so if A, B, and A B are all similar then this gives us a nice recursion) and the syntactic accident <F,X> <F,Y> = <F,Y> F X = F F Y X so we can use pairs <F,_> for A, B and let F F Y X reduce to some <F,Z> to fulfil the shape requirement. The concrete instance uses Z = f Y.
06:44:03 -!- tm512 has joined.
06:44:05 -!- tm512 has changed hostmask to ~tm512@user/tm512.
07:08:22 <int-e> Oh wow, I messed up my definition of K, wow. n A A F should be n A (A A) F instead.
07:15:50 -!- zzo38 has quit (Ping timeout: 268 seconds).
07:19:58 <int-e> (the other one gives the predecessor instead which is kind of neat)
07:21:46 <tromp> int-e: that's really cool! and doesn't even need recursion.
07:22:12 <tromp> mine did: to_church = \toc\n. iszero n C0 (C_succ (to_church (pred n)))
07:22:44 <tromp> that should be to_church = \n. iszero n C0 (C_succ (to_church (pred n)))
07:23:59 <tromp> iszero = \n. n F I S K
07:24:34 <tromp> pred = \n\x\y.n (K y) x
07:25:38 <int-e> yeah it's always nice to get the duplication that recursion requires for free
07:29:17 <tromp> hmm, i thought yours would be smaller in CL size
07:29:50 <int-e> I'm only looking at BLC sizes
07:30:08 <int-e> CL size is too volatile and usually bigger anyway
07:31:06 <int-e> to_church = \n\f\z. let tc = \n. isZero_ n z (f (tc (pred_ n))) in tc n; is *a bit* smaller in BLC than the C0/C_succ thing.
07:31:28 <int-e> sorry, I renamed iszero and pred to fit my test file
07:32:50 <int-e> With CL, that's probably not true... because adding and using extra arguments is so expensive.
07:33:51 <tromp> sometimes hand optimized bracket abstraction can improve things
07:34:03 <int-e> tromp: So in that spirit, toChurch = \n. let A = \p. p (\a\b\_\p. p a (C_succ b)) C0 in n A (A A) F may be better for CL.
07:34:57 <tromp> oh yes, much shorter
07:38:12 <tromp> i came across these numerals in Wolfram's book on combinators
07:38:19 <int-e> is it worth to manually replace n A (A A) by S n A A?
07:38:41 <tromp> https://www.wolfram-media.com/products/combinators-a-centennial-view.html
07:39:22 <int-e> (that looks like a rare pattern so I doubt you'd implement it in an automatic converter)
07:40:04 <tromp> no, that S n A A doesn't make a difference
07:41:20 <int-e> Ah, right... bracket abstraction will act the same either way.
07:41:45 <tromp> Stephen Wolfram only came up with a size 181 combinator for to_church
07:41:49 <int-e> \A. n A (A A) -> S n I
07:42:24 <tromp> apparently based on applying n to Church numerals 2 and 3
07:43:33 <tromp> that's S n A, not S n I ?!
07:46:33 <tromp> i wonder if these should be called SK numerals or Fibonacci numerals
07:46:41 <int-e> Oh, right, I stopped too early. It'll be S n (S I I), vs. \A. S n A A = S (S n) I. So it's a bit unclear which is better.
07:47:16 <tromp> since they satisfy (n+2) x y = (n x y) ((n+1) x y)
07:47:52 <int-e> (you have two I's in the former, but n is at a deeper depth in the latter.)
07:48:30 <int-e> Yeah they do have a Fibonacci vibe.
07:48:55 <tromp> the number of y's in n x y is Fibonacci(n)
07:49:17 <tromp> this just replaces sum in the recurrence by application
07:49:20 <int-e> Already visible in S x A B = x B (A B)
07:51:17 <esolangs> [[Language list]] M https://esolangs.org/w/index.php?diff=89351&oldid=89308 * Elmusfire * (+16) Added new language
07:52:17 <esolangs> [[Rrreplace]] N https://esolangs.org/w/index.php?oldid=89352 * Elmusfire * (+6648) rrreplace is an esoteric language that uses string substitution in a functional way.
07:53:53 <esolangs> [[Rrreplace]] M https://esolangs.org/w/index.php?diff=89353&oldid=89352 * Elmusfire * (+1) typo
07:57:38 <int-e> tromp: Hmm, I don't think I have you abstraction elimination code... what sizes do you get for to_church and toChurch?
07:58:35 <tromp> well, i have to manually adjust for the SK Y combinator of size 12:(
07:58:50 <int-e> or does `blc comb` mostly do it?
07:59:08 <tromp> then my to_church comes out at 69
08:00:27 <tromp> i actually use ./blc bcl and divide output length by 3
08:01:14 <int-e> ah, we're just counting combinators.
08:01:55 <tromp> yes, but we could count bits as well. which is nearly purely linear
08:02:19 <int-e> and I need to use the right `succ` too
08:02:37 <tromp> the newline at the end of bcl output bumps that right up to 3n
08:02:50 <int-e> (\n\f\x. n f (f x) is worse than \n\f\x. f (n f x) in CL)
08:03:18 <tromp> yes, i use C_succ = \n\f\x.f (n f x);
08:03:47 <int-e> bcl just doesn't care
08:04:48 <int-e> I guess I should prefer \n\f\x. f (n f x) for beaing lazier.
08:05:16 <tromp> yes, it's always seemed the more proper order to me
08:05:24 -!- hendursa1 has joined.
08:05:34 <tromp> applying the extra f at the end rather than at the start
08:07:42 -!- hendursaga has quit (Ping timeout: 276 seconds).
08:12:08 <int-e> anyway nice to see a Wolfram book that's not reinventing science :P
08:13:06 <int-e> "thought-provoking and broadly accessible" I can believe... I imagine that's also actually true for the ANKS of book.
08:20:28 <tromp> maybe you want to go after his $20k prize: https://combinatorprize.org/
08:21:28 <int-e> Hmm, does he cite Johannes Waldmann's thesis?
08:22:11 <tromp> he's not much into citing other people:(
08:23:13 <tromp> but he does have Waldmann in the references
08:23:59 <int-e> (it's almost exclusively on the S combinator, https://www.imn.htwk-leipzig.de/~waldmann/pub/)
08:25:30 <int-e> Yeah attributing the idea that this might be TC to himself doesn't feel right to me at all.
08:26:18 <tromp> did Johannes come up with that 39x39 table?
08:27:08 <tromp> to determine halting behaviour of S-only combinators?
08:28:15 <tromp> his book just says: What was discovered in 2000 is that there's a complete way to test.... and then gives the table
08:29:31 <tromp> for rule 110 universality, he says: with much of the heavy lifting done by a then-research assistent of mine
08:30:10 <int-e> Hmm there's no table of states in the thesis, I think. He defines lots of auxiliary regular tree languages. I've never thought to count them...
08:33:28 <int-e> 2000 matches The Combinator S, Information and Computation 159, 2-21 (2000)... hmm. have I seen that paper...
08:35:11 <tromp> yes,that's one of his 2 references
08:35:45 <tromp> the other is a coauthored 2010 paper on local termination
08:36:45 -!- Sgeo has quit (Read error: Connection reset by peer).
08:36:58 <tromp> oh, he does name Johannes at the chapter end
08:37:32 <int-e> the paper has a grammar, so the table is Wolfram's own doing, I think.
08:38:51 <tromp> he mentions Joerg Endrullis
08:39:18 <tromp> for "The detailed version that I used here"
08:39:27 <int-e> yeah not unexpected in this context
08:40:43 <tromp> one of the coauthors of the 2010 paper
08:49:02 <int-e> Anyway I'm not going down that rabbit hole :)
08:51:20 <int-e> (I've already managed to stay away from the question whether the word problem for S is decidable for 10+ years)
10:23:05 <tromp> i'll write some sort of blog article about SK numerals...
10:48:39 -!- Everything has joined.
11:29:56 -!- wib_jonas has joined.
11:39:00 <esolangs> [[Rrreplace]] M https://esolangs.org/w/index.php?diff=89354&oldid=89353 * PythonshellDebugwindow * (+62) Lowercase, categories
12:19:08 -!- arseniiv has joined.
13:26:29 <esolangs> [[Lananang]] M https://esolangs.org/w/index.php?diff=89355&oldid=89349 * Heptor * (+114)
13:34:07 <esolangs> [[Lananang]] https://esolangs.org/w/index.php?diff=89356&oldid=89355 * Heptor * (+72) /* Inbuilt Commands */
13:34:58 <esolangs> [[Lananang]] https://esolangs.org/w/index.php?diff=89357&oldid=89356 * Heptor * (+4) /* Math */
13:37:34 -!- wib_jonas has quit (Quit: Client closed).
13:41:46 -!- wib_jonas has joined.
13:49:53 -!- perlbot has quit (Ping timeout: 268 seconds).
13:49:53 -!- simcop2387 has quit (Ping timeout: 268 seconds).
14:12:57 -!- Everything has quit (Quit: leaving).
14:29:57 <Corbin> tromp, int-e: S isn't complete on its own. Wolfram doesn't accept the folklore proof for some reason, probably because it would make him look like a dunce.
14:30:47 -!- tech_exorcist has joined.
14:37:34 <esolangs> [[Brainfuckn't]] N https://esolangs.org/w/index.php?oldid=89358 * 4gboframram * (+7224) Created page with "Brainfuckn't is a tape-based esolang created by [[user:4gboframram]]. The goal of the language was to make a language that is more frustrating to use than [[brainfuck]], but a..."
14:39:24 <esolangs> [[Brainfuckn't]] https://esolangs.org/w/index.php?diff=89359&oldid=89358 * 4gboframram * (+11) /* Brief Specification */
14:40:58 <esolangs> [[Brainfuckn't]] https://esolangs.org/w/index.php?diff=89360&oldid=89359 * 4gboframram * (+8) /* Computational Class */
15:24:56 <tromp> Corbin: what folklore proof are you referring to? S is not complete because you can't define K in terms of S? Wolfram recognizes that of course
15:32:17 <int-e> yeah part of the exercise is undoubtedly to come up with an encoding for inputs and an acceptance condition; maybe even an evaluation order
15:32:49 <tromp> Wolfram wonders if there are some efficient functions <embed, detect, extract> such that embed maps an SK term to an S term, detect maps an S term to a boolean, and extract maps an S term to an SK term, and if SK term t has a normal form nf, then you can reduce embed t to some term s for which detect s and extract s = nf (or something like that)
15:34:13 <tromp> this seems exceedingly unlikely to be possible, but i don't know how to disprove it
15:34:20 <int-e> https://combinatorprize.org/ should really include a proper problem statement (did I miss one?)
15:36:05 <tromp> check https://writings.stephenwolfram.com/2021/06/1920-2020-and-a-20000-prize-announcing-the-s-combinator-challenge/
15:37:16 <tromp> the <embed, detect, extract> statement is my own interpretation for what he wants
15:39:09 <int-e> oh the full 39x39 table is actually online too https://content.wolfram.com/uploads/sites/43/2020/12/sw1203img440.png
15:39:14 <tromp> you can intrepret "efficient" either as polytime, or more generously as any primitive recursive running time
15:39:15 <int-e> for whatever that's worth
15:40:06 <tromp> and the reduction strategy used in the above should also be efficiently computable
15:40:08 <Corbin> Part of the problem is that Wolfram keeps saying "universal" instead of "Turing-complete". This is part of his effort to avoid actually citing real mathematics.
15:41:02 <Corbin> For consider the Church-Turing thesis. Given two Turing-complete systems, we should be able to write emulators for each system in the other system, so that we can emulate a system on itself by stacking the two emulators together.
15:41:18 <tromp> it's funny how his books are full of "it seems that", "it appears that", "it looks like" .... :)
15:41:46 -!- Sgeo has joined.
15:41:48 <Corbin> So if S is "universal", then there should be emulations SK -> S -> SK and S -> SK -> S which preserve halting.
15:42:32 <Corbin> The latter is trivial with a handwave. So it's the former that we want; how do we emulate SK in S? And so that's what Wolfram has focused on.
15:43:14 <Corbin> But now, notice that we still want anything we map from SK into S to come back out in SK working the same way. And *that* gives us leverage, because now we can use folklore about missing K and I to argue that S is not Turing-complete.
15:43:37 <tromp> but it's a non-standard notion of emulation, as he allows a terminating computation to be emulated by a non-terminating one
15:44:53 <Corbin> Yeah, that's kind of a problem, isn't it? I wonder how he imagines checking whether a computation is complete.
15:45:07 <int-e> That's rather unrestricted (the compiler/detector/decoder scheme), so yeah I don't see how a negative proof could work.
15:46:14 <Corbin> As soon as we've done this, then all of the proofs that people give in the comments to Wolfram's challenge post are back on the table, and at least some of them sound convincing enough.
15:48:01 <int-e> How do you prevent this... encode TM in the stabilized part of a non-terminating term. The detector runs the TM for <current size of term> steps, signals success on nontermination; the decoder also runs the TM, extracts input.
15:48:09 <int-e> Now... if I put it like that it's clearly cheating.
15:48:43 <int-e> But neither of the parts is Turing-Complete by itself.
15:49:33 <int-e> The S combinator evolution is an essential part if it's ultimately just used as fuel.
15:52:05 <tromp> int-e: cute exploit:-)
15:53:25 <int-e> s/nontermination/termination/
15:53:30 -!- FreeFull has joined.
15:54:07 <Corbin> Hm. Here's another approach. From category theory, it's provable that Turing-complete computation cannot be reversed. But because S doesn't forget values, we should be able to reverse a sequence of applications in a tree with only S combinators.
15:54:37 <int-e> This kind of thing is a hard problem to state if you don't want to severely restrict the encoder and decoder.
15:55:33 <tromp> it's easy to make TM reversible with an extra tape
15:56:14 <Corbin> A fair point. Similarly, while sets and functions aren't reversible, sets and relations are reversible. The chosen model matters a lot.
15:56:28 <Corbin> This is another reason why "universal" is a weasel-word for Wolfram.
16:00:09 -!- daggy1234[m] has quit (Quit: You have been kicked for being idle).
16:02:47 <int-e> Well, S contraction isn't confluent. S(SSS)SS -> SSSS(SS) -> SS(SS)(SS) -> S(SS)(SS(SS)) <- S(SS)(SSSS) and neither S(SSS)SS nor S(SS)(SSSS) can be contracted further.
16:02:55 -!- hendursa1 has quit (Quit: hendursa1).
16:02:59 -!- daggy1234[m] has joined.
16:03:05 <int-e> So that's an obstacle to reversal.
16:03:28 -!- hendursaga has joined.
16:04:54 <Corbin> Oh! Okay. Then I have been too facile about this. If S isn't confluent on its own, then that means that we need to consider this non-deterministically.
16:05:44 <int-e> Hmm... do you accept the proof that rule 110 is universal? I don't think I do. I think providing an infinite background pattern is too much freedom.
16:06:45 <Corbin> I don't think it's any different than allowing a Turing machine to take an input, or allowing a Wang tileset to start with a border on one edge/corner.
16:07:16 <int-e> inputs are finite though
16:08:11 <int-e> Corbin: S-reduction is confluent though.
16:08:13 <Corbin> That's fair. An infinite *repeating* background pattern would be fine.
16:08:19 -!- daggy1234[m] has left.
16:08:58 <Corbin> Oh, sorry; what's contraction?
16:09:37 <int-e> Uh, the inverse of reduction here... why did I pick the term "contraction"...
16:09:58 <int-e> Ah because S x y z -> x z (y z) the right-hand side is usually bigger than the left-hand side.
16:10:14 <int-e> So inspired by size.
16:10:30 <Corbin> Oh, okay. It doesn't have to be confluent to be reversible. What I'm getting at is that, because all of the data is still there, even a non-deterministic reversible approach is possible.
16:10:35 <int-e> But technically wrong, I should've said "expansion".
16:11:05 <tromp> or "unreduction" :-)
16:11:11 <Corbin> If there's a K combinator, then the non-constant input is forgotten, and in an untyped context, we can't just range over what that input might have been; it could have been *anything*. So we can't non-deterministically go backwards.
16:11:32 <Corbin> Going backwards with S is merely exponential. It's expensive but finite to explore.
16:12:40 <int-e> Right. tromp's argument was more to the point anyway.
16:12:58 <int-e> (that reversibility isn't an obstacle to universality)
16:15:20 <Corbin> It's an obstacle to asserting that something has been *computed*. I'm sure you've heard the argument of the waterfall computer, which "computes" by permuting the positions of atoms; but in order to actually extract computation from a permutation, we must label the inputs and the outputs, and the manipulation of those labels is the actual computation.
16:16:17 <Corbin> Quantum computers only compute because of how the Born rule works; we measure qubits at the end, irreversibly altering their state.
16:17:35 -!- wib_jonas has quit (Quit: Client closed).
16:17:56 <int-e> Corbin: Well, an extractor could potentially be as simple as labeling the term with a top-down tree automaton and discarding the subtrees for certain trees.
16:18:40 <Corbin> int-e: Yes, but I view that as just plugging in a K at the top and letting the S terms apply that K over and over, which is known to build all of SKI.
16:18:41 <int-e> If that works (big if, obviously) I'd accept that the actual computation happens in the S calculus.
16:19:44 <int-e> I doubt that you can capture that in a finite tree automaton.
16:20:45 <int-e> (Gut feeling, no proof.)
16:22:49 <Corbin> int-e: Here's a large pile of statements; the important part is under "Applicative Systems and Computable Maps". https://golem.ph.utexas.edu/category/2019/08/turing_categories.html If S and K are present, even in a way where S was pre-applied and freeze-dried and K was only mixed in later, then we get a partial combinatory algebra and etc.
16:23:25 <Corbin> The root of that is ultimately https://en.wikipedia.org/wiki/Smn_theorem and so that should be our focus. Can we use S to implement Kleene's projections?
16:24:38 <Corbin> Well, K is one of Kleene's projections! It's the projection which takes two arguments and returns the first one. And it's known that S can't implement K.
16:25:53 <Corbin> This completes a proof statement which convinces me that Wolfram's conjecture is false; every Turing category has a K combinator.
16:28:11 <esolangs> [[Brainfuckn't]] https://esolangs.org/w/index.php?diff=89361&oldid=89360 * 4gboframram * (-9) /* Brief Specification */
16:29:44 <esolangs> [[Brainfuckn't]] https://esolangs.org/w/index.php?diff=89362&oldid=89361 * 4gboframram * (+1) /* Brief Specification */
16:41:01 <int-e> A strong counterpoint is that BCW is Turing-complete and also lacks K. The idea is to replace every value v by a pair <v,g> where g collects any garbage that would have to be deleted, while the first component just acts as in ordinary lambda calculus/combinatory logic.
16:41:29 <int-e> (as usual pairs are encoded by <x,y> = \p. p x y)
16:51:34 <Corbin> I haven't seen this before and I'm having trouble working it out myself. Could you show me how I or K are encoded?
16:53:34 <int-e> something like http://paste.debian.net/1218221/
16:54:04 <int-e> that feels overcomplicated, actually
16:55:01 <int-e> Note on variable names: px = pair encoding x; x = the original x; gx = garbage associated with x.
16:55:37 <Corbin> Oh. I'll keep working it out for myself, but I was hoping for expressions in B, C, and W.
16:55:51 <int-e> That would be totally uninstructive
16:56:39 <Corbin> It would be totally constructive, though.
16:59:58 <Corbin> int-e: I want to buy your argument. Even with it, I think I can refute the idea that this would work for S. The problem is, roughly, implementing S with S.
17:01:24 <Corbin> Let's suppose for contradiction that there's two expressions in S, called big-S and big-K, which implement SK and are therefore make S universal. In order to do this, we'd use the same application for big-S and big-K as with just S, except maybe our application needs an intermediate glue, also made wholly of S, in order to function.
17:02:25 <Corbin> There's a smallest such big-S and big-K, since we're working with finite expressions. But the smallest big-S is just S itself. This reduces the problem to whether big-K can be implemented with just S, which is just the question of whether S alone implements K.
17:06:48 <int-e> Oh I need I as well, don't I.
17:15:39 <tromp> yes, to the extent that I = W K
17:17:10 <tromp> but isn't I also B C C ?
17:18:16 <int-e> How? B C C x = C (C x)
17:18:39 <tromp> B C C x y z = C (C x) y z = C x z y = x y z
17:19:10 -!- sprock has quit (Ping timeout: 260 seconds).
17:25:26 <int-e> Corbin: so, [K] = C (W (B (C I) (B (C I) (C (B C (B (B C) (W (B (C (B B B)) (B (B (B (C I))) (B (B B) (B B))))))) I)))) I (B C (C I))
17:27:22 <int-e> yay it's actually correct.
17:29:35 <int-e> This implementation isn't very good, it encodes W as B W (C (B B C) I) :)
17:31:22 <Corbin> Okay, and that's with I = B C C as above. Makes sense. The size of the trees is definitely foreboding.
17:32:15 <int-e> But unsurprisingly the bad encoding of W itself doesn't matter.
17:32:18 <Corbin> Consider me convinced. Good work; thank you.
17:33:51 <int-e> Unfortunately, I = B C C only works if it's actually applied to 3 more arguments.
17:35:15 <Corbin> But that's fine, isn't it? Because at the top, we have a pair which needs one argument to eliminate the pair, and then two more arguments to invoke the LHS and throw away the RHS?
17:36:20 <int-e> So what about the first component of the pair
17:36:26 <int-e> we know nothing about that.
17:36:40 <int-e> But it's the value we actually want to have in the end.
17:51:02 <int-e> tromp: so I hacked BCWI(plus K if erasure is present) abstraction elimination in the blc tool... but I did it by extending the CL datatype with extra constructors for I, B, C, and W. Should I commit or is that too dirty?
17:52:18 <int-e> I guess I can make a pull request instead and leave it for discussion.
17:52:33 <tromp> please commit as a different branch for now
17:54:36 <tromp> need to think about best approach. maybe a new datatype with some conversion operators?
17:54:37 <int-e> yeah did that just now
17:55:04 <int-e> I mean I pushed a new branch and made a PR for discussion
17:55:47 <int-e> I also know almost nothing about this combinator basis... like, are there any interesting optimizations?
17:58:06 <int-e> Anyway, at least this way the code won't be lost.
18:02:41 <Corbin> Huh. By complete coincidence, I just found https://cstheory.stackexchange.com/q/50688/52212
18:03:17 <Corbin> Is the answer just C? And then adding K makes for a better encoding.
18:03:50 <Corbin> int-e: I think you could provide a complete answer here, if you'd like the karma. I only feel qualified to leave a comment.
18:05:21 <int-e> I have no SE account. I also lack intuition for how essential or not C is in all of this.
18:06:57 <int-e> What I do know is that B, C, and S have very clear roles in abstraction elimination. Assuming x occurs in M N we have [\x. M N] -> B M [\x. N] if x doesn't occur in M; [\x. M N] -> C [\x. M] N if x doesn't occur in N; [\x. M N] -> S [\x. M] [\x. N] otherwise.
18:08:24 <int-e> And you can get close enough to S from W, B, and C: S a b = W (B (C a) b)
18:12:16 <esolangs> [[User:Pandaqwanda/pixeLang]] https://esolangs.org/w/index.php?diff=89363&oldid=89335 * Pandaqwanda * (+258)
18:14:01 -!- sprock has joined.
18:14:50 <esolangs> [[User:Pandaqwanda/pixeLang]] https://esolangs.org/w/index.php?diff=89364&oldid=89363 * Pandaqwanda * (-231)
18:26:09 -!- sprock has quit (Ping timeout: 268 seconds).
18:46:38 -!- zzo38 has joined.
18:57:39 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
19:12:50 <b_jonas> “<tromp> but it's a non-standard notion of emulation, as he allows a terminating computation to be emulated by a non-terminating one” => I don't think that's much of a problem. In PCs before the ATX chasis, programs couldn't turn the power supply off, nor did they have a power-saving mode for the CPU or motherboard, and often had no power saving mode for the CRT either. The main power supply and CRT
19:12:57 <b_jonas> could only be turned off externally, with no control from a program. Would you argue that those old computers can't do powerful enough computations because they can't decide to halt depending on the result of a computation? I don't think so. (If you want to say that they're not powerful because they have little RAM, that's fine.)
19:18:43 <b_jonas> Or, for a more mathematical argument, consider Underload without the ! and S primitives, which can't delete anything, but is still Turing-complete.
19:20:07 <int-e> or that stupid rule 110 cellular automaton
19:20:11 <int-e> wich just keeps going
19:20:49 -!- tromp has joined.
19:38:18 <b_jonas> “But the smallest big-S is just S itself.” => are you saying that if you already know how to do arithmetic with dollars, then you can't simulate doing arithmetic with dollars and cents, because the smallest thing that can simulate a dollar is a dollar itself, and there's nothing that can simulate a cent if you choose that?
19:42:40 <b_jonas> “or that stupid rule 110 cellular automaton / wich just keeps going” => hmm. if https://esolangs.org/wiki/Infinite_Vector was defined without the :-( operator, so that programs can't halt and in nontrivial programs the memory keeps growing and can never shrink, would you still count it as Turing-complete?
19:47:54 <int-e> btw I'm fine with that aspect of rule 110, it's really the infinite intial state that leaves me dissatisfied
19:49:14 <riv> no one has managed to remove that?
19:49:29 <riv> i guess people aren't really interested in rule 30
19:49:30 -!- sprout_ has joined.
19:49:36 <int-e> not that I'm aware of.
19:50:17 <int-e> But I could easily have missed it... I largely don't care.
19:50:50 <riv> it seems like nobody really studies these 1d CAs
19:52:29 -!- sprout has quit (Ping timeout: 268 seconds).
19:53:07 <int-e> maybe 2D CAs are just more exciting to look at
19:54:13 <b_jonas> a finite control pointer register machine that allocates immutable conses on the heap also can't "forget" anything, though it can lose conses in a way that a garbage collector could free them, and it is Turing-complete.
20:12:02 <int-e> tromp: oh you made a suggestion, that sounds reasonable. will revisit tomorrow
20:13:01 -!- Guest71 has joined.
20:13:37 -!- Guest71 has quit (Client Quit).
20:14:33 <Corbin> b_jonas: That's a really funny analogy, thanks.
20:26:05 <b_jonas> there is some difference in scale though. Infinite Vector has to at least double its memory usage in every loop, while a pointer machine might cons logarithmically rarely.
20:26:53 <b_jonas> maybe it's not logarithmic, only nth root if you have n+O(1) registers
20:37:58 -!- perlbot has joined.
20:39:29 -!- simcop2387 has joined.
20:41:17 -!- sprock has joined.
20:46:37 -!- arseniiv has quit (Quit: gone too far).
20:49:03 -!- tech_exorcist has quit (Quit: see you tomorrow).
20:49:54 -!- sprout has joined.
20:53:31 -!- sprout_ has quit (Ping timeout: 268 seconds).
21:02:34 <esolangs> [[User:AmNow/Sandbox]] N https://esolangs.org/w/index.php?oldid=89365 * AmNow * (+196) Created page with "amnows sandbox page im not dead currently == apl stuff == s1 both{} truth{s s=1 : loop s} loop{ss both 1 loop s}..."
21:02:44 <esolangs> [[User:AmNow/Sandbox]] https://esolangs.org/w/index.php?diff=89366&oldid=89365 * AmNow * (-1)
21:29:12 -!- sprock has quit (Ping timeout: 256 seconds).
21:36:12 -!- delta23 has joined.
21:42:53 <esolangs> [[Timers]] M https://esolangs.org/w/index.php?diff=89367&oldid=89242 * Rphii * (-190) minor feature enhancement
22:27:57 -!- archenoth has quit (Read error: Connection reset by peer).
22:34:38 -!- archenoth has joined.
22:51:58 -!- dutch has quit (Quit: WeeChat 3.3).
23:07:35 -!- archenoth has quit (Ping timeout: 264 seconds).
23:08:19 <tromp> SK numerals article up at https://john-tromp.medium.com/sk-numerals-9ad1b5634b28
23:09:04 -!- archenoth has joined.
23:11:34 -!- Kit has quit (Remote host closed the connection).
23:11:53 -!- Kit has joined.
23:13:34 -!- Kit has quit (Remote host closed the connection).
23:13:52 -!- Kit has joined.
23:14:32 -!- FreeFull has quit.
23:15:29 -!- dutch has joined.
23:32:18 -!- sprock has joined.
23:55:44 -!- richbridger has joined.