Integer Stack Machine

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

Feel free to contribute to solving a specific variant.

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: Linear

Available instructions: ;-0+!()

Decidability Status: Unknown

Highly likely to be decidable, due to the fact that it is impossible to duplicate information before testing it with ().

Variant 2: Linear+

Available instructions: ;-0+![]

Decidability Status: Unknown

Also likely to be decidable, although this one is less certain, as information is not destroyed when tested.

Variant 3: Duplicative

Available instructions: :;-0+![]

Decidability Status: Unknown

It is unknown whether this is likely to be decidable or not, as : can be used to create comparatively complex functions, but useful functions are hard to create without ~.

Variant 4: 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 5: Swap+

Available instructions: ~;-0+![]

Decidability Status: Undecidable

Follows from Swap being undecidable, as this variant is an extension.

Variant 6: Complete

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

Decidability Status: Undecidable

Undecidable for the exact same reason as Swap+.