User:Stkptr

From Esolang
Jump to navigation Jump to search

I'm stack pointer, or stkptr 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
MS-DOS Batch See page Turing complete Tag system

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