Rendered at 00:40:11 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
voidUpdate 3 days ago [-]
> "Can you see a way to transform a string of 8 apples "" into a string of 10 apples ""?"
Am I missing something? The only rules we have are BAB -> AAA and BBB -> BB, and we start with only A, no B, so neither of those rules can be used, so the answer is no?
EDIT: Ah, looks like you cant put emoji in HN comments. Imagine there's apples in there
Phemist 3 days ago [-]
The relations are bi-directional. So you can change AAA -> BAB and BB -> BBB as well.
dhosek 3 days ago [-]
Yeah, that was the secret sauce that left me a bit confused
voidUpdate 3 days ago [-]
Oh, I see. That makes sense
3 days ago [-]
entaloneralie 3 days ago [-]
I'm too scared to leave the comfy world of commutative monoids.
Sesse__ 3 days ago [-]
Is the word problem easier if the monoids are commutative? (Or even trivial? I haven't thought deeply about it.)
hyperpape 3 days ago [-]
I haven't previously thought about this, but I think words over a commutative monoid are equivalent to a vector of non-negative integers, at which point you have vector addition systems, and I believe those are decidable, though still computationally incredibly hard: https://www.quantamagazine.org/an-easy-sounding-problem-yiel....
Sesse__ 3 days ago [-]
Thanks, that's an interesting tidbit!
(The whole thing made me think about applications to SQL query optimizers, although I'm not sure if it's practically useful for anything.)
Am I missing something? The only rules we have are BAB -> AAA and BBB -> BB, and we start with only A, no B, so neither of those rules can be used, so the answer is no?
EDIT: Ah, looks like you cant put emoji in HN comments. Imagine there's apples in there
(The whole thing made me think about applications to SQL query optimizers, although I'm not sure if it's practically useful for anything.)