# Talk:4

## Proof of Turing completeness

Assuming cells are unbounded (or at least 00 and 01 are), 4 is Turing complete as Portable Minsky Machine Notation can be translated into it.

Cell usage
Cell Use Possible values
00 counter 0 ${\displaystyle \mathbb {Z} _{0}^{+}}$
01 counter 1 ${\displaystyle \mathbb {Z} _{0}^{+}}$
02 constant 01
03 scratch {00, 01}
04 condition {00, 01}

Both counters are unbounded and can be any nonnegative integer.

Incrementation is straightforward.

```inc(c)
add c = c + 02

inc(00) 0000002
inc(01) 0010102
```

Decrementation requires a oneshot loop, to avoid going negative.

Successful decrements (on nonzero counters) set 04, decrements on 0 clear it.

```dec(c)
mul 04 = c * 02
begin 04
sub c = c - 02
end

dec(00) 204000280410000029
dec(01) 204010280410101029
```

While is straightforward, using the condition setting property of the decrement.

```while (test) {code}
dec(test)
begin 04
{code}
dec(test)
end

= dec(test)804{code}dec(test)9
```

If does the same but clears the condition instead of retesting.

```if (test) {code}
dec(test)
begin 04
{code}
set 04 = 00
end

= dec(test)804{code}604009
```

If-else inverts the condition and executes the else first to ensure the temp cell is cleared appropriately. It also clears the conditional to ensure that the if block doesn't execute if the else block did.

```if (test) {ifcode} else {elsecode}
dec(test)
sub 03 = 02 - 04
begin 03
set 03 = 00
{elsecode}
set 04 = 00
end
begin 04
{ifcode}
set 04 = 00
end

= dec(test)103020480360300{elsecode}604009804{ifcode}604009
```

Any arbitrary PMMN program can therefore be translated into a 4 program with the general structure of:

```set 02 = 01
{compiled code}

= 3.60201{compiled code}4
```

stkptr (talk) 20:26, 13 April 2023 (UTC)

If-else blocks are not required for Turing-Completness, because you can simulate ALWCIDFEC using just inc, dec, and while commands --ChuckEsoteric08 (talk) 17:14, 21 April 2023 (UTC)