# Yoctostack

Yoctostack is an esolang made by User:Otesunki (talk) (and further whittled down by User:Quintopia (talk)) based loosely on Minsky machines and operates on a stack.

## Commands

Command Meaning
`+` Increment the top of the stack, then pushes 0.
`-` If the top of the stack is non-zero, decrement it. otherwise (or if the stack is empty), branch.
`%` Swap the top two elements on the stack.
`:` If not branching, restart the program with the current stack.

All other characters are comments, and when the end of the program is reached, the IP goes back to the start.

## Turing completeness proof

First, start with a program written in Portable Minsky Machine Notation that uses 2 counters, for example:

```inc(1)
inc(1)
while (dec(1)) {
inc(0)
inc(0)
inc(0)
}
[...]
```

Label it as state 1:

```(1) inc(1)
inc(1)
while (dec(1)) {
inc(0)
inc(0)
inc(0)
}
[...]
```

Then, use the following table to convert the program into an FSA (combined with two registers)

Find Replace with
`inc(0);` `+-:`
`inc(1);` ```%+-:% ```
```dec(0);
[code A]
```
```if (dec(0)) {
[code A]
} else {
[code A]
}
```
```dec(1);
[code A]
```
```if (dec(1)) {
[code A]
} else {
[code A]
}
```
```(x) [code A]
while([code B]) {
[code C]
}
[code D]
```
```(x) [code A]
goto y
(y) if ([code B]) {
[code C]
goto y
}
goto z
(z) [code D]
```

(where `x`, `y`, and `z` are different numbers)

```if ([code A]) {
[code B]
}
[code C]
```
```if ([code A]) {
[code B]
[code C]
} else {
[code C]
}
```
```(x) [code A]
if ([code B]) {
[code C]
} else {
[code D]
}
[code E]
```
```(x) [code A]
if ([code B]) {
[code C]
[code E]
} else {
[code D]
[code E]
}
```
```(x) [code A]
if ([code B]) {
[code C]
} else {
[code D]
}
```
```(x) [code A]
if ([code B]) {
goto y;
} else {
goto z;
}
(y) [code C]
(z) [code D]
```

(where `x`, `y`, and `z` are different numbers)

```(x) [code A]
if (dec(0)) {
[code B]
} else {
[code C]
}
```
`(x) A-B:+%-%C:`
```(x) [code A]
if (dec(1)) {
[code A]
} else {
[code B]
}
```
`(x) A%-%B:+%-C:`
`goto N;` `+%-%`, repeat `+-:` N times, `:`

Applied to the above example, produces:

```(1) %+-:%%+-:%+%-%+-:+-::
(2) -+%-%+-:+-:+-:::+%-%+%-%+-:+-:+-:+-:::
(3) +-:+-:+-:+%-%+-:+-::
(4) [...]
```

Next, add the following 0 state:

```(0) +%-%+%-%+%-%:::
```

Now we can start writing the final program. Count the total number of states (including 0) and write that many `-`s, followed by the same amount of `:`s, on seperate lines. For the above example:

```-----
:
:
:
:
:
```

Finally, write the code for each state, in backward order (0 on bottom, 1 above it, etc...).

```-----
:[...]
:+-:+-:+-:+%-%+-:+-::
:-+%-%+-:+-:+-:::+%-%+%-%+-:+-:+-:+-:::
:%+-:%%+-:%+%-%+-:+-::
:+%-%+%-%+%-%:::
```