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	$\mathbb {Z} _{0}^{+}$
01	counter 1	$\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)

When I wrote that comment I forgot that this uses only two counters, and ALWCIDFEC has three, so it would not work --ChuckEsoteric08 (talk) 20:36, 31 October 2024 (UTC)