01:10:31 <salpynx> In Computation: Finite and Infinite Machines Theorem 14.1-1 phrases the 2 reg machine as having two instructions (another, new set): inc_and_branch, dec_or_branch_if_zero
01:10:46 <salpynx> The next page p.258 remark incorrectly summarises that theorem's addition instruction as: $₁Iⱼ$₂ → $₁Iⱼ₊₁$₂
01:10:53 <salpynx> I think it should be: $₁Iⱼ$₂ → $₁Iⱼ'$₂ i.e. The next instruction is j-prime (jump anywhere), not j+1 (go-to-next)
01:11:05 <salpynx> It's subtle, but it's at literally the final summing up and tying it back to previous results remark of the 2reg machine proof, so being accurate is important.
01:13:11 <salpynx> I guess I'm claiming Minsky got it wrong / oversimplified too, (at least a typographical error) in Computation: Finite and Infinite Machines on p.258.
01:16:26 <salpynx> Big claim, I'm interested to know if people here have access to the book and agree, or can point to something I'm missing.
01:20:54 <salpynx> I'm not saying theorem 14.1-1 is wrong, that seems right with those very specific instruction. The subsequent remark tying it back to improve upon previous results on canonical systems is inaccurate though, at least in the notation used.
01:21:33 <salpynx> (instruction -> instructions)
02:32:33 -!- impomatic has joined.
03:22:05 -!- impomatic has quit (Quit: impomatic).
03:22:45 -!- impomatic has joined.
03:25:35 -!- impomatic has quit (Client Quit).
03:25:58 -!- impomatic has joined.
03:51:03 -!- impomatic has quit (Quit: impomatic).
03:51:23 -!- impomatic has joined.
03:55:34 -!- impomatic has quit (Client Quit).
03:55:56 -!- impomatic has joined.
04:42:18 -!- impomatic has quit (Quit: impomatic).
04:46:42 -!- salpynx has quit (Quit: Client closed).
05:31:16 <esolangs> [[!or]] https://esolangs.org/w/index.php?diff=103174&oldid=102849 * Lon233bcc * (+4)
05:43:43 -!- nikcnaem has joined.
05:58:07 -!- nikcnaem has left.
06:06:09 -!- tromp has joined.
06:34:29 <b_jonas> I think you're misunderstanding something
06:43:02 -!- salpynx has joined.
06:43:55 <salpynx> TC Minsky machines with 3 or more registers have instructions: inc(r), decz(r, n)
06:44:33 <salpynx> 2 reg TC Minsky machines have instructions { inc(r), decz(r, n), go(n) } OR { decz(r, n), incgo(r, n) }
06:45:37 <salpynx> A 2 reg Minsky machine with only the inc(r), decz(r, n) instructions is not TC, but that distinction doesn't seem to emphasised anywhere
06:46:52 <salpynx> well, not that I've seen, and it seems to be a mistake which is frequently made.
06:48:45 <b_jonas> salpynx: but what do those second instructions do and aren't those just assembly macro shortcuts? I don't understand what you mean by their name
06:51:00 <salpynx> sorry, there doesn't seem to be a standard notation for the instructions. I'm trying to stick to Minsky's descriptions, but he uses different notation at different points too
06:51:47 <b_jonas> salpynx: are you sure it's not just a notation to increment a register multiple times in a single go, which you can compile to multiple instructions that increment a counter once (but you have to manage all the state labels)?
06:52:54 <salpynx> inc(r) : Increase register r by one, and go to the next instruction. decz(r, n) : if register r is 0, jump to instruction n, otherwise decrease register r by 1 , which I think is the standard way people think of MMs
06:53:20 <b_jonas> in particular, I read the Aho, Ullman (1972) book, and I'm pretty sure that it gives a proof that two-counter Minsky machines are Turing-complete, because I'm still deliberately choosing to forget that proof, and all I'm remembering that in general it requires another level of exponential slowdown over the exponential slowdown you already have by using Minsky machines instead of machines with more than
06:53:26 <b_jonas> one symbol in the stack alphabets.
06:53:27 <salpynx> go(n) is an unconditional jump, which lets the program go back
06:54:06 <b_jonas> salpynx: that makes sense so far, but what about the other instructions that you mentioned then?
06:55:22 <salpynx> incgo(r, n) = is Increase register r by one and then jump to instruction n unconditionally, which lets you have a advance one instruction, or jump anywhere, forwards or back.
06:55:36 <salpynx> Jumping back is imposible otherwise
06:56:58 <salpynx> Minsky makes a point of a register 'w' in the 5 register machine which is wasted because all it does in allow a go(n) instruction to be made from dec(w, n) -- a guaranteed failed test to let you jump arbitrarily
06:59:07 <salpynx> The thing that struck me is that there are quite a few instruction sets discussed, and they have pretty clear trade offs with the number of registers required to be certain things. You can trade a register for an instruction
07:00:20 <salpynx> I have only been looking at Minsky, esowiki languages, and my own experiments. I'll try to locate the Aho, Ullman (1972) book
07:01:21 <b_jonas> salpynx: wait, so all you're saying is a three-register Minsky machine is still TC if you don't use arbitrary finite state control, but only restricted types of programs that can only jump after trying to pop an empty stack?
07:02:28 <b_jonas> that might be true but I don't think it's very illuminating. the normal Minsky machine that I think of is the one that has arbitrary finite control so it can jump any time, or alternately the increment instruction has one goto target and the decrement instruction has two, or alternately the increment instruction has one goto target and the decrement has two but they're adjacent lines
07:03:27 <salpynx> Well, if I understand what you mean, that's what Minsky is saying ; 3 regs, inc(n), and decz(r, n) , is TC , and I agree and can see how that works, but removing one register breaks it
07:03:27 <b_jonas> but I don't see why that would break any proofs that reduce something *to* Minsky machines, rather than the other direction
07:04:27 <salpynx> The Autopsy TC proof is the most sensible / best one that might be affected http://yiap.nfshost.com/esoteric/autopsy/autopsy.html -- I'm still trying to figure it out
07:05:07 <salpynx> but taking Keymaker's statement at face value "any Minsky Machine program using no more than 2 registers and only INC and DEC instructions (which is, of course, a Turing-complete system)."
07:05:32 <salpynx> it seems like it falls short
07:08:39 <salpynx> Any language that tries to be clever by using minimal (2) unbounded registers , and reduced instruction sets could fall for this -- Minsky Swap seems the prime example.
07:08:48 <b_jonas> wait, sorry, ignore my last line
07:09:50 <salpynx> The proof stuff on the Minsky Swap page is written by me, and I now think it's wrong, because I messed up the instruction set.
07:10:31 <b_jonas> ok, so if you happened to want to prove a language turing-complete by compiling Minksy machines to it, but this reduction is so limited that it can only jump after a failed decrement, then yes, you could have a problem. so are there really any such attempts to proof that aren't trivial to fix, by allowing jumps anywhere, or by allowing more than one symbol on the stacks, or allowing more than two
07:12:12 <salpynx> b_jonas: your Minsky machine conception seems sensible -- jumping at any time is helpful. The problem seems to be there is no clear definitions, and it's not generally a problem unless
07:12:30 <salpynx> someone is trying to be minimal as possible.
07:13:02 <b_jonas> salpynx: ok, I didn't know you'd call the classes with no full finite control Minsky machines
07:13:57 <salpynx> I first ran into problems with PMMN, which, while it makes working with general Minsky machines nice, it can't simulate a TC 2 reg machine (with only internal registers)
07:15:11 <salpynx> I'm just going by what's written in the book Computation: Finite and Infinite Machines, which I thought was the best treatment of it.
07:17:10 <salpynx> I think the root of my frustration + surprise is you can look up the 'fact': How many registers does a Minsky machine require to be TC
07:17:36 <salpynx> and combine it with the 'fact': What instructions does a Minsky machine support?
07:18:21 <salpynx> ... and come to a wrong conclusion that a 2 register machine can be TC with two simple instructions.
07:21:30 <salpynx> Also surprised that there's a lot of work of minimal bf command sets to get to 3 cell bf, but there's less on the Minsky machine version
07:22:18 <salpynx> Minsky tends to call his machine 'program machines', if that helps terminology.
07:26:08 -!- razetime has joined.
07:27:11 <b_jonas> I think I understand now why you mentioned 3-cell Brainfuck: Brainfuck is what popularizes this kind of silly restricted control flow, and while the restriction usually doesn't matter, for variants like BF on a fixed short length tape or Bfjoust it does
07:29:15 <b_jonas> "Minsky tends to call his machine 'program machines'," => I call them counter machines, or 2-counter machines for the case of two counters. I only started to hear "Minsky" here from ais523.
07:30:37 <b_jonas> well ok, not just those. regular expressions are the other thing that popularizes them.
07:34:37 <b_jonas> but even so, brainfuck, regular expressions, and pascal without goto (with only if and while) are restrictions that also limit your branches to properly nest; the one you're talking about only restricts where you can place a jump but allows arbitrary targets there. I guess that's not too weird either, that kind of restriction could arise semi-naturally, but it's not one I'm thinking of often
07:37:48 <b_jonas> I guess I just haven't met these kinds of restrictions recently
07:37:57 <b_jonas> the ones I've seen all allow arbitrary finite control with conditional gotos
07:38:12 <b_jonas> or if-goto-else-gotos or whatnot
07:44:57 -!- Sgeo has quit (Read error: Connection reset by peer).
08:12:31 -!- razetime has quit (Ping timeout: 265 seconds).
08:31:47 -!- razetime has joined.
08:32:40 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
08:42:33 -!- underpantsgnome[ has quit (Quit: Bridge terminating on SIGTERM).
08:47:04 -!- underpantsgnome[ has joined.
08:59:15 -!- __monty__ has joined.
09:10:40 -!- tromp has joined.
09:11:29 <salpynx> https://en.wikipedia.org/wiki/Counter_machine describes a Minsky machine as having 2 instructions: { INC ( r, z ), JZDEC ( r, ztrue, zfalse) }
09:13:58 <salpynx> I think instruction sets { { INC ( r ) , JZDEC ( r, ztrue, zfalse) } or { INC ( r, z ), JZDEC ( r, ztrue ) } would give the same ability, trading arbitrary jumps for sequential ones in two different locations.
09:17:34 <salpynx> These would be TC with 2 registers. Being able to branch to a non-sequential next instruction is crucial for only 2 registers. Adding another register allows arbitrary jumps to be simulated while retaining data storage and a working / testing reg
09:20:30 <salpynx> I'll try and read some of the other literature on Counter machines. It feels like there should be a table of trade-offs for minimal basis machines like this, in terms of branch instructions, allowed values, and number of registers etc
09:23:38 <salpynx> b_jonas: "without goto (with only if and while) " ... Portable Minsky Machine notation has that limitation, and that's what struck me as a problem first, it's quite different from a goto, but if you have an extra register, you can simulate the gotos
09:24:40 -!- salpynx has quit (Quit: Client closed).
10:04:33 -!- wib_jonas has joined.
10:15:09 <wib_jonas> salpynx: there's kind of a distinction though: programming only if and while is somewhat worse than programming with if, while, and calling named functions. but then even just if and while doesn't really restrict control flow if you can set and clear named flag variables anywhere and the if can test any named flag variable. it can just get ugly
10:15:09 <wib_jonas> with a big while{if{}if{}...if{}} state machine loop in the worst case.
10:16:31 <wib_jonas> I have a kind of dual feeling about the control flow thing: I write almost all my programs with just ifs (or if-elses) and whiles and function calls, but despite that I prefer if the language gives me the ability to write gotos, gotos that I then almost never use.
10:17:43 <int-e> . o O ( 99% of my program terminates )
10:18:44 <wib_jonas> int-e: mine don't because for theoretical reasons I have to consider some kinds of diagnosed fatal errors as non-termination
10:20:59 <int-e> Also, what's a fatal error in Turing machines or lambda calculus ;)
10:21:23 <wib_jonas> they may be lies but they make the language composable, and that's what makes the theory and proofs simpler
10:22:09 <wib_jonas> int-e: you may be ";)"ing now but it'll make sense when I reveal how Consumer Society works and why it necessarily has fatal errors
10:22:42 <wib_jonas> (obviously it also has non-termination, just like turing-machines or lambda-calculus)
10:32:26 <wib_jonas> fungot, who invented electrons? J. J. Thomson or Taneb?
10:32:27 <fungot> wib_jonas: ( the least amount of processing, even if their stupidity causes a bunch of
10:33:38 <wib_jonas> fungot: what's the name of the industry concerned by manufacturing electrons? electrics industry or electronics industry?
10:33:38 <fungot> wib_jonas: why doesn't define-macro work in mzscheme
10:34:42 <int-e> `learn Electrons are a blatant violation of the axiom of foundation: Electron contains chrome, and chrome contains electrons.
10:34:45 <HackEso> Learned 'electron': Electrons are a blatant violation of the axiom of foundation: Electron contains chrome, and chrome contains electrons.
10:36:04 -!- genpaku has quit (Remote host closed the connection).
10:36:18 <wib_jonas> I should remove some of my more stupid older wisdoms and use the freed up quota to modify /wisdom/catamorphism
10:36:42 <wib_jonas> I just don't dare to edit it because it already exists and its body is unrelated to the cat fitting through hole joke
10:36:46 <HackEso> A catamorphism is when you recurse too greedily and too deep.
10:39:13 <wib_jonas> nah, even if I free up quota I wouldn't be able to edit this
10:40:41 -!- genpaku has joined.
11:04:26 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
11:10:40 -!- wib_jonas has quit (Quit: Client closed).
12:24:02 <esolangs> [[Befunge]] https://esolangs.org/w/index.php?diff=103175&oldid=102034 * Quintopia * (+194) /* Befunge-93 and Befunge-98 */
12:59:24 -!- wib_jonas has joined.
13:06:11 <wib_jonas> `run /bin/cat /hackenv/bin/$'\x0F' # so this is an invisible command that ... does what exactly?\
13:06:12 <HackEso> #!/bin/bash \ cmd="${@-quote}" \ TIMEFORMAT="real: %lR, user: %lU, sys: %lS" \ shopt -s extglob globstar \ eval -- "$cmd" | rnooodl
13:06:47 <wib_jonas> so it's just like the double and triple backtick?
13:06:53 <HackEso> #!/bin/bash \ cmd="${@-quote}" \ TIMEFORMAT="real: %lR, user: %lU, sys: %lS" \ shopt -s extglob globstar \ eval -- "$cmd" | rnooodl
13:06:56 <HackEso> #!/bin/sh \ export LANG=C; exec bash -O extglob -c "$@" | rnooodl
13:09:10 <wib_jonas> and more backticks overwrites the locale, but differs slightly in other ways. heck.
13:22:34 -!- Lord_of_Life has quit (Quit: Laa shay'a waqi'un moutlaq bale kouloun moumkine).
13:31:26 -!- Lord_of_Life has joined.
13:43:18 -!- impomatic has joined.
13:45:11 <esolangs> [[Main Page]] https://esolangs.org/w/index.php?diff=103176&oldid=102452 * Seemingly Unrelated * (+0)
14:01:24 -!- impomatic has quit (Quit: impomatic).
14:06:20 -!- impomatic has joined.
14:23:55 -!- Sgeo has joined.
14:56:27 -!- impomatic has quit (Quit: impomatic).
14:56:48 -!- impomatic has joined.
15:00:59 -!- impomatic has quit (Client Quit).
15:01:21 -!- impomatic has joined.
15:06:27 -!- impomatic has quit (Quit: impomatic).
15:06:47 -!- impomatic has joined.
15:11:01 -!- impomatic has quit (Client Quit).
15:11:21 -!- impomatic has joined.
15:28:48 -!- wib_jonas has quit (Quit: Client closed).
15:29:45 -!- impomatic has quit (Quit: impomatic).
15:33:49 -!- impomatic has joined.
15:39:44 -!- impomatic has quit (Quit: impomatic).
15:40:04 -!- impomatic has joined.
15:41:15 -!- Noisytoot has quit (Excess Flood).
15:44:15 -!- impomatic has quit (Client Quit).
15:44:35 -!- impomatic has joined.
15:54:44 -!- impomatic has quit (Quit: impomatic).
15:55:04 -!- impomatic has joined.
15:59:15 -!- impomatic has quit (Client Quit).
15:59:27 -!- Noisytoot has joined.
15:59:36 -!- impomatic has joined.
16:04:44 -!- impomatic has quit (Quit: impomatic).
16:05:04 -!- impomatic has joined.
16:09:15 -!- impomatic has quit (Client Quit).
16:09:36 -!- impomatic has joined.
16:11:25 -!- tromp has joined.
16:14:44 -!- impomatic has quit (Quit: impomatic).
16:15:06 -!- impomatic has joined.
16:19:15 -!- impomatic has quit (Client Quit).
16:19:36 -!- impomatic has joined.
17:13:57 <esolangs> [[Main Page]] M https://esolangs.org/w/index.php?diff=103177&oldid=103176 * Seemingly Unrelated * (+20) Rounded corners
17:26:47 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
17:29:44 -!- impomatic has quit (Quit: impomatic).
17:30:04 -!- impomatic has joined.
17:32:54 -!- razetime has quit (Remote host closed the connection).
17:34:15 -!- impomatic has quit (Client Quit).
17:34:36 -!- impomatic has joined.
17:54:06 -!- tromp has joined.
18:04:44 -!- impomatic has quit (Quit: impomatic).
18:05:04 -!- impomatic has joined.
18:09:15 -!- impomatic has quit (Client Quit).
18:09:36 -!- impomatic has joined.
18:14:30 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
18:16:37 -!- tromp has joined.
18:32:23 -!- Noisytoot has quit (Excess Flood).
18:33:21 -!- Noisytoot has joined.
18:45:03 <esolangs> [[UglyBF]] https://esolangs.org/w/index.php?diff=103178&oldid=25413 * Kaveh Yousefi * (+2148) Reformatted and extended the documentation.
18:46:05 -!- Lord_of_Life_ has joined.
18:46:58 <esolangs> [[UglyBF]] https://esolangs.org/w/index.php?diff=103179&oldid=103178 * Kaveh Yousefi * (+164) Added a hyperlink to my implementation of the UglyBF programming language on GitHub.
18:47:09 -!- Lord_of_Life has quit (Ping timeout: 265 seconds).
18:48:49 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
18:49:10 <esolangs> [[UglyBF]] https://esolangs.org/w/index.php?diff=103180&oldid=103179 * Kaveh Yousefi * (+206) Added categories to the page.
18:50:54 <esolangs> [[UglyBF]] https://esolangs.org/w/index.php?diff=103181&oldid=103180 * Kaveh Yousefi * (+103) Added an infinite cat program as a further example.
18:55:59 -!- immibis_ has quit (Ping timeout: 268 seconds).
18:56:17 -!- immibis_ has joined.
18:59:44 -!- impomatic has quit (Quit: impomatic).
19:00:04 -!- impomatic has joined.
19:04:15 -!- impomatic has quit (Client Quit).
19:04:36 -!- impomatic has joined.
19:17:50 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
19:24:44 -!- impomatic has quit (Quit: impomatic).
19:25:04 -!- impomatic has joined.
19:29:15 -!- impomatic has quit (Client Quit).
19:29:35 -!- impomatic has joined.
19:33:58 -!- perlbot has quit (Ping timeout: 244 seconds).
19:35:00 -!- simcop2387 has quit (Ping timeout: 244 seconds).
19:46:03 -!- tromp has joined.
19:56:04 <esolangs> [[Colang]] https://esolangs.org/w/index.php?diff=103182&oldid=103008 * Rdococ * (+973) Update for new syntax
19:59:44 -!- impomatic has quit (Quit: impomatic).
19:59:52 <esolangs> [[Colang]] M https://esolangs.org/w/index.php?diff=103183&oldid=103182 * Rdococ * (+72) Fix inconsistent indentation
20:00:04 -!- impomatic has joined.
20:04:15 -!- impomatic has quit (Client Quit).
20:04:36 -!- impomatic has joined.
20:04:36 -!- FreeFull has joined.
20:15:53 <esolangs> [[Colang]] M https://esolangs.org/w/index.php?diff=103184&oldid=103183 * Rdococ * (+66)
20:16:40 <esolangs> [[Colang]] M https://esolangs.org/w/index.php?diff=103185&oldid=103184 * Rdococ * (+22) /* Sets */
20:17:28 <esolangs> [[Colang]] M https://esolangs.org/w/index.php?diff=103186&oldid=103185 * Rdococ * (+44) Fix code tags
20:27:01 <esolangs> [[UglyBF]] https://esolangs.org/w/index.php?diff=103187&oldid=103181 * Kaveh Yousefi * (+0) Rectified an erroneous instance of < instead of > in the command list.
20:54:44 -!- impomatic has quit (Quit: impomatic).
20:55:06 -!- impomatic has joined.
20:59:15 -!- impomatic has quit (Client Quit).
20:59:36 -!- impomatic has joined.
21:04:44 -!- impomatic has quit (Quit: impomatic).
21:05:04 -!- impomatic has joined.
21:09:15 -!- impomatic has quit (Client Quit).
21:09:36 -!- impomatic has joined.
21:20:38 -!- __monty__ has quit (Quit: leaving).
21:34:44 -!- impomatic has quit (Quit: impomatic).
21:35:04 -!- impomatic has joined.
21:39:15 -!- impomatic has quit (Client Quit).
21:39:35 -!- impomatic has joined.
21:44:01 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
21:45:41 -!- simcop2387 has joined.
21:46:41 -!- perlbot has joined.
21:49:44 -!- impomatic has quit (Quit: impomatic).
21:50:04 -!- impomatic has joined.
21:54:15 -!- impomatic has quit (Client Quit).
21:54:35 -!- impomatic has joined.
22:14:44 -!- impomatic has quit (Quit: impomatic).
22:15:04 -!- impomatic has joined.
22:19:15 -!- impomatic has quit (Client Quit).
22:19:36 -!- impomatic has joined.
23:23:35 -!- impomatic has quit (Quit: impomatic).
23:41:56 <esolangs> [[Optimism]] M https://esolangs.org/w/index.php?diff=103188&oldid=37322 * PythonshellDebugwindow * (+21) Add link and category
23:45:02 <esolangs> [[User:Salpynx/Minimal TC program machines]] N https://esolangs.org/w/index.php?oldid=103189 * Salpynx * (+5248) Starting a table of minimal TC counter machines for comparison
23:53:04 <esolangs> [[User:Salpynx/Minimal TC program machines]] M https://esolangs.org/w/index.php?diff=103190&oldid=103189 * Salpynx * (-3) typo: reducinging the inging