algorithmturing-machinesmarkovmarkov-models

How to define a normal Markov algorithm (NMA) to swap two ternary numbers separated by the symbol "^"?

I'm trying to write a normal Markov algorithm in an emulator to swap two ternary numbers separated by the symbol "^". For example, for input "120^210", the result should be "210^120".

I have tried these rules:

^0 -> 0@^
^1 -> 1@^
^2 -> 2@^
@^0 -> 0@^
@^1 -> 1@^
@^2 -> 2@^
@^ -> ^
^->@
@0 -> ^0
@1 -> ^1
@2 -> ^2
@ -> ^

But it didn't work correctly; I just get "120210^".

Solution

  • When the ^ symbol has moved to the far right, and it is replaced with @, then there are no more rules that apply. For instance, @0, @1, @2 will never occur, so the corresponding rules never activate, and so that @ is replaced back to ^ without having accomplished anything.

    I would suggest to split the task in these phases:

    1. Turn all right side digits to letters (a, b and c)
    2. Move all letters to the left of all (remaining) digits
    3. Turn the letters back to digits

    You could use a distinct marker for each phase to know "where you are".

    Here is a possible implementation in JavaScript of the Markov algorithm, given a set of rules that will apply the above phases:

    // Every rule consists of 3 parts: find, replace, is-terminating-rule
const rules = [
    // Map the right-side digits to letters
    ["^0", "a^", false],
    ["^1", "b^", false],
    ["^2", "c^", false],
    ["^",  "@",  false], // Mapping completed, go to next phase:
    // Move letters left of all digits
    ["0a", "a0", false],
    ["0b", "b0", false],
    ["0c", "c0", false],
    ["0@", "@0", false],
    ["1a", "a1", false],
    ["1b", "b1", false],
    ["1c", "c1", false],
    ["1@", "@1", false],
    ["2a", "a2", false],
    ["2b", "b2", false],
    ["2c", "c2", false],
    ["2@", "@2", false],
    ["@",  "<|", false], // Move completed, go to next phase:
    // Change letters back to digits
    ["a<", "<0", false],
    ["b<", "<1", false],
    ["c<", "<2", false],
    ["<",  "",   false], // Change back completed, go to last phase:
    // Terminating rule
    ["|",  "^",  true],
];

const result = applyRules("210^120", rules);
console.log("final:", result);

// Used Markov algorithm
function applyRules(str, rules) {
    for (let i = 0; i < 5000; i++) { // Avoid infinite loop
        const rule = rules.find(([find]) => str.includes(find)); 
        if (!rule) return str;
        const [find, replace, terminating] = rule;
        str = str.replace(find, replace);
        console.log(`apply rule "${find}"=>"${replace}", result="${str}"`);
        if (terminating) return str;
    }
}