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