2020-05-25 12:41:29 (This post was last modified: 2020-05-25 12:50:32 by queha.

*Edit Reason: PS.*) First of all I had already proven that

Pxem is Turing-complete

last summer, but the program I programmed to prove Pxem's Turing-completeness was too large and had some unnecessary parts to prove the computation class.

So I thought if Pxem can be smaller while keeping its computation class.

1. Previous proofs

Last time I proved in two ways. I used 17+1 and 14+1 commands for the proofs respectively, and both of they have I/O commands, which affects to Pxem's computation class because they push and pop some items on stack.

2. What makes Pxem Turing-complete

nk., the designer of Pxem, first thought Pxem cannot be Turing-complete because Pxem has no built-ins for "swap" command as in this blog: swaps two top items of stack, which is represented in following pseudo code:

However, a commenter commented on my article on Qiita posted one can implement such the manipulation with available built-ins. They said .t.c.m.c.t.+.c.m.-.t.-.m is the one (the article is not available anymore because I deleted it), and I traced how it works, as shown below. It was proven that manipulation works properly if and only if (a) two items on top of stack are non-negative values and (b) sum of the two values never overflows.

Now we know how the "swap" manipulation can be done. I considered this, however, does not really affect to Pxem's computational class; Pxem has possibly four features to make Pxem Turing-complete: (a) .w, .x, .y, .z, and .a commands for condition-controlled loops, (b) .v command to reverse order of items stored on a stack, © .t and .m commands to manipulate the heap register, and (d) .e command for recursive call of subroutine. I proved the combinations of (a) and (b), (a) and ©, and (a) and (d) are enough to prove Pxem is still Turing-complete.

3. Pxem without contents of file and a heap

3.1. Emulating tag system

At first I tried to prove in this case. The method I used was to emulate a tag system on Pxem. I referred an example on article on Wikipedia to emulate, which is:

Here is my first version of Pxem program to emulate the program with that input:

I'd like you to notice some parts of the program above are underlined; they indicate the input string to the tag system, the symbols to compare with first one of the currently computed string, and what substrings to append.

Last program consists of some literal strings, .p, .o, .c, .v, .w, .y, .z, .a, .d, and .-, which is 10+1 commands.

3.1.1. Reduction of .y command

You may have noticed some parts of the last program were surrounded with .cc.-ab.-.y and XX.a. That is an idiom to check if top of the stack is equal to the value c and execute what are surrounded with those codes if that condition is true.

Those codes can be replaced with .cc.-.c.w.sab.-XX.-.aab.-.w and XX.-.a respectively. This is, however, inadequate for case when stack is empty. To make the condition true if so, you have to prefix .c.c.-.wXXc.-.a to former code; they push c if stack is empty, and do nothing otherwise.

3.1.2. Reduction of .z command

Last program had a part to halt the program if stack is empty: .c.c.z.d.a. This can be replaced with .c.c.-.w.d.a.

3.1.3. Reduction of .p command

The command is to pop each item of stack to output to stdout, which is represented with following algorithm:

This can be realized with: L.w.o.c.c.-.c.wab.-XX.-.aab.-.a. The program gets out of the loop when the stack gets empty.

3.1.4. Reduction of .s command

On 3.1.1 we used a .s command, but it can be replaced with .wXX.-.a. This works when stack has nothing.

3.1.5. Reduction of I/O commands

If you never hesitate reduction of I/O to reduce Pxem as small as possible, you can replace .o with .s, which is also replaced with longer code, as explained on previous section.

Now, we have 6+1 commands with which replace first program to emulate a tag system: some literal strings, .c, .v, .w, .a, .d, and .-. If you could do more, it may be possible to reduce .d or replace .w and .- commands with .z. I, unfortunately, could not hit on the idea until I thought of emulating another, smaller computation model.

3.2. Emulating cyclic tag system

The next idea I hit on was to emulate a simpler computation model. I emulated an example one from this article: (011, 10, 101) with input "1".

3.2.1. First attempt

Here is my first attempt:

This program used some literals consists of '0' and '1' only, .c, .v, .z, and .a, which is only 4+1 kinds of commands. This program, however, never halts and I wondered, "is what does never halt at all a Turing-complete thing?"

Then I tried to change the program, shown below. This halts when the data string gets empty.

Now the system can halt, but last literal string has a character 'X', and this was a fault.

Later, after thinking of reducing .v command while using .e or a set of .t and .m, I hit on alternative way.

3.2.1.1. Syntax in EBNF

3.2.2. Final version of reducing contents of file and a heap

The alternative way to store data string was based on this grammar-thing.

When <nil> is on top, you have to move to bottom. When <nil> is on top again, then data string is empty, and assumes if "0" is set now.

