User:Stkptr
Jump to navigation
Jump to search
I'm stack pointer, or stkptr#3840
on Discord.
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.
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 |