Minimalization of Pxem queha Level 5 user     Posts: 1,206 Threads: 312 Joined: 2016-02-02 #1 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: 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. ::=<, > ::=empty set | {m|m is an integer} ::=nil | m::, where m is an integer to by .t.c.m.c.t last result to by .+ last result to by .c.m.- abs(m+n-m)=abs(n) second previous result to by .t.- finally, to 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. =::| =::1 =::0 =::0|1 When is on top, you have to move to bottom. When 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 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 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', , '.!', , '.x'; checks if times current integer is equal or greater than . second-checker = '.c', , '.!', , '.%', <1>, '.y'; checks if times current integer is divible by . actual-updater = , '.!', , '.\$', '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 , 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 = , '.e' [, '.d', '.pxe']; content-of-file = {, }; command = '.c', , '.!', , '.x', '.c', , '.!', , '.%', <1>, '.y', , '.!', , '.\$', '.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. The following 1 user says Thank You to queha for this post:1 user says Thank You to queha for this post queha Level 5 user     Posts: 1,206 Threads: 312 Joined: 2016-02-02 #2 2020-06-10 06:17:07 Part two. 7. Pxem without .[vfetmd] 7.1. Program structure In Sections 4 and 5, I showed you how Pxem can emulate any Fractran programs, using .[tm] and .e respectively. Remembering any recursive functions can be expressed by structured functions, I thought if the program in 5.1 can be reconstructed. Then I hit on this idea: map current input n to either (a)2n+1 if already updated, or (b)2n otherwise. Using this idea, the pseudo code to do same computation is as follows: Let input be positive integer input to the Fractran program expressed in sequence of command_i where 1<=i<=m and each command_i has two properties: command_i.numerator and command_i.denominator. n<-2*input+1; do{ n<-n-1; for each command_i in 1<=i<=m: if n%2 is 0: if (n/2*command_i.numerator)%command_i.denominator is 0: n<-2*((n/2*command_i.numerator)/command_i.denominator)+1; }while n%2 is 1; 7.2. Actual syntax Finally, the EBNF-noted syntax to generate the program is: program = initial, main, [end]; initial = <2n+1>; n (>0) is the input to the Fractran program. main = '.z', reset, {cmd}, final-check, '.a'; reset = <1>, '.-'; cmd = '.c', <2>, '.%', <1>, '.y', cmd2, 'XX.a'; cmd2 = '.c', <2>, '.\$', , '.!', '.c', , '.x', , '.%', 'XX.a', <1>, '.y', cmd3, 'XX.a'; cmd3 = <2>, '.\$', , '.!', , '.\$', <2>, '.!', <1>, '.+'; final-check = '.c', <2>, '.%', <0>; end = '.d.pxe'; optional. 8. Second conclusion Trying to figure out the way to smaller Pxem more, the following 1+10 commands also can be a set to minimize Pxem: literal, '.c', '.x' '.y', '.z', '.a', '.+', '.-', '.!', '.\$', '.%'. « Next Oldest | Next Newest » 