User:Stkptr
Jump to navigation
Jump to search
I'm stack pointer, or stkptr on Discord. I spend most of my time here trying to prove the computational class of languages, or writing up common theory.
Missing languages (if you're reading this, I implore you to write one of these up):
- Node code https://github.com/Stick404/Node_Code
- Paka https://github.com/FastVM/paka
- Dataflow
- Concatenative calculus
What I've done
Languages I've formulated:
Models I've described:
Languages which I've written proofs for (some of these are on the respective talk pages):
- Cratefuck (finite state automata) from Smallfuck and TOGA, but was outdone by User:Salpynx (Turing complete) from counter machines
- 4 (TC) from counter machines
- Tack (TC) from multiplicative machines
- MS-DOS Batch (TC) from tag
- Signals (TC) from counter machines (proof not provided yet)
- qoob (TC) from tag
- MSFE++ (TC) from 3-cell brainfuck
- T-rexes (TC) from Smallfuck, with help from User:Otesunki
- (1, 0)-L-systems (TC) from tag (I haven't published the compiler yet)
- Rotary (TC) from bitwise cyclic tag
- G85 (TC) from qoob
- Likely also others that I'm forgetting
I've also touched on the class of:
- AnnoyStack (incapable of computation)
- ◧◨ (TC), the proof already existed, but I explained how it worked
- And lots of others
Theory pages I've written:
- Markov algorithm
- Nondeterministic
- Formal grammar
- Lag system
- L-system
- Clockwise Turing machine
- Universal machine
- Total function
- Diophantine equation
- Oracle machine
- Metalanguage
- Binary tag
- Concatenative calculus
Language pages I wrote:
Todo
- 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
- qoob but instead of 1 theres * which dequeues, inverts, enqueues (call it qoop)
- May have implications for Queuenanimous
- 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?
- The subset would be
- 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.
- Fackward might implement concatenative calculus
- Verify the compiler on Braincursion
Wanted pages:
- Shepherdson-Sturgis machine see Lag system, ref https://dl.acm.org/doi/10.1145/321160.321170
- semi-Thue system -> Formal grammar
- Dynamical system
- Belts a computational model based on factory game conveyor belts, it's Turing complete with a single repeated pattern
Total rewrite needed:
- General blindfolded arithmetic which models discrete time dynamical systems, more references needed
Additions:
- L-system parametric grammars, which are quite Turing complete
- Post canonical system
- Post normal system
- User:stkptr/sandbox needs a name and some improvements
- Signals needs that proof
- Formal grammar needs Thue stuff, references, normal forms (incl. Pentonnen which should be equivalent to (1, 0)-L)
- Regular expression, what extensions are non-regular? Is lookaround truly regular? What is the reduction scheme?
- Echo Tag should have a compiler on the page
Placing this here for convenience:
{| class=wikitable
|+ title
! head1
! head2 !! head3
|-
| cell 0 || cell 1 || cell 2
|-
| cell 0 || cell 1 || cell 2
|-
| cell 0 || cell 1 || cell 2
|}