Here is the final version of my emulator:

This one, actually, reduces one minor behaviour of a command '.c': it originally works as a NOP command if stack is empty, but this, final version, does never use the feature.

3.2.2.1. Syntax in EBNF

4. Pxem without stack-reverser and contents of file

In this and next section I attempted to emulate programs written in Fractran. Unlike to previous section I didn't really try minimalizing Pxem under given restrictions; just tried to find out to prove Turing-completeness under given restrictions.

4.1. Algorithm for emulation of Fractran programming

Because of how Pxem's built-ins works, I had to think of a procedure to execute each Fractran fractions, which is:

Unlike to many other stack-based programming languages, two Pxem built-ins .$ and .% care which value is greater than other, and they divide greater one by less one. For example, if you wanted to do what is like 13/17 on C or several languages in Pxem, you cannot do it directly; when 13 and 17 were popped, 17/13->1 will be pushed back no matter the order of those items is.

4.2. Implementation of Fractran using a heap only

Here is the syntax to generate a program to emulate a Fractran program with an input, in EBNF. The <n> means a manipulation to push the integer value i onto the stack; e.g. <10> has to be replaced with ak.-, 05.-.c.+, or whatever does same.

5. Pxem without heap and stack-reverser

This, however, was easier than previous limitation.

5.1. Implementation of Fractran using content of file only

<n>, where n is an integer value, is a manipulation to push the value onto the stack, as I said on 4.2. Here is the syntax to emulate a fractran program with an input:

When the program ends, the final value is on top of stack.

6. Conclusion

Now I have shown how

Pxem is Turing-complete,

with kinda formaler and smaller proofs, publishing online for the first time.

I don't think anyone really, really, really, care for this great blog because Pxem, the esolang I asked original designer nk. to bring it back, is insufficiently known today.

I am very glad and proud of revealing nk. how Pxem can be Turing-complete.

Acknowledgment

I would like to express my very great appreciation to nk., for designing, giving birth, and bringing back Pxem, an esolang.

PS

I forgot to write if .[wxyza] commands cannot be omitted.

Pxem is Turing-complete

last summer, but the program I programmed to prove Pxem's Turing-completeness was too large and had some unnecessary parts to prove the computation class.

So I thought if Pxem can be smaller while keeping its computation class.

1. Previous proofs

Last time I proved in two ways. I used 17+1 and 14+1 commands for the proofs respectively, and both of they have I/O commands, which affects to Pxem's computation class because they push and pop some items on stack.

2. What makes Pxem Turing-complete

nk., the designer of Pxem, first thought Pxem cannot be Turing-complete because Pxem has no built-ins for "swap" command as in this blog: swaps two top items of stack, which is represented in following pseudo code:

- a<-Pop
- b<-Pop
- Push(a)
- Push(b)

However, a commenter commented on my article on Qiita posted one can implement such the manipulation with available built-ins. They said .t.c.m.c.t.+.c.m.-.t.-.m is the one (the article is not available anymore because I deleted it), and I traced how it works, as shown below. It was proven that manipulation works properly if and only if (a) two items on top of stack are non-negative values and (b) sum of the two values never overflows.

- <A set of registers>::=<<Heap>, <Stack>>
- <Heap>::=empty set | {m|m is an integer}
- <Stack>::=nil | m::<Stack>, where m is an integer

- <heap, m::n::R> to <m, m::n::n::R> by .t.c.m.c.t
- last result to <m, (m+n)::n::R> by .+
- last result to <m, abs(m+n-m)::(m+n)::n::R> by .c.m.-
- abs(m+n-m)=abs(n)
- second previous result to <abs(n), abs(m)::R> by .t.-
- finally, to <abs(n), abs(n)::abs(m)::R> by .m

Now we know how the "swap" manipulation can be done. I considered this, however, does not really affect to Pxem's computational class; Pxem has possibly four features to make Pxem Turing-complete: (a) .w, .x, .y, .z, and .a commands for condition-controlled loops, (b) .v command to reverse order of items stored on a stack, © .t and .m commands to manipulate the heap register, and (d) .e command for recursive call of subroutine. I proved the combinations of (a) and (b), (a) and ©, and (a) and (d) are enough to prove Pxem is still Turing-complete.

3. Pxem without contents of file and a heap

3.1. Emulating tag system

At first I tried to prove in this case. The method I used was to emulate a tag system on Pxem. I referred an example on article on Wikipedia to emulate, which is:

- m=2
- initial word is baa
- a->ccbaH
- b->cca
- c->cc
- H halts the program

Here is my first version of Pxem program to emulate the program with that input:

