00:07:31 <zzo38> I read that if a program requires X time then it should require sqrt(X) memory.
00:12:36 <esolangs> [[Topple/Source Code/Topple 1.0]] M https://esolangs.org/w/index.php?diff=164314&oldid=163809 * H33T33 * (+81)
00:19:49 <korvo> The recent results from Ryan Williams?
00:25:05 <zzo38> I forget what was their name; I mentioned the part that I remembered.
00:27:16 <korvo> No worries. Yeah, it's a big deal. The resulting program is *not* fast, so it's not something we'd practically use, but it's very cool.
00:30:54 <zzo38> I had made up a cryptographic hash algorithm some time before I read that, which has a similar property; the time requirement is the product of the input size and output size, and the memory requirement is either size (whichever one is known ahead of time), so if the input and output sizes are equal then it will be similar.
01:43:13 -!- bongino has joined.
02:09:20 -!- salpynx has joined.
02:10:05 <salpynx> !ztest nana_returns (-)*23>(+)*11(>>(-)*5>[-[-[(+)*9[-]>]]>](-)*23)*-1
02:10:05 <zemhill> salpynx.nana_returns: points -3.62, score 17.98, rank 24/47
02:10:48 <salpynx> !zjoust nana_returns (-)*23>(+)*11(>>(-)*5>[-[-[(+)*9[-]>]]>](-)*23)*-1
02:10:49 <zemhill> salpynx.nana_returns: points -3.62, score 17.98, rank 24/47
02:11:56 <salpynx> !ztest nana_original (-)*13>>(+)*21(>>[-[-.[(+)*21[-]>]]+>+](-)*21)*13[>[-]]
02:11:56 <zemhill> salpynx.nana_original: points -6.62, score 14.48, rank 43/47
02:14:29 -!- salpynx has quit (Quit: Leaving).
02:24:28 <esolangs> [[5MAT]] M https://esolangs.org/w/index.php?diff=164315&oldid=160477 * Kg583 * (+0) Fix initialization example
04:19:35 <zemhill> web.toodles: points -0.60, score 20.75, rank 19/47
04:51:35 <zemhill> web.toodles: points -0.60, score 20.75, rank 19/47 (--)
05:07:51 -!- AlsoJAA has joined.
05:11:20 -!- bongino has quit (Ping timeout: 256 seconds).
05:27:09 <esolangs> [[Bespoke]] https://esolangs.org/w/index.php?diff=164316&oldid=150322 * OliveIsAWord * (+2) change comment mnemonic TERMINATE to be 10 letters
05:32:52 -!- bongino has joined.
06:15:20 <korvo> Double-checking https://news.ycombinator.com/item?id=44406171 for insights and getting frustrated with folks confidently misunderstanding BB relative to ZFC.
06:16:53 <ais523> !zjoust two_thirds http://nethack4.org/pastebin/two_thirds.bfjoust
06:16:53 <zemhill> ais523.two_thirds: points 18.90, score 50.30, rank 2/47 (--)
06:17:05 <ais523> (thank you to all my BF Joust opponents for helping to find bugs in two_thirds)
06:17:22 <korvo> In *any* language of arithmetic, a statement like "BB(k) = n" is formally encoded as something like "every k-state TM that is not stuck after n+1 steps will never be stuck", or "for all k-state TMs: if the TM isn't stuck after n+1 steps then it never sticks". It's a universally-quantified implication, *not* an expansion of some arithmetic. BB is explicitly *not* a computation.
06:17:52 <korvo> Oh hey, BF joust~ Instantly brightening up my day. Or darkening down my night, whatever.
06:21:15 <ais523> hmm, there's an interesting philosophical point here in that once you've proven that all the non-terminating programs don't terminate, BB *becomes* a computation
06:21:55 <ais523> or, well, it's basically a halting oracle + a computation run over the programs that halt – e.g. the reason we know BB(5) is that we have a halting oracle for it
06:22:34 <ais523> BB(6) is interesting in that it is very likely that the value of BB(6) is beyond the range of what current computers can calculate naively, so we will need to invent some sort of compressed way to do the computation
06:24:58 <korvo> Sure. "for all k-state TMs" is exponential but finite in k. So the part that defies computation is the proof that they all fail to stick. Or, as constructed by the community, we have constructed an explicit machine which definitely doesn't have a proof of halting, and it in fact doesn't halt assuming SRP or ZFC or etc is consistent.
06:25:57 <korvo> This is where a fear of Erdös shows up. What if we literally don't have the axioms for Collatz, and thus don't have the axioms to prove that every 6- or 7-state TM (doesn't) halt? This could still be the case!
06:34:38 <ais523> oh, of course, there's definitely a point at which it becomes uncomputable
06:34:41 <ais523> we just don't know where it is yet
06:35:22 <ais523> at least, we don't know the exact location (we have upper bounds)
06:36:04 <ais523> fwiw, I have a suspicion that consistent Collatz (Feed the Chaos, Antihydra, etc.) where the multipliers are all the same, may be different from general Collatz where the multipliers can be different
06:36:33 <ais523> the latter is TC, the former isn't obviously so and in fact it isn't clear how to distinguish the programs' behaviours from randomness
06:37:53 <korvo> Sure. General Collatz may also still be somewhat algorithmic; Conway's obstruction just means that the final set of equations which generates solutions is TC.
06:38:09 <korvo> Er, *recursive, and solving recursive equations in general is TC.
06:39:23 <korvo> I'd normally dismiss this sort of thing as unevidenced, but there is one trouble that I haven't solved. We don't have a program on *any* machine which halts iff Collatz is true/false.
06:40:13 <korvo> Tao has a footnote somewhere that it's Pi₂, so some sort of tricky algorithm is required to actually check for the Collatz preconditions without leaving any gaps.
06:45:12 <korvo> I wonder whether I can make the Kirby-Paris-Harrington "hydra" game into an interesting machine. That one's independent of PA, IIRC.
06:45:58 <ais523> korvo: oh, you're talking about the specific 3n+1/2 Collatz rather than Collatz in general?
06:46:28 <korvo> ais523: Yeah. Like, the sort of programs that I could use in the BB Gauge. Standardized Collatz.
06:47:23 <ais523> right, we have a sort of double quantifier – if we interpret 3n+1/2 Collatz as a program, we're basically trying to prove that the program halts for all inputs
06:47:38 <ais523> but it's hard to see how you could detemine that by running it on all inputs, because if it doesn't halt on one of them you never find out
06:48:33 <korvo> Yep. We can somewhat rephrase it as a graph-connectivity problem; we can enumerate the nodes and check whether each one's connected. But that check is also semidecidable and might not halt.
06:50:30 <korvo> This isn't like Con(PA) or Con(ETCS), which are straightforward engineering problems. I guess I have one question about Con(ETCS) that I can take to Stack Exchange tomorrow morning.
06:51:27 <ais523> now I'm wondering how to distinguish between the collatz-like things that act like PRNGs and the collatz-like things that don't – it might not be possible
06:51:52 <ais523> but it feels like for Collatz-like problems, PRNG-style behaviour is the "default" and you need to go out of your way to make it act like, e.g., a set of counters
06:53:00 <korvo> Or at least the counters are up in the exponents, like Gödel numbering.
06:55:29 <ais523> well, when there are counters, they're in the exponents
06:55:52 <ais523> but something like Antihydra or canonical-Collatz doesn't obviously have a structure to its counter at all
06:56:35 <korvo> Oh, is Antihydra the one with the (mod 2**k) pattern? I thought it had a lovely pattern. I have a photo from a whiteboard diagram somewhere.
06:57:55 <korvo> Basically the transition diagram can always admit division by another factor of two, making two copies of the diagram which are interlinked in a very satisfying symmetry. The diagram is always extremely balanced in terms of even and odd, and also in terms of behavior (mod 4), and (mod 8), and etc.
06:58:18 <korvo> This makes it really easy to see that it "probviously" is balanced out and can't really have an excess of evens or odds.
06:58:43 <korvo> Nuts, I'm gonna turn back into a pumpkin. Have a good night.
07:28:44 -!- Sgeo has quit (Read error: Connection reset by peer).
07:59:01 -!- wib_jonas has joined.
08:01:41 <wib_jonas> "recent results from Ryan Williams" => specifically https://eccc.weizmann.ac.il/report/2025/017/ , which I heard of from https://scottaaronson.blog/?p=8680 . note that the runtime is measured on a multi-tape Turing machine.
08:34:07 -!- bongino has quit (Remote host closed the connection).
09:00:39 -!- ais523 has quit (Quit: sorry about my connection).
09:03:51 -!- ais523 has joined.
09:18:56 <zemhill> web.takwin-yuzbasi: points -3.90, score 18.01, rank 25/47 (+21)
09:53:27 <esolangs> [[User talk:GUAqwq]] M https://esolangs.org/w/index.php?diff=164317&oldid=162257 * GUAqwq * (-1845)
10:07:14 <esolangs> [[TrackSpan]] N https://esolangs.org/w/index.php?oldid=164318 * GUAqwq * (+30) Created page with "[[Category:Works_in_progress]]"
10:09:19 <esolangs> [[User:GUAqwq/TCproof to Lambda calculus]] https://esolangs.org/w/index.php?diff=164319&oldid=138289 * GUAqwq * (+20)
10:32:17 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164320&oldid=164318 * GUAqwq * (+788)
10:56:19 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164321&oldid=164320 * GUAqwq * (+1015)
11:02:34 -!- amby has joined.
11:05:07 <esolangs> [[Special:Log/newusers]] create * EnvelopingHedgehog * New user account
11:06:50 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=164322&oldid=164237 * EnvelopingHedgehog * (+112)
11:07:22 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=164323&oldid=164322 * EnvelopingHedgehog * (+117)
11:11:34 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164324&oldid=164321 * GUAqwq * (+702)
11:12:35 <esolangs> [[User:EnvelopingHedgehog]] N https://esolangs.org/w/index.php?oldid=164325 * EnvelopingHedgehog * (+56) Created page with "Hello! I am a software developer who is also a hedgehog."
11:12:43 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164326&oldid=164324 * GUAqwq * (+8)
11:13:10 <esolangs> [[TrackSpan]] M https://esolangs.org/w/index.php?diff=164327&oldid=164326 * GUAqwq * (+31)
11:27:02 -!- Lord_of_Life has quit (Ping timeout: 256 seconds).
11:27:05 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164328&oldid=164327 * GUAqwq * (+245)
11:27:18 -!- Lord_of_Life has joined.
11:29:50 <esolangs> [[TrackSpan]] M https://esolangs.org/w/index.php?diff=164329&oldid=164328 * GUAqwq * (-2) /* Chip */
11:39:53 <esolangs> [[Talk:TrackSpan]] N https://esolangs.org/w/index.php?oldid=164330 * I am islptng * (+158) Created page with ":what inspired you to make it? norworld and quantum circuitry? ~~~~"
12:24:25 -!- ais523 has quit (Quit: quit).
13:16:08 -!- Everything has joined.
13:22:26 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164331&oldid=164329 * GUAqwq * (+4) /* Chip */
13:39:31 <esolangs> [[Talk:C-Hex]] https://esolangs.org/w/index.php?diff=164332&oldid=75227 * MijiGamin1 * (+176) /* Just use GitHub */ new section
13:39:51 <esolangs> [[Talk:C-Hex]] https://esolangs.org/w/index.php?diff=164333&oldid=164332 * MijiGamin1 * (+22) /* Just use GitHub */
13:56:41 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164334&oldid=164331 * GUAqwq * (+892) /* Inter-chip cooperation */
14:08:54 -!- Sgeo has joined.
14:10:51 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164335&oldid=164334 * GUAqwq * (+745) /* Inter-chip cooperation */
14:18:59 <esolangs> [[TrackSpan]] M https://esolangs.org/w/index.php?diff=164336&oldid=164335 * GUAqwq * (+6) /* Chip */
14:30:39 <esolangs> [[TrackSpan]] M https://esolangs.org/w/index.php?diff=164337&oldid=164336 * GUAqwq * (+15) /* Chip */ Trying to fix my grammar ):
14:35:27 <esolangs> [[Talk:Boo!]] N https://esolangs.org/w/index.php?oldid=164338 * MijiGamin1 * (+206) /* Interpreter */ new section
14:38:28 <esolangs> [[User:MijiGamin1]] M https://esolangs.org/w/index.php?diff=164339&oldid=164285 * MijiGamin1 * (+11) added new language
14:39:20 <esolangs> [[Talk:PP]] M https://esolangs.org/w/index.php?diff=164340&oldid=161339 * MijiGamin1 * (+95) added github link
14:44:21 <esolangs> [[TrackSpan]] M https://esolangs.org/w/index.php?diff=164341&oldid=164337 * GUAqwq * (+134) /* Inter-chip cooperation */ Tryna advance my expressions
14:45:06 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164342&oldid=164341 * GUAqwq * (+27) /* Infinite chips */
14:52:22 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164343&oldid=164342 * GUAqwq * (+207) /* Computational class */ my prediction for the computational class. Proofs are on its way~
15:07:52 -!- wib_jonas has quit (Quit: Client closed).
15:11:08 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164344&oldid=164343 * GUAqwq * (+351) /* Examples */
15:40:35 <esolangs> [[TrackSpan]] https://esolangs.org/w/index.php?diff=164345&oldid=164344 * GUAqwq * (+490) /* Single run of chip */
15:41:52 <esolangs> [[TrackSpan]] M https://esolangs.org/w/index.php?diff=164346&oldid=164345 * GUAqwq * (+5)
15:57:04 <esolangs> [[Eezy]] N https://esolangs.org/w/index.php?oldid=164347 * ChuckEsoteric08 * (+763) Created page with "{{Stub}} '''Eezy''' is an esolang by [[User:ChuckEsoteric08]] based on [[Minsky machine]] that can be easily implemented in other esolangs ==Description== There are two unbounded nonnegative registers, initially zero, and a pointer which points to the first one: +
15:58:23 <esolangs> [[While Pointstack]] https://esolangs.org/w/index.php?diff=164348&oldid=164212 * ChuckEsoteric08 * (+6) /* Computational class */
16:02:38 -!- Everything has quit (Ping timeout: 258 seconds).
16:04:42 -!- Everything has joined.
16:45:17 -!- Everything has quit (Quit: leaving).
17:26:25 <esolangs> [[User:Hotcrystal0/Sandbox]] https://esolangs.org/w/index.php?diff=164349&oldid=163889 * Hotcrystal0 * (+289)
17:48:58 -!- Everything has joined.
18:03:04 <esolangs> [[User:Hotcrystal0/Sandbox]] https://esolangs.org/w/index.php?diff=164350&oldid=164349 * Hotcrystal0 * (+151)
18:17:46 -!- Lord_of_Life has quit (Quit: Laa shay'a waqi'un moutlaq bale kouloun moumkine).
18:21:12 -!- Lord_of_Life has joined.
18:39:19 -!- Everything has quit (Ping timeout: 250 seconds).
18:49:22 -!- chloetax has quit (Quit: Ping timeout (120 seconds)).
18:49:40 -!- chloetax has joined.
19:06:17 -!- moony5 has changed nick to moony.
19:07:55 -!- moony has quit (Quit: leaving).
19:08:29 -!- moony has joined.
19:23:11 <esolangs> [[Talk:Bespoke]] https://esolangs.org/w/index.php?diff=164351&oldid=156406 * Hotcrystal0 * (+428)
19:36:23 -!- ais523 has joined.
21:16:39 -!- chiselfuse has quit (Remote host closed the connection).
21:16:54 -!- chiselfuse has joined.
21:39:41 -!- chiselfuse has quit (Remote host closed the connection).
21:39:56 -!- chiselfuse has joined.
21:58:55 <esolangs> [[Special:Log/newusers]] create * ACBLOX * New user account
22:00:35 -!- chiselfuse has quit (Remote host closed the connection).
22:00:50 -!- chiselfuse has joined.
22:02:38 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=164352&oldid=164323 * ACBLOX * (+134) added my introduction :)
22:05:33 <esolangs> [[User:ACBLOX]] N https://esolangs.org/w/index.php?oldid=164353 * ACBLOX * (+41) Created page with "Hi! I'm ACBLOX. I'm here cuz of truttle1."
22:26:39 <esolangs> [[Esolang talk:Community portal]] https://esolangs.org/w/index.php?diff=164354&oldid=155075 * ACBLOX * (+554) /* Weird esolang I remember using before */ new section
22:28:02 -!- impomatic has joined.
23:10:26 -!- salpynx has joined.
23:10:52 <salpynx> !ztest thioate >(-{}>)%9([-[+]]>)*-1
23:10:52 <zemhill> salpynx.thioate: points -4.86, score 16.83, rank 33/47
23:12:34 <salpynx> !zjoust thioate >(-{}>)%9([-[+]]>)*-1
23:12:34 <zemhill> salpynx.thioate: points -4.86, score 16.83, rank 33/47
23:15:17 <salpynx> (trying to golf a minimal bfjoust strategy that does ok on the hill.)
23:16:29 -!- salpynx has quit (Quit: Leaving).
23:17:43 <ais523> I think that counts as fast rush by modern standards, despite the deco
23:19:20 <ais523> aww, and it beats medium by 4 cycles on one polarity on long tapes, that is incredibly close
23:19:32 <ais523> (but the same thing happens consistently on enough tape lengths to swing the result)
23:19:50 <ais523> medium doesn't care much about beating fast rush because there's hardly any of it on the hill, so I optimised for beating other strategies