Underflow
Underflow is an esolang created by User:Yayimhere, to make a Pushdown automata able to solve the problem that it is unable to do (the problem with a b and c). it is also turing complete!
Memory
there is an unbounded registry called R, a string called S, two stacks called X and Y, and a boolean called B. If there ever is stack underflow, B will be set to false, and nothing else will happen.
R is started at 0, S is started as the empty string, X and Y are started empty, and B is started as true
Commands
Below are all the commands of Underflow:
| Command | Meaning |
|---|---|
"x" |
Push any single char x to X(if there's multiple char's, then the first one is pushed first as a single char, and so on) |
! |
Pop the top of X |
+ |
Increment R |
{x} |
set S to any string x |
[...][x] |
loops ... n times, where n is equal to how many times the single char x is repeated in S |
[...] |
loops ... R times. if R changes value we can do things. if increased, simply continue until that value is reached, keeping in mind the amount of times the loop has looped. if decreased, do thee same as with increased, however if it increases below the amount of time's the loop has looped, simply stop. |
- |
pops top of Y |
# |
NOT(B) |
= |
sets R to the amount of objects on X |
: |
sets R to the amount of objects on Y |
^ |
pops R objects off of Y |
$ |
set S to all the chars on X, with the bottom char of X being the leftmost of S |
` |
push S to X |
s |
set S to all the chars on Y, with the bottom char of Y being the leftmost of S |
* |
push S to Y |
> |
push the top of X to Y, without popping |
< |
push the top of Y to X, without popping |
S |
pop top of X, and set S to that |
' |
run S as a program in Underflow |
\x |
does not interpret x as a char, however does not ignore it either(so {\}} sets S to })
|
| a space | NOP |
Examples
[+]
Solving that same abc problem:
{the string} [ "a" ][a] [ ! ][b] [ "a" ][a] [!][c] [ "b" ][b] [ ! ][a] [ "b" ][b] [ ! ][c] [ "c" ][c] [ ! ][a] [ "c" ][c] [ ! ][b]
at the end, if B is still true, then there is an equal amount, if not, B becomes false.
Underload to Underflow
here is a proof that Underflow is Turing complete, by providing a translation table from Underload to Underflow(without the Underload S, which is not needed anyways)
| Underload | Underflow |
|---|---|
~ |
>!>!<-<-
|
: |
><-
|
! |
!
|
* |
>!>!s`--
|
(x) |
{x}`
|
a |
"{">!>!{\}\`}*s`---
|
^ |
S'
|
note that within all {}'s, if there is an Underflow command inside, then that command should have a \ before it(however avoid patterns like \\), to avoid errors. an example translation could be:
Underload program: (:^):^
Underflow program: {\>\<\-\S\'}`><-S'
Minimized
As :()^ is the only needed commands for underload, we can see that Underflow only needs ><S'{}\. some smart person can propably minimize this further though.