// //////////////////////////////////////////////////////////////////////// // This is the inner, simulated counter automaton used to check whether the // 2^n part has the same parity length in binary and ternary. // In the full single variable automaton code given later this will have // been encoded using Gödel numbering, and embedded as "step 3". // There are three counters v2, v3 and v5 represented in the outer automaton // by the exponents of the primes 2, 3 and 5, respectively. // Any exponents of other primes are irrelevant to the working of the inner // automaton. // v2 initially starts as n, v3 and v5 as 0. // The first part decrements v2 until it is zero, // constructing 2^n in the process. If 2^n was even, we will then pass to even2 // with 2^n in v3; If 2^n was odd, we will pass to odd2 with 2^n in v5. INC v3 // Set v3 to 1 = 2^0 to start with. even1: // We have decremented v2 an even number of times so far. // 2^decremented amount is in v3. JZ v2, odd2 DEC v2 dup3to5: JZ v3, odd1 DEC v3 INC v5 INC v5 GOTO dup3to5 odd1: // We have decremented v2 an odd number of times so far. // 2^decremented amount is in v5. JZ v2, even2 DEC v2 dup5to3: JZ v5, even1 DEC v5 INC v3 INC v3 GOTO dup5to3 // The second part checks whether 2^n, which starts out in v3 or v5 according // to whether the binary length of 2^n (i.e. n+1) was odd or even odd2: // v3 needs to have odd ternary length to accept. // It is simplest to consider 0 to have even length in both // binary and ternary. This works out as long as we're // consistent. JZ v3, reject trisect3to5: DEC v3 DEC v3 JZ v3, even2 DEC v3 INC v5 GOTO trisect3to5 even2: // v5 needs to have even ternary length to accept JZ v5, accept trisect5to3: DEC v5 DEC v5 JZ v5, odd2 DEC v5 INC v3 GOTO trisect5to3 accept: HALT Accept reject: HALT Reject // End code of inner simulated automaton // ///////////////////////////////////// // ///////////////////////////////////////////////////////////////////// // Single variable automaton which accepts the set // { 2^n | length of 2^n in binary == length of 2^n in ternary (mod 2) } // "Step 1" (Why did I number this with the others?): // Assume that the input to be tested is in the single variable c, and // imagine c = 2^n * a, where a is odd. (OK it could be zero, we'll test that.) // "Step 2": Check enough about the input to ensure step 3 can do its // calculations. // Check that the input is not zero JZ reject // Check that 3 is not a factor of the input DIV 3, reject, check3.f1, check3.f2 check3.f1: MUL 3 GOTO check3.i1 check3.f2: MUL 3 INC check3.i1: INC // Check that 5 is not a factor of the input DIV 5, reject, check5.f1, check5.f2, check5.f3, check5.f4 check5.f1: MUL 5 GOTO check5.i1 check5.f2: MUL 5 GOTO check5.i2 check5.f3: MUL 5 GOTO check5.i3 check5.f4: MUL 5 INC check5.i3: INC check5.i2: INC check5.i1: INC // "Step 3": Simulate the previously given 3-counter automaton by using the // exponents of the primes 2,3 and 5 in the variable c as the counter. // That is, at each simulated command c = 2^v2 * 3^v3 * 5^v5 * a, where a is // some possible product of primes _other_ than 2, 3 and 5 which we need // not be concerned with until step 4, except that it will be preserved // until then. MUL 3 even1: DIV 2, dup3to5, even1.f1 even1.f1: MUL 2 INC GOTO odd2 dup3to5: DIV 3, dup3to5.a, dup3to5.f1 dup3to5.f2 dup3to5.f1: MUL 3 GOTO dup3to5.i1 dup3to5.f2: MUL 3 INC dup3to5.i1: INC GOTO odd1 dup3to5.a: MUL 25 GOTO dup3to5 odd1: DIV 2, dup5to3, odd1.f1 odd1.f1: MUL 2 INC GOTO even2 dup5to3: DIV 5, dup5to3.a, dup5to3.f1, dup5to3.f2, dup5to3.f3, dup5to3.f4 dup5to3.f1: MUL 5 GOTO dup5to3.i1 dup5to3.f2: MUL 5 GOTO dup5to3.i2 dup5to3.f3: MUL 5 GOTO dup5to3.i3 dup5to3.f4: MUL 5 INC dup5to3.i3: INC dup5to3.i2: INC dup5to3.i1: INC GOTO even1 dup5to3.a: MUL 9 GOTO dup5to3 odd2: DIV 3, ts3to5.a, reject, reject trisect3to5: DIV 3, ts3to5.a, ts3to5.f1, ts3to5.f2 ts3to5.a: DIV 3, ts3to5.b, ts3to5.f1, ts3to5.f2 ts3to5.b: DIV 3, ts3to5.c, ts3to5.f1, ts3to5.f2 ts3to5.c: MUL 5 GOTO trisect3to5 ts3to5.f1: MUL 3 GOTO ts3to5.i1 ts3to5.f2: MUL 3 INC ts3to5.i1: INC // GOTO even2 even2: DIV 5, ts5to3.a, even2.f1, even2.f2, even2.f3, even2.f4 even2.f1: MUL 5 GOTO even2.i1 even2.f2: MUL 5 GOTO even2.i2 even2.f3: MUL 5 GOTO even2.i3 even2.f4: MUL 5 INC even2.i3: INC even2.i2: INC even2.i1: INC // The simulated automaton has accepted, go to final checks for the outer one. GOTO step4 trisect5to3: DIV 5, ts5to3.a, ts5to3.f1, ts5to3.f2, ts5to3.f3, ts5to3.f4 ts5to3.a: DIV 5, ts5to3.b, ts5to3.f1, ts5to3.f2, ts5to3.f3, ts5to3.f4 ts5to3.b: DIV 5, ts5to3.c, ts5to3.f1, ts5to3.f2, ts5to3.f3, ts5to3.f4 ts5to3.c: MUL 3 GOTO trisect5to3 ts5to3.f1: MUL 5 GOTO ts5to3.i1 ts5to3.f2: MUL 5 GOTO ts5to3.i2 ts5to3.f3: MUL 5 GOTO ts5to3.i3 ts5to3.f4: MUL 5 INC ts5to3.i3: INC ts5to3.i2: INC ts5to3.i1: INC GOTO odd2 // "Step 4": The simulated automaton has accepted successfully. It remains // to check whether there were any prime factors other than 2, 3 or 5 in // the input. (The simulated automaton doesn't touch these.) // Conveniently the particular simulated automaton used here only accepts when // all its counters are zero, so the final test consists simply of checking // that the variable of the outer automaton is now 1. // More generally we would have needed to divide out any unzeroed counters from // step 3 first. step4: DEC // BTW it cannot be zero before this. JZ accept reject: HALT Reject accept: HALT Accept // I guess we're finished. // ///////////////////////