00:10:04 <esolangs> [[General blindfolded arithmetic]] https://esolangs.org/w/index.php?diff=154001&oldid=154000 * Stkptr * (+351) /* Equivalence to with / */
00:26:04 <esolangs> [[General blindfolded arithmetic]] M https://esolangs.org/w/index.php?diff=154002&oldid=154001 * Stkptr * (+0) /* Equivalence to with / */
00:26:36 <esolangs> [[General blindfolded arithmetic]] M https://esolangs.org/w/index.php?diff=154003&oldid=154002 * Stkptr * (+0) /* Equivalence to with / */
00:59:43 -!- amby has quit (Quit: so long suckers! i rev up my motorcylce and create a huge cloud of smoke. when the cloud dissipates im lying completely dead on the pavement).
01:00:24 <esolangs> [[General blindfolded arithmetic]] https://esolangs.org/w/index.php?diff=154004&oldid=154003 * Stkptr * (+176) /* Equivalence to with / */
01:04:25 <esolangs> [[General blindfolded arithmetic]] https://esolangs.org/w/index.php?diff=154005&oldid=154004 * Stkptr * (+26) /* with +, -, * (at least FSM) */
01:05:25 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=154006&oldid=153719 * Helpeesl * (+100)
01:05:51 <esolangs> [[Marble maze]] N https://esolangs.org/w/index.php?oldid=154007 * Helpeesl * (+3578) Created page with "== Info == Marble Maze is a multidimensional esolang made by Elijah Hunt(helpeesl) on March 14th 2025 and is inspired by marble mazes, hence the name. ==Commands== {| class="wikitable sortable" |+ Board commands |- ! Commands !! What they do |- | @ || When the prog
01:23:49 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154008&oldid=154007 * Helpeesl * (-1) /* Commands */
01:29:30 -!- FreeFull has quit.
02:22:55 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154009&oldid=154008 * Helpeesl * (-2)
02:26:46 <esolangs> [[Sb]] https://esolangs.org/w/index.php?diff=154010&oldid=153955 * C0ffee * (+25)
02:28:07 <esolangs> [[Sb]] https://esolangs.org/w/index.php?diff=154011&oldid=154010 * C0ffee * (+30)
02:29:07 <esolangs> [[Sb]] https://esolangs.org/w/index.php?diff=154012&oldid=154011 * C0ffee * (+34)
02:30:05 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154013&oldid=154009 * Helpeesl * (+130)
02:30:26 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154014&oldid=154013 * Helpeesl * (+2)
02:31:46 <esolangs> [[Sb]] https://esolangs.org/w/index.php?diff=154015&oldid=154012 * C0ffee * (+90)
02:32:12 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154016&oldid=154014 * Helpeesl * (+5)
02:35:44 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154017&oldid=154016 * Helpeesl * (-88)
02:36:50 <esolangs> [[Sb]] https://esolangs.org/w/index.php?diff=154018&oldid=154015 * C0ffee * (+155)
02:46:04 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154019&oldid=154017 * Helpeesl * (+148)
02:49:43 <esolangs> [[Sb]] https://esolangs.org/w/index.php?diff=154020&oldid=154018 * C0ffee * (+14)
03:04:11 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154021&oldid=154019 * Helpeesl * (+0) /* Commands */
03:04:33 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154022&oldid=154021 * Helpeesl * (-6) /* Truth machine */
03:09:30 <esolangs> [[Language list]] https://esolangs.org/w/index.php?diff=154023&oldid=153980 * Helpeesl * (+18)
03:11:09 <korvo> 100th Coin has uploaded another Mario 3 video: https://www.youtube.com/watch?v=pK7hU-ovUso
03:14:39 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154024&oldid=154022 * Helpeesl * (+14)
03:15:08 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154025&oldid=154024 * Helpeesl * (+9)
03:16:15 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154026&oldid=154025 * Helpeesl * (+18)
03:17:46 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154027&oldid=154026 * Helpeesl * (+23)
03:25:54 -!- chiselfuse has quit (Read error: Connection reset by peer).
03:26:12 -!- chiselfuse has joined.
03:29:03 <esolangs> [[Talk:Marble maze]] N https://esolangs.org/w/index.php?oldid=154028 * Aadenboy * (+364) Created page with "it's quite fun seeing more marble based languages! I'll def try this out later! ~~~~"
03:44:58 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154029&oldid=154027 * Helpeesl * (+70)
03:50:13 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154030&oldid=154029 * Helpeesl * (+92) /* Info */
03:50:45 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154031&oldid=154030 * Helpeesl * (+2)
03:54:11 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154032&oldid=154031 * Helpeesl * (+9)
03:54:57 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154033&oldid=154032 * Helpeesl * (+0)
03:55:18 <esolangs> [[Users:helpeesl]] N https://esolangs.org/w/index.php?oldid=154034 * Helpeesl * (+12) Created page with "Hi Im Eli"
03:56:23 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154035&oldid=154033 * Helpeesl * (-13)
03:56:35 <esolangs> [[User:Helpeesl]] N https://esolangs.org/w/index.php?oldid=154036 * Helpeesl * (+12) Created page with "Hi Im Eli"
03:56:52 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154037&oldid=154035 * Helpeesl * (+12)
03:57:34 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154038&oldid=154037 * Helpeesl * (+0)
03:58:29 <esolangs> [[User:Helpeesl]] https://esolangs.org/w/index.php?diff=154039&oldid=154036 * Helpeesl * (+23)
04:04:06 <esolangs> [[User:Helpeesl]] https://esolangs.org/w/index.php?diff=154040&oldid=154039 * Helpeesl * (+215)
04:29:34 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154041&oldid=154038 * Helpeesl * (-2)
04:32:34 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154042&oldid=154041 * Helpeesl * (+4)
04:34:23 <esolangs> [[User:Helpeesl]] https://esolangs.org/w/index.php?diff=154043&oldid=154040 * Helpeesl * (+16)
04:40:15 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154044&oldid=154042 * Helpeesl * (+1)
04:42:41 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154045&oldid=154044 * Helpeesl * (-5)
04:43:30 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154046&oldid=154045 * Helpeesl * (+1)
04:49:55 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154047&oldid=154046 * Helpeesl * (+49)
04:50:58 <esolangs> [[CJKGolfer]] https://esolangs.org/w/index.php?diff=154048&oldid=153960 * PrySigneToFry * (+60)
04:57:04 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154049&oldid=154047 * Stkptr * (+0) /* Extra stuff */ That's not what the halting problem is
05:05:20 -!- mtm has quit (Ping timeout: 252 seconds).
05:06:45 -!- mtm has joined.
05:27:52 <esolangs> [[Talk:4 bits, 8 bytes]] https://esolangs.org/w/index.php?diff=154050&oldid=137309 * PrySigneToFry * (+924)
05:28:11 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154051&oldid=154049 * Helpeesl * (+204)
05:32:30 <esolangs> [[Marble maze]] https://esolangs.org/w/index.php?diff=154052&oldid=154051 * Helpeesl * (+33)
05:43:00 <esolangs> [[2 Trits, 1 Trybble]] https://esolangs.org/w/index.php?diff=154053&oldid=132850 * PrySigneToFry * (+21)
07:13:10 -!- Lord_of_Life_ has joined.
07:13:21 -!- Lord_of_Life has quit (Ping timeout: 248 seconds).
07:14:32 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
07:36:56 -!- tromp has joined.
07:37:23 -!- tromp has quit (Client Quit).
07:44:44 -!- tromp has joined.
08:03:53 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
08:09:49 -!- tromp has joined.
08:51:56 <esolangs> [[Talk:Brainfuck: Free Version]] https://esolangs.org/w/index.php?diff=154054&oldid=148716 * PrySigneToFry * (+75) /* How can I get the Premium Version?(by PSTF) */ new section
09:23:02 <esolangs> [[Surround notation]] https://esolangs.org/w/index.php?diff=154055&oldid=77702 * PrySigneToFry * (+16)
09:24:52 <esolangs> [[16 bits, 256 bytes]] N https://esolangs.org/w/index.php?oldid=154056 * PrySigneToFry * (+4996) Created page with "16 bits, 256 bytes is an Esolang designed by PSTF, and his new AI friend DeepSeek-R1 671b. It is to be not a joke, just like [[6 bits, 12 bytes]]. It is second x-bits, y-bytes, non-joke langugage. = Overview = 16 bits, 2556 bytes uses a 16 bit CPU and
09:25:43 <esolangs> [[Language list]] https://esolangs.org/w/index.php?diff=154057&oldid=154023 * PrySigneToFry * (+25)
09:26:38 <esolangs> [[Game of Life]] https://esolangs.org/w/index.php?diff=154058&oldid=153993 * PrySigneToFry * (+18)
09:45:27 -!- craigo has joined.
10:19:40 -!- tromp has quit (Read error: Connection reset by peer).
10:41:49 -!- Sgeo has quit (Read error: Connection reset by peer).
11:15:07 <esolangs> [[User talk:None1]] https://esolangs.org/w/index.php?diff=154059&oldid=153489 * None1 * (+376) /* You're currently not active now. */
12:00:34 -!- tromp has joined.
12:04:21 <esolangs> [[User talk:None1]] https://esolangs.org/w/index.php?diff=154060&oldid=154059 * PrySigneToFry * (+1027)
12:15:59 <esolangs> [[Talk:Pyline]] N https://esolangs.org/w/index.php?oldid=154061 * Gilbert189 * (+248) Created page with "== exec? == exec(""" while True: print("If it uses exec, is it Pyline?") # I'm surprised that nobody actually bothered to ask this since 2022. """) --~~~~"
12:19:22 -!- amby has joined.
12:48:12 <esolangs> [[Pyline Classic]] https://esolangs.org/w/index.php?diff=154062&oldid=150172 * PkmnQ * (+46) /* Brainfuck interpreter */ a few walrus operators slipped their way through
12:49:35 <esolangs> [[User talk:None1]] https://esolangs.org/w/index.php?diff=154063&oldid=154060 * I am islptng * (+64) /* You're currently not active now. */
12:50:20 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
13:07:19 -!- FreeFull has joined.
13:17:43 <esolangs> [[User talk:None1]] https://esolangs.org/w/index.php?diff=154064&oldid=154063 * PrySigneToFry * (+242)
13:38:30 <esolangs> [[16 bits, 256 bytes]] https://esolangs.org/w/index.php?diff=154065&oldid=154056 * PrySigneToFry * (+27)
14:04:06 -!- tromp has joined.
15:25:59 <esolangs> [[Pyline Classic]] M https://esolangs.org/w/index.php?diff=154066&oldid=154062 * Corbin * (-20) /* Brainfuck interpreter */ It's now a group project. Your credit will still be preserved in the edit history.
15:29:08 <esolangs> [[Talk:Pyline]] https://esolangs.org/w/index.php?diff=154067&oldid=154061 * Corbin * (+452) /* exec? */ Yes, and.
16:23:37 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
16:50:43 -!- tromp has joined.
17:04:53 -!- mtm has quit (Ping timeout: 248 seconds).
17:06:38 -!- mtm has joined.
17:07:28 <esolangs> [[General blindfolded arithmetic]] https://esolangs.org/w/index.php?diff=154068&oldid=154005 * Stkptr * (+1422) /* with +, -, * (at least FSM) */ It's probably equivalent to the nonnegative integers with + and *
17:09:06 <esolangs> [[Fun 2 code]] https://esolangs.org/w/index.php?diff=154069&oldid=153595 * I am islptng * (-167)
17:11:40 <korvo> Are there any languages that *don't* admit some sort of decomposition? I can't decide if this is a super-deep question or extremely stupid.
17:13:23 <esolangs> [[General blindfolded arithmetic]] https://esolangs.org/w/index.php?diff=154070&oldid=154068 * Stkptr * (+348) /* Removal of - */
17:30:36 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
17:54:15 -!- ais523 has joined.
17:54:27 <ais523> korvo: I suspect the answer to that question may depend on how you define "decomposition"
17:54:54 <korvo> ais523: Allow me to dump a list of examples.
17:55:49 <korvo> In Prolog, a program is a pile of Horn clauses. In many flowchart languages, a program is a pile of basic blocks. In Scheme, a program is a tree.
17:55:54 <ais523> fwiw, I was considering a similar (possibly identical?) problem a while ago, to create a language in which programs had to be written all at once and couldn't be built up from smaller pieces
17:56:29 <korvo> This kind of extremely simple-minded framing is really useful for partial evaluation. But even languages that aren't so simple still have nice decomposition sometimes.
17:57:17 <ais523> there are existing languages based around hash reversal, e.g. any Bubblegum program that's able to access unbounded memory or do any control flow needs to have a specific SHA-256 hash
17:57:19 <korvo> I was considering binding-time analysis in an arbitrary category, and was able to get the BTA for Brainfuck as an immediate consequence, because Brainfuck is almost entirely built from a monoid and the underlying storage is algebraically easy to describe.
17:57:46 <ais523> ah, are you thinking mostly syntactically with the decomposition?
17:58:25 <ais523> I think no-control-flow-and-implicit-loop languages are hard to decompose in that sense, things like Blindfolded Arithmetic or Three Star Programmer – but it's fairly easy to compile into them from programs with more structure
17:58:36 <korvo> Abstract syntax, yes. Don't care about concrete syntax; we typically analyze e.g. C as a basic-block language.
17:59:19 <korvo> TSP should admit a decent BTA. I'm still wrapping my head around Blindfolded Arithmetic and trying to figure out what kind of cryptanalytic tools are useful.
18:00:09 <ais523> well, Blindfolded Arithmetic isn't really encrypted, the main challenge if you have few variables is juggling data storage and control flow
18:01:00 <ais523> Imprecision (which is related to Blindfolded Arithmetic) is much harder due to the way that control flow tends to corrupt the data – I think it's probably still TC but am not usre
18:01:03 <korvo> For example, I think of the Chinese Remainder theorems as cryptanalytic. I didn't learn group theory until after I already learnt the basics of hash cracking.
18:02:11 <korvo> TIL about Bubblegum. Quite funny. I'd be happy to break it, but it'll be a few decades; any feasible attack would be better spent slurping arbitrage out of e.g. the Bitcoin market, and I'd like to retire first.
18:02:57 <ais523> the SHA-256 requirement is basically just there because the language isn't "intended" to write arbitrary programs and the aim was to avoid triggering the TC codepath accidentally, whilst still making itechnically a valid language
18:03:02 <korvo> ...Maybe this is the universe sending me a sign that I should get on that whole Bitcoin thing before somebody else finds it.
18:03:36 <ais523> A Pear Tree does something similar but I intentionally used a hash that wasn't preimage-resistant for that one
18:03:47 <korvo> Oh, really? If that's the case, then SHA-256 was *not* a good choice of hash function. Probably should have chosen something that's more symmetrically hard to assault, like RIPEMD-160.
18:03:53 <ais523> (because people were intended to be able to write arbitrary programs in it)
18:04:39 <ais523> if I had had the idea for Bubblegum rather than Dennis, I would probably have designed it differently
18:04:45 <ais523> different language designers have different styles
18:05:33 <korvo> No worries. When I'm pronoun-dropping, I'm usually intending the ambiguity. I prefer postmortem (or at least post-author-being-here) analysis to be blameless, because the goal isn't to shame but to do better in the future.
18:06:37 <ais523> that said, my main regret with A Pear Tree is that the size of the CRC doesn't scale with the size of the program, making extremely long programs hard to write due to the risk of false positives
18:06:51 <ais523> I didn't realise that was a (theoretical) problem until I'd been using it for a while
18:07:59 <ais523> (also, the interpreter isn't as optimised as I'd like, there's probably a linear-time algorithm for "identify the longest substring with a CRC-32 of 0" due to the way CRCs work, but the reference interpreter is quadratic)
18:08:55 <ais523> anyway, going back to the original question, I think a language which is hard to decompose would also be hard to program in, or to prove TC
18:09:21 <ais523> for something like Feed the Chaos, it is very unclear how storage of arbitrarily large data works, if it works at all
18:09:35 <ais523> and yet you'd need to figure that out in order to be able to decompose programs in a meaningful way
18:10:50 <ais523> (Feed the Chaos is basically a finite-state machine plus a PRNG whose state expands over time, allowing it to "store" arbitrary data, but with no obvious way to extract the data again because doing so would require distinguishing the pseudo-randomness from true randomness using just a finite state machine)
18:15:27 -!- chiselfuse has quit (Remote host closed the connection).
18:15:27 <b_jonas> korvo: one thing you can do in any Turing-complete language is to encrypt most of the code so it can only run if the input gives a specific key for the symmetric encryption, and then it's impossible to find how the code decomposes (or tell anything about what it does) unless you know that key
18:15:43 -!- chiselfuse has joined.
18:16:46 <korvo> b_jonas: So, that's similar to what ais523 did with A Pear Tree and what Dennis did with Bubblegum. I don't think that that's a serious obstacle.
18:16:57 -!- tromp has joined.
18:17:34 <korvo> Maybe it's easiest to see with Bubblegum, where I could assemble a partial evaluator from two components: a partial evaluator for Python and a second-preimage oracle for SHA-256. (Which I should emphatically stress I do *not* have.)
18:18:44 <korvo> I don't know about Feed the Chaos. And maybe that's a good place to draw a line, because it seems like anything we learn about Collatz-style chaos is going to clarify how FtC's programming model would work.
18:20:09 <ais523> I am busy trying to work out what partial evaluation in, say, the I/D machine "conceputally" is
18:20:23 <ais523> it feels like it should be meaningful but I am having trouble defining it
18:20:48 <ais523> (likewise for Blindfolded Arithmetic or Three Star Programmer)
18:22:11 <korvo> Well, it involves a complete modelling of the RAM, because that's where an input parameter would be passed in.
18:22:21 <ais523> I guess the problem is that programs in that sort of language generally rely heavily on invariants in order to keep the behaviour of code contained – the blocks of code are only designed to be meaningful under certain invariants that hold all program (except during startup) and are unlikely to happen by chance
18:23:30 <ais523> Three Star Programmer and the I/D machine both have somewhat difficult startups for the known programming techniques, generally they've been found by writing startup code and then working out how to left-cancel it
18:23:31 <korvo> A partial evaluator for TSP is very simple; it's a function N* × N* → N* sending pairs of lists of nats to a list of nats. The question is how TSP models computable functions.
18:23:48 <ais523> (but the left-cancelling also depends on the invariants)
18:24:28 <ais523> korvo: why are there two lists? program and RAM?
18:25:19 <korvo> ais523: Partial evaluation is always defined relative to an input parameter. They're both programs when we're talking about non-trivial stuff. In TSP's case, yeah, I guess it'd be passed via RAM.
18:26:13 <esolangs> [[General blindfolded arithmetic]] https://esolangs.org/w/index.php?diff=154071&oldid=154070 * Stkptr * (+958) /* Equivalence to with / */
18:26:18 <ais523> it isn't even immediately obvious to me how input works in 3SP
18:26:40 <korvo> It's obvious to me that it *must* work, somehow, or else it can't do something a Turing machine can.
18:27:00 <ais523> it does, but you need an encoding
18:27:19 <ais523> the output encoding in the article is a bit weird, but generic enough that you can usually fit programs around it
18:27:48 <ais523> but an input encoding is harder because in some sense it's tied to the program's memory layout
18:29:35 <ais523> I guess you could just use a sufficiently spaced-out stream of 0 and 1 in RAM (with the addresses forming an arithmetic progression), then a program could add to the cells before reading them in order to move the addresses somewhere that they could handle
18:29:40 <korvo> Well, I figured that the identity encoding is a decent-enough starting choice. And yeah, the program is allowed to non-uniformly depend on the encoding; what matters is that each encoding has its own associated proof of computability.
18:29:56 <ais523> although 0 and 2 might make it easier to write the startup code
18:30:34 <ais523> hmm, now I am wondering whether there are any inherently locked-up RAM initialisation patterns in Three Star Programmer
18:30:43 <korvo> Since one encoding can be transformed into another, there should be an underlying category, so just compose to victory. We're not begging the existence of that composition, I think.
18:30:50 <ais523> i.e. if memory has a certain state, then certain cells will be unchangeable/unreadable
18:31:32 <ais523> (barring degenerate solutions like "initialise all RAM cells with 1, now cell 0 is unwriteable and unreadable")
18:32:16 <korvo> ais523: FWIW I will credit you with achieving the goal in practice; I can't actually imagine sitting down and building any of these partial evaluators. I can't even imagine partial evaluation of BIIA?
18:32:54 <ais523> korvo: I guess my problem is that although the encodings can be transformed into each other given a sufficiently powerful language, 3SP can't do the transformation "from inside" – I suspect the language is insufficiently powerful to read arbitrarily initialised RAM
18:34:31 <ais523> so when I think about a partial evaluator, I'm mostly thinking about it from the language's own point of view
18:35:46 <ais523> I think about Three Star Programmer in terms of a wimpmode in which you can use one, two or three stars – this is much easier to program in, and there's a type of partial evaluation that's much easier to achieve in the wimpmode (if you can assume a memory address is not changed indirectly while a fragment of code is running, and starts with a known value, you can constant-fold)
18:36:44 <korvo> ais523: Oh, okay, I think I confused TSP with something else. All TSP programs run forever, right? So what's an example of a Rice property in TSP?
18:36:53 <ais523> and the primary difficulty is just that 3SP always has *exactly* three levels of indirection, if you want fewer you need to indirect through a RAM cell with a known value – but then constant folding isn't expressible in the language itself, you have to go to the wimpmode
18:37:07 <ais523> korvo: whether a specific cell is ever changed
18:38:01 <korvo> Ugh, okay. Then I was completely wrong with my guess about RAM. Input would have to be simulated by pre-composition.
18:38:20 <korvo> Sorry for the red herring. I was thinking of some other RAM machine.
18:38:28 <ais523> ah, OK – this explains why I was confused
18:39:41 <b_jonas> ais523: this sounds like the complaint that David Madore recently had that if you are writing in untyped lambda calculus (or, say, unlambda without c or d) and you pass your program a lambda calculus function then it can't examine that function without executing it and executing it might result in an endless loop that your program can't break. but the problem here is just the encoding, you should ask
18:39:47 <b_jonas> for an encoded version of the function, and add a lambda expression interpreter to your program. similarly for 3SP, ask for a 3SP machine program and state encoded in a way that you can process with 3SP.
18:39:59 <korvo> No worries. I am not a fan of never-halting machines. In addition to the category of encodings, I see what you're describing now; it's like how a Ferris wheel has a group action but only one egress.
18:40:13 <korvo> I dislike these because e.g. Wolfram likes to sneak in uncomputable bullshit at the exit.
18:40:47 <b_jonas> it's kind of an unfair complaint, because you could just as well say that if you pass your turing machine program a second turing machine by adding its states with the starting state with a known name, then you can't write a turing machine program that examines its argument program
18:40:52 <ais523> korvo: this is a problem that's annoyed me for a very long time (i.e. ensuring that the "artificial halt condition" isn't contributing to computability at all)
18:41:12 <b_jonas> but if you just write an encoding of the turing machine program onto the tape then your program can easily examine it
18:41:44 <ais523> b_jonas: yes – one of the reasons that many of my languages don't have clear I/O is that they inherently require an encoding in order to work and yet the language doesn't naturally enforce a particular encoding
18:42:05 <korvo> ais523: At the same time, e.g. analog computers often converge to a steady state, and that's what we want so that we can take a reading. Sometimes that's how nature computes for us.
18:42:27 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
18:43:13 <korvo> b_jonas: Sure. That distinction is built into partial-evaluation lore; we say that the evaluator always operates on source code or abstract syntax. Folks will often bust out the lore that a TC language's programs "have access to their own source code", too.
18:43:30 <ais523> there are some input schemes for implicit-loop languages that are fairly general, e.g. "you write two programs, X and Y; the interpreter runs X a number of times equal to the input, then runs Y in a loop until the program halts"
18:43:51 <korvo> But what "have access" means is that we use one of Gödel's diagonal lemmas to *bundle* the source code into an encoded package which can be treated as a first-order syntactic literal.
18:43:52 <ais523> that's basically what I did for Tip
18:44:55 <ais523> korvo: this is well-known among esoprogrammers but normally seen from a different point of view, often summarised as "any TC language has a quine" (modulo issues with output encoding)
18:45:09 <b_jonas> don't take "complaint" seriously, I'm misrepresenting what David said a bit there
18:45:19 <korvo> That's also how a DSP is set up, too. The "interpreter" takes a high-level plan X in a language like CSound, emits parameters for a "super-shader" or "effects pipeline" Y, and then runs Y on incoming samples indefinitely.
18:45:31 <ais523> it's possible to define languages with defective output routines that leave them unable to *output* their own source even though they can *calculate* it
18:46:12 <ais523> and that leads to languages with no literal quines, even though they can do arbitrary calculations on their own source
18:46:45 <ais523> but generally that only happens in cases intentionally constructed as counterexampels
18:47:24 -!- tromp has joined.
18:47:29 <korvo> ais523: Yeah. Again, what Gödel actually gave is very specific: given that a language computes a surjection over some output type which encodes source code, if it's TC then there will be a program which encodes itself.
18:47:53 <korvo> And again that's just the Diagonal Lemma. So it really is just a problem of that final exit encoding.
18:48:18 <ais523> anyway, I do get concerned enough about people cheating with "artificial halt conditions" that I generally look for ways to simplify them
18:49:06 <korvo> I think that this is an even sharper answer to my original question. If a language is TC and has a Gödel encoding that it can emit, then there should be a partial evaluator; otherwise, there's many possible obstacles.
18:49:29 <ais523> e.g. I think that Wolfram's 2,3 Turing machine can be made to halt by going off the left edge of a semi-infinite tape (unfortunately it still requires the nonrepeating and somewhat complex input encoding – and although I'm fairly sure I wasn't cheating with that, it is hard to precisely define the reason the encoding isn't cheating)
18:49:45 <korvo> TC-ness ensures that we can do the bundling required to pass input parameters via precomposition.
18:52:27 <ais523> OK, I think the result can be expressed like this – say we have a TC language and an input encoding for it that can express multiple inputs – we can write an interpreter that takes a set of inputs some of which are taken from its input and some of which are hardcoded, plus a hardcoded program, and simulates that program on those inputs – and then because the original language is TC we can write that interpreter in that language
18:52:37 <ais523> and this is a (somewhat degenerately) partially evaluated program
18:53:04 <korvo> Yep, that's all the ingredients of Futamura's first projection.
18:54:14 <ais523> but that doesn't imply to me that the language is necessarily decomposable, although this is partly due to not having a formalised notion of what decomposition means
18:54:46 <int-e> Hmm, where did this start. Decomposition? I suspect that's mostly an artifact of making programming manageable for humans. It's worth noting that pretty much the first thing Alan Turing did with his inscrutable TM formalism (it's a bag of transitions that interact in wild ways) is make it structured so you can have composable parts.
18:54:58 <ais523> I guess it's because the projection treats the program, in effect, as a black box – and the black box is still there (in encoded form) in the output, so nothing's actually been decomposed, just composed around
18:55:20 <korvo> int-e: Oh, I think I was starting with homoiconicity. Prolog and Lisp are both homoiconic; does that make them easier to partially evaluate?
18:55:40 <int-e> Or maybe consider Malbolge? Hmm.
18:55:40 <ais523> korvo: so recently I've been working with Rust procedural macros
18:56:08 <korvo> I think, in this discussion, the answer is that it's easier to write a *syntactically trivial* self-applicable partial evaluator, yes. But writing a good partial evaluator still requires writing an interpreter and doing optimizations.
18:56:14 <ais523> it is a bit of a mess to program in, you basically get a list of tokens that are contained within the macro call (with () [] {} matched for you) and have to output a list of tokens (again with those matched)
18:56:46 <korvo> ais523: Yeah, it's kind of like an expression tree, I guess? I've only used them; I haven't written any.
18:56:47 <ais523> and I'm not sure of the extent to which that's related to homoiconicity
18:57:21 <ais523> korvo: it's less structured than the language as a whole, because it's a token list rather than an AST (i.e. it's been lexed for you but you have to parse it yourself)
18:57:42 <int-e> korvo: I see. But there is a "how do we program" or, closely related, "how do we show TC-ness" angle to this.
18:57:48 <ais523> the requirement for matched brackets/braces/parens is probably just there to ensure that the end of the macro call can be uniquely determined
18:58:13 <ais523> in particular the contents of the macro call don't have to be valid Rust, you can make up your own language as long as it lexes the same way Rust does
18:58:25 <ais523> (same literal syntax and same comment syntax)
18:59:19 <ais523> I have been trying to hand-write parsers for this and it is really frustrating, I would actually rather just have a list of bytes
19:00:06 <ais523> (mostly because you can't ergonomically do matches on the tokens, because you have to call methods on them to work out what sort of token they are and Rust's pattern-matching can't express that succinctly)
19:00:27 <korvo> There's a simple class of parsers that I haven't really seen discussed. Parsing proceeds by string splitting on delimiter tokens. On-wiki, a good example is DIVSPL. In Rust macros, I've used egg's macro interface.
19:01:28 <ais523> I've written those in the past, mostly for scraping output generated from a known program (i.e. the program outputted the output for human consumption and I'm trying to undo the pretty-printing to get at the underlying data in machine-readable form)
19:02:07 <korvo> But yeah, writing this still looks quite nasty: https://github.com/egraphs-good/egg/blob/main/src/macros.rs
19:02:47 <korvo> ais523: I've been researching what to add to Cammy, because I don't want to just slap on an Expr type and call it good. That wasn't fun in Monte.
19:03:10 <int-e> rust macros are a sore spot
19:03:45 <korvo> Monte's homoiconic like Prolog's homoiconic: there's an API that lets you turn expressions into primitives and syntax for (quasi)quotation. But there's always going to be some sort of builtin or opaque expression that can't be examined this way, and we say an interpreter "bottoms out" and calls something native.
19:04:13 <ais523> the motivation behind Rust's system was basically to ensure that macros wouldn't break as new language features were added, which is surprisingly sensible
19:04:48 <ais523> the API is basically just there to be something stable that's technically usable, and they're relying on third-party crates to turn it into something that's actually reasonable in practice
19:05:05 <ais523> (but, I don't like using third-party crates so I've been trying to make it work on my own)
19:05:09 <int-e> . o O ( Leading to Rust's original syn )
19:05:31 <korvo> Yeah. I've used PyMacro for Python, and those macros break between Python 3 minor versions. PyMacro for RPython, which is frozen on Python 2.7's AST, is actually kind of awesome; we added do-notation, etc.
19:11:06 <korvo> So, my idea for Cammy was to *not* have an Expr type. Nor to add trees that are Cammy-shaped, since that's dependent on the number of primitives, which I want to reduce. Awkward future compatibility.
19:12:10 <korvo> Instead I'm thinking of doing like MetaOCaml and adding a two-tiered type theory. So there are arrows X → Y and also lifted arrows [X → Y] along with liftings of all of the builtins and primitives.
19:12:34 <ais523> <korvo> int-e: Oh, I think I was starting with homoiconicity. Prolog and Lisp are both homoiconic; does that make them easier to partially evaluate? ← my guess is that homoiconicity "shouldn't" be relevant because it is in theory an implementation detail
19:13:42 <korvo> This bites in general because we can't lower a lifted arrow without a proof, but in Cammy I can use some abstract nonsense and yoga to lift Cartesian-closedness from the inner curry [X,Y] to the lifted curry [X → Y].
19:13:55 <ais523> it's more relevant in Prolog than in Lisp due to assert and clause; Lisp has eval, which is assert-like, but I don't think it has a commonly used clause
19:14:10 * int-e is looking at https://doc.rust-lang.org/proc_macro/enum.TokenTree.html and still doesn't like it ;-)
19:14:37 <korvo> ais523: I think (read) is the key for Lisp. Like, the trick isn't a nice abstract syntax, but a nice reader for that abstract syntax which separates out everything into evaluated and lifted ("quoted") terms.
19:15:52 <ais523> I guess Tcl is also an interesting case
19:16:42 <ais523> (Wikipedia thinks it's homoiconic, although if so, it's homoiconic in the "reverse" sense to Lisp – notionally it stores everything as strings, including loop bodies, and parses them only when they're just about to be used)
19:16:51 <int-e> adding to ais523's point, you don't have to do partial evaluation at the source code level; you can pick an intermediate language that supports it better
19:18:17 <ais523> actually I guess Underload is in the same boat as Tcl, except that it doesn't have string manipulation primitives so the only ways to operate on strings in Underload are eval ^ and output S
19:18:28 <ais523> and that in turn means that they probably aren't actually strings in a useful sense
19:19:03 <korvo> Execline is another fun example of everything-is-a-string.
19:20:05 <korvo> Actually we don't know if execline is TC! We merely know that it has quines.
19:40:05 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
19:48:38 -!- vyv has joined.
19:57:58 <esolangs> [[Delta Relay]] https://esolangs.org/w/index.php?diff=154072&oldid=142759 * Ais523 * (+11) /* Continuous Delta Relay */ add a couple of words that were omitted from the sentence
20:01:51 -!- tromp has joined.
20:29:06 <esolangs> [[Language list]] M https://esolangs.org/w/index.php?diff=154073&oldid=154057 * Buckets * (+12)
20:29:47 <esolangs> [[User:Buckets]] M https://esolangs.org/w/index.php?diff=154074&oldid=153981 * Buckets * (+11)
20:29:56 <esolangs> [[Esorn]] N https://esolangs.org/w/index.php?oldid=154075 * Buckets * (+850) Created page with "Esorn is an Esoteric programming language created by [[User:Buckets]] in 2020. {| class="wikitable" |- ! Commands !! Instructions |- | a || +1 |- | b || -1 |- | c || Go down 2 lines. |- | d || Set the point. |- | E || Go to the point. |- | f || Ignore the next command onc
20:41:33 -!- vyv has quit (Quit: Konversation terminated!).
20:50:08 <esolangs> [[Pointing]] https://esolangs.org/w/index.php?diff=154076&oldid=153991 * Calculus is fun * (+1215) Simple calculator
21:01:41 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
21:04:41 -!- tromp has joined.
21:05:41 -!- tromp has quit (Client Quit).
21:06:28 -!- tromp has joined.
21:32:34 -!- ais523 has quit (Quit: quit).
22:17:31 <esolangs> [[S*n]] M https://esolangs.org/w/index.php?diff=154077&oldid=153437 * Buckets * (+34)
22:19:32 -!- ajal has joined.
22:19:32 -!- amby has quit (Read error: Connection reset by peer).
22:19:53 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
23:19:17 -!- Sgeo has joined.