User:Stkptr

I'm stack pointer, or stkptr on Discord.

My class proofs

Language	Proof	Class	Target	Note
Cratefuck	Talk:Cratefuck	bounded-storage machine	TOGA, Smallfuck	User:Salpynx proved it TC
4	Talk:4	Turing complete	PMMN
Tack	Talk:Tack	Turing complete	Minsky machine
AnnoyStack	See page	< Combinational	n/a
MS-DOS Batch	See page	Turing complete	Tag system

There are a lot more that I've made proofs or sketches for, just don't feel like filling the table.

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:

• Rewrite infinite state machine, the current version is bad
• Prove that a restricted PMMN (sans if, if/else) is Turing complete, this is Structured Minsky
• Smallfuck except its * randomly sets the sell to either 0 or 1 depending on some preset probability. (potentially TC)
  • This has implications for 5050BrainF and BFBWW
  • Ash may fit the bill
• This machine is a server. DO NOT POWER IT DOWN!! seems TC
• ButWhy is almost certainly TC, but it has an interesting subset
  • The subset would be 1 (push 1), pop (pop top bit), dup, cycle (move bottom bit to top), teardown (pop bits until a 0 is peeked), nor (pop top two bits, NOR, push). If enclosed in a full program loop, is it TC?
• Varia is likely TC but a variant where the equations must hold for the entire program could be interesting. Maybe only lines which are valid equalities are run. So B^0=1 always runs regardless of its operation, but something like B+2=5 might only work sometimes.

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