The problem is not about programming, but about algorithm. We need to solve |x-y| in unary code on the Turing machine. For example if we have 111 * 11 on the tape. * as a number separator, then we need to leave 1. I understand that when we have a space left or right near the *, the program should remove the * and terminate, but I always get it to work if only the numbers on the right are larger or vice versa. To make the same algorithm work and if the ribbon is 11 * 1 and 1 * 11 does not work.

If it is possible to write a system command:

q1 1 -> q2 _ R

Or with a function table as in the screenshot

CodePudding user response：

I would apply this algorithm:

• Move to the right and ensure that there is a "1" at both sides of the "*"
• Wipe out the rightmost "1" and then walk back to wipe out the leftmost "1"
• Repeat
• When the condition in the first scan is not true, then wipe out the "*" and stop.

This leads to the following transition table:

Here is a little implementation in JavaScript:

class Turing {
    constructor(str, idx=0) {
        this.tape = Array.from(str);
        this.idx = idx;
    }
    read() {
        return this.tape[this.idx] || " ";
    }
    writeAndMove(chr, move) {
        this.tape[this.idx] = chr;
        this.idx  = (move > 0) - (move < 0);
    }
    toString() {
        return this.tape.join("").trim();
    }
    static run(input, transitions, state, endState) {
        const turing = new Turing(input);
        let move, chr;
        while (state !== endState) {
            chr = turing.read();
            [,,chr, move, state] = transitions.find(t => t[0] === state && t[1] === chr);
            turing.writeAndMove(chr, move);
        }
        return turing.toString();
    }
}

const transitions = [
   // STATE      IN   OUT MOVE NEWSTATE
   // --------- ----  ---  --  ----------
    ["start"   , "1", "1",  1, "toright" ],
    ["start"   , "*", " ",  1, "stop"    ],
    ["toright" , "1", "1",  1, "toright" ],
    ["toright" , "*", "*",  1, "toright" ],
    ["toright" , " ", " ", -1, "delright"],
    ["delright", "1", " ", -1, "toleft"  ],
    ["delright", "*", " ", -1, "stop"    ],
    ["toleft"  , "1", "1", -1, "toleft"  ],
    ["toleft"  , "*", "*", -1, "toleft"  ],
    ["toleft"  , " ", " ",  1, "delleft" ],
    ["delleft" , "1", " ",  1, "start"   ],
];

// Demo run
const output = Turing.run("1*111", transitions, "start", "stop");
console.log(output);