Talk:Integer Stack Machine

Decidability of Simple

I think Simple can be compiled to a PDA. The PDA stack would be made of three distinct elements which will be represented as 0, 1, and 2. An integer k on the integer stack would be represented on the PDA (from bottom to top) as a 0, abs(k) 1's, with the last one being replaced with a 2 if k is negative (e.g. 0 is represented as 0, 5 is represented as 01111, and -3 is represented as 0112). Then:

• 0 pushes a 0.
• - pops one element. If it's 0, another 0 is pushed back on. If it's 1, a 2 is pushed. If it's 2, a 1 is pushed.
• ; pops one element. If it's 0 or 1, it's pushed back on, and a 1 is pushed on top of it. If it's 2, another element is popped. If that element is 0, another 0 is pushed, while if that element is 1, a 2 is pushed.
• ! pops until it hits a 0.
• [ pops one element. If it's a 0 it jumps to the next state, but if it's a 1 or 2 it jumps to the state just after the matching ]. In any case, the element is also pushed back on immediately.
• ] pops one element. If it's a 1 or 2 it jumps to the next state, but if it's a 0 it jumps to the state just after the matching [. In any case, the element is also pushed back on immediately.

Unfortunately, I don't think this trick works with Affine. Also, I tried doing something similar to the proof sketch Duplicative, but I couldn't figure out division or anything else that would emulate decrementing. –PkmnQ (talk) 13:57, 25 August 2026 (UTC)

The compilation looks good to me. My proof of deciding Affine is almost done, I just need to formalize it to make sure it's correct. --Doors (talk) 17:38, 25 August 2026 (UTC)