- Filename: Qbaa.w.cH.-ab.-.y.p.d.a.ca.-ab.-.y.o.c.c.z.d.a.o.vHabcc.vXX.a.cb.-ab.-.y.o.c.c.z.d.a.o.vacc.vXX.a.cc.-ab.y.o.c.c.z.d.a.o.vcc.vXX.aQ.a.pxe

I'd like you to notice some parts of the program above are underlined; they indicate the input string to the tag system, the symbols to compare with first one of the currently computed string, and what substrings to append.

Last program consists of some literal strings, .p, .o, .c, .v, .w, .y, .z, .a, .d, and .-, which is 10+1 commands.

3.1.1. Reduction of .y command

You may have noticed some parts of the last program were surrounded with .cc.-ab.-.y and XX.a. That is an idiom to check if top of the stack is equal to the value c and execute what are surrounded with those codes if that condition is true.

Those codes can be replaced with .cc.-.c.w.sab.-XX.-.aab.-.w and XX.-.a respectively. This is, however, inadequate for case when stack is empty. To make the condition true if so, you have to prefix .c.c.-.wXXc.-.a to former code; they push c if stack is empty, and do nothing otherwise.

3.1.2. Reduction of .z command

Last program had a part to halt the program if stack is empty: .c.c.z.d.a. This can be replaced with .c.c.-.w.d.a.

3.1.3. Reduction of .p command

The command is to pop each item of stack to output to stdout, which is represented with following algorithm:

- Check if stack is not empty
- If so, end this algorithm
- Pop and output the character
- Go to step 1

This can be realized with: L.w.o.c.c.-.c.wab.-XX.-.aab.-.a. The program gets out of the loop when the stack gets empty.

3.1.4. Reduction of .s command

On 3.1.1 we used a .s command, but it can be replaced with .wXX.-.a. This works when stack has nothing.

3.1.5. Reduction of I/O commands

If you never hesitate reduction of I/O to reduce Pxem as small as possible, you can replace .o with .s, which is also replaced with longer code, as explained on previous section.

Now, we have 6+1 commands with which replace first program to emulate a tag system: some literal strings, .c, .v, .w, .a, .d, and .-. If you could do more, it may be possible to reduce .d or replace .w and .- commands with .z. I, unfortunately, could not hit on the idea until I thought of emulating another, smaller computation model.

3.2. Emulating cyclic tag system

The next idea I hit on was to emulate a simpler computation model. I emulated an example one from this article: (011, 10, 101) with input "1".

3.2.1. First attempt

Here is my first attempt:

- Filename: 011.z.c.c.z000.a0.z11.v110.v.a.c.c.z000.a0.z11.v01.v.a.c.c.z000.a0.z11.v101.v.a01.a.pxe, however you may omit last .pxe.

This program used some literals consists of '0' and '1' only, .c, .v, .z, and .a, which is only 4+1 kinds of commands. This program, however, never halts and I wondered, "is what does never halt at all a Turing-complete thing?"

Then I tried to change the program, shown below. This halts when the data string gets empty.

- Filename: 011.z.c.c.z000.a0.z.v110.v11.a.c.c.z000.a0.z.v01.v11.a.c.c.z000.a0.z.v101.v11.a.c.c.z00X.a.cX.a.d.pxe, however you may omit last .d.pxe.

Now the system can halt, but last literal string has a character 'X', and this was a fault.

Later, after thinking of reducing .v command while using .e or a set of .t and .m, I hit on alternative way.

3.2.1.1. Syntax in EBNF

- Filename = init, main [, omitable ];
- init = dummy, data-string;
- dummy = '01';
- data-string = data-bit {, data-bit };
- data-bit = '0' | '1';
- main = '.z', { command }, exiter, '.a';
- command = empty-checker, actual-command;
- empty-checker = '.c.c.z000.a'; actually stores a bit '0' if empty
- actual-command = '0.z.v', data-string-reversed, '.v11.a';
- data-string-reversed = { data-bit }, data-bit;
- exiter = '.c.c.z00X.a.cX';
- omitable = '.d.pxe';

3.2.2. Final version of reducing contents of file and a heap

The alternative way to store data string was based on this grammar-thing.

- <data-string>=::<nil>|<data-bit> <data-string>
- <nil>=::1
- <data-bit>=::0 <actual-data-bit>
- <actual-data-bit>=::0|1

When <nil> is on top, you have to move to bottom. When <nil> is on top again, then data string is empty, and assumes if "0" is set now.

Here is the final version of my emulator:

- Filename: 01011.z.c0.z.s.v1.v.c0.z0000.a00.a.s0.zv101000.v00.a.c0.z.s.v1.v.c0.z0000.a00.a.s0.z.v0010.v00.a.c0.z.s.v1.v.c0.z0000.a00.a.s0.z.v100010.v00.a.c0.z.s.v1.v00.a.c1.a.d.pxe but each .s must be replaced with 1.z.a and .d.pxe as the extension of the file can be omitted.

