User:Stkptr

I'm stack pointer, or stkptr#3840 on Discord.

My computability proofs

Language	Proof	Class	Target
Cratefuck	Talk:Cratefuck	bounded-storage machine	TOGA, Smallfuck
4	Talk:4	Turing complete	PMMN
Tack	Talk:Tack	Turing complete	Minsky machine
AnnoyStack	See page	< Combinational	n/a

Useful proof targets:

• Minsky machine a machine made of two unbounded counters which can be incremented and decremented with conditional execution on decrementation
• Portable Minsky Machine Notation (PMMN) a sort of structured Minsky machine, obviating the need to emulate absolute jumps
• Smallfuck binary no-I/O Brainfuck derivative
• TOGA OISC with an optionally separate code and data space

Todo:

• Prove that a restricted PMMN (sans if, if/else) is Turing complete.

Models of computation

Model	Class	Finite state	Infinite state	Program finity	Looping construct	Conditional execution	Halting
Turing machine	Turing complete	State register	Tape, tape pointer	Finite	Arbitrary conditional	Flow	Arbitrary
P'', Brainfuck	Turing complete	Nesting instruction pointer	Tape, tape pointer	Finite	Arbitrary conditional	Looping flow	Program end
Tag system	Turing complete		Input symbol deque	Finite	Wrapped program	Assignment	Input empty
Cyclic tag, BCT	Turing complete	Instruction pointer	Input bit deque	Finite	Wrapped program	Assignment	Input empty
Minsky machine	Turing complete	Instruction pointer	Pair of counters	Finite	Arbitrary conditional	Flow	Arbitrary
PMMN	Turing complete	Nesting instruction pointer	Pair of counters	Finite	Arbitrary conditional	Flow	Program end
Finite state machine	FSM complete	State register		Finite	Arbitrary conditional	Flow	Arbitrary
Infinite state machine	Turing complete		State register	Infinite	Arbitrary conditional	Flow	Arbitrary
BitBitJump, ByteByteJump	Turing complete		Instruction pointer, hybrid data/instruction space	Finite	Arbitrary	Self-modifying flow	Program end
TOGA	Turing complete	Instruction pointer	Data space	Finite	Arbitrary conditional	Flow	Program end