Integer Stack Machine

This is still a work in progress. It may be changed in the future.

Integer Stack Machine is a collection of closely-related language variants built on top of the same general concept, with the goal of being non-obvious to decide whether a specific variant is Turing-complete or not.

Feel free to contribute to solving a specific variant, or even add variants.

General Idea

All variants have a single stack of unbounded integers, although the stack starts empty. Each variant allows certain stack instructions. Execution terminates when the stack underflows, or when the end of the program is reached.

Instructions

Instruction Table

Instruction	Effect
:	Duplicate the top integer.
;	Increment the top integer.
-	Negate the top integer.
0	Push 0 onto the stack.
!	Pop the top integer, and discard it.
+	Pop the top two integers, and push their sum.
~	Swap the top two integers.
(	Pop the top integer. If it is 0, continue to the next instruction. Otherwise, jump to the instruction past the matching ).
)	Pop the top integer. If it is 0, jump to the instruction past the matching (. Otherwise, continue to the next instruction.
[]	Has the same effect as () brackets, but the top element is peeked, not popped.

Variants

General Notes

Any constant can be created by starting with 0, incrementing it, and negating it if needed, assuming 0;- are all available.

If : is available and () is as well, then [ and ] can be replaced by :( and :) respectfully. Similarly, using ! and [], () can be represented as [! and ]!.

! can be replaced with (0;), if those instructions are available.

0;-+ can be used to decrement.

Variant 1: Simple

Available instructions: ;-0![]

Decidability Status: Decidable

Proof sketch: Can be converted to a pushdown automata, which is decidable to determine if it halts. (Compilation provided by PkmnQ)

Variant 2: Affine

Available instructions: ;-0+![]

Decidability Status: Decidable

Very condensed and hand-wavy proof: Basically, running 0 creates a new "frame" that cannot communicate with lower frames as long as it is running, while + and ! terminates a frame and returns a value (or not, in the ! case). Then, it is a matter of keeping track of frames, making sure there are no infinite loops, and storing what a frame will return (if anything) if it does return. Once a frame is confirmed to always halt, it must either halt with no value, or with a value (that must be added to the new current frame). If there is no value, entering a frame can be transformed into a jump. If it does return a value, it can be transformed into the proper amount of increments or decrements, before a jump. At some point in this process, assuming we do not find that the program runs forever, we will end up with a one-counter machine, which is decidable.

Variant 3: Duplicative

Available instructions: :;-0+![]

Decidability Status: Unknown

Falsely believed to be undecidable, now unknown.

Variant 4: Micro

Available instructions: ~;-0+!()

Decidability Status: Unknown

Fully unknown. The loss of information through () is quite powerful and balances out the power of ~.

One interesting mini-variant building on Micro is allowing any stack operation that moves around the stack without adding or removing anything.

Variant 5: Swap

Available instructions: ~;-0+![]

Decidability Status: Undecidable

Proof sketch: Have two integers on top of the stack. Use ~ to swap between them as needed. Use ; and 0;-+ to increment and decrement. Use [] to check for 0. As this characterizes a Minsky Machine, this variant is undecidable.

Variant 6: Complete

Available instructions: ~;:-0+![]

Decidability Status: Undecidable

Undecidable for the exact same reason as Swap.