This one, actually, reduces one minor behaviour of a command '.c': it originally works as a NOP command if stack is empty, but this, final version, does never use the feature.

3.2.2.1. Syntax in EBNF

- Filename = init, main [, omitable ];
- init = dummy, data-string;
- dummy = '01';
- data-string = { data-bit }, end-of-string;
- data-bit = '0', actual-bit;
- actual-bit = '0' | '1';
- end-of-string = '1';
- main = '.z', command, exiter, '.a';
- command = empty-checker, actual-command;
- empty-checker = 'c0.z1.z.a.v1.v.c0.z0000.a'; If empty, data string is updated with a '0' string.
- actual-command = '00.a1.z.a0.zv', pushing-data-string-reversed, '.v00.a';
- pushing-data-string-reversed = { actual-bit, '0' };
- exiter = '.c0.z1.z.a.v1.v00.a.c1';
- omitable = '.d.pxe';

4. Pxem without stack-reverser and contents of file

In this and next section I attempted to emulate programs written in Fractran. Unlike to previous section I didn't really try minimalizing Pxem under given restrictions; just tried to find out to prove Turing-completeness under given restrictions.

4.1. Algorithm for emulation of Fractran programming

Because of how Pxem's built-ins works, I had to think of a procedure to execute each Fractran fractions, which is:

- Let n be current value
- Check if numerator times n is greater than or equal to denominator (or alternatively numerator times n is greater than denominator minus one)
- If not, go to next fraction
- Check if numerator times n modulo denominator is NOT zero
- If equals zero, go to next fraction
- Let n be numerator times n divided by denominator
- Go to first fraction

Unlike to many other stack-based programming languages, two Pxem built-ins .$ and .% care which value is greater than other, and they divide greater one by less one. For example, if you wanted to do what is like 13/17 on C or several languages in Pxem, you cannot do it directly; when 13 and 17 were popped, 17/13->1 will be pushed back no matter the order of those items is.

4.2. Implementation of Fractran using a heap only

Here is the syntax to generate a program to emulate a Fractran program with an input, in EBNF. The <n> means a manipulation to push the integer value i onto the stack; e.g. <10> has to be replaced with ak.-, 05.-.c.+, or whatever does same.

- filename = initializer, main [, extension ];
- initializer = <n>,<n'>,<n''>; n is the input to a Fractran program to be emulated, and n' and n'' must be two different values.
- main = loop-begin, loop, loop-end;
- loop-begin = '.z';
- loop-end = '.mF.a';
- loop = set-false, command {, check-done, command, exit-check-done };
- set-false = 'F.t';
- check-done = '.mF.-', <1>, '.y';
- exit-check-done = 'XX.a';
- command = first-checker, second-checker, actual-updater, end-command;
- first-checker = '.c', <numerator>, '.!', <denominator minus 1>, '.x'; checks if <numerator> times current integer is equal or greater than <denominator>.
- second-checker = '.c', <numerator>, '.!', <denominator>, '.%', <1>, '.y'; checks if <numerator> times current integer is divible by <denominator>.
- actual-updater = <numerator>, '.!', <denominator>, '.$', 'T.t', 'XX.a', 'XX.a'; the 'T.t' is to have the heap remember that an update was done.
- extension = '.d.pxe'; actual extension is '.pxe'.

5. Pxem without heap and stack-reverser

This, however, was easier than previous limitation.

5.1. Implementation of Fractran using content of file only

<n>, where n is an integer value, is a manipulation to push the value onto the stack, as I said on 4.2. Here is the syntax to emulate a fractran program with an input:

- filename = <input>, '.e' [, '.d', '.pxe'];
- content-of-file = <command> {, <command> };
- command = '.c', <numerator>, '.!', <denominator minus 1>, '.x', '.c', <numerator>, '.!', <denominator>, '.%', <1>, '.y', <numerator>, '.!', <denominator>, '.$', '.e.d', 'XX.a', 'XX.a';

When the program ends, the final value is on top of stack.

6. Conclusion

Now I have shown how

Pxem is Turing-complete,

with kinda formaler and smaller proofs, publishing online for the first time.

I don't think anyone really, really, really, care for this great blog because Pxem, the esolang I asked original designer nk. to bring it back, is insufficiently known today.

I am very glad and proud of revealing nk. how Pxem can be Turing-complete.

Acknowledgment

I would like to express my very great appreciation to nk., for designing, giving birth, and bringing back Pxem, an esolang.

PS

I forgot to write if .[wxyza] commands cannot be omitted.