我怎样才能设计一个识别这种语言的图灵机？ 01^n01^n0

Question

我一直在努力思考如何实际捕获 0 的数量。

我是否需要使用不同的标记来捕获 0 和 1？或者我是否需要创建新的状态来计算 0 的数量？这对我来说似乎不是特别优雅，但我无论如何也看不到精确地数出 3 个 0。另外，当我回溯重新数 1 的数量时，我怎么知道何时到达起点？

Answer 1

我需要使用不同的标记来捕获 0 和 1 吗？

无需不同的标记。您可以通过以受控方式将 1 替换为 0 来擦除 1。

或者我是否需要创建新的状态来计算 0 的数量？

是的。

这对我来说似乎不是特别优雅

这是一个观点问题，但使用不同的状态是正确的方法。

当我回过头来重新数1的数量时

你实际上并没有数1的数量。相反，您将左半部分的每个 1 与右半部分的另一个 1 配对。

...我怎么知道何时到达起点？

在第一个状态中，您将断言第一个字符是 0，因此现在回溯时，您知道当您遇到（第三个）零时，您将到达开头。同样，您将在返回时使用不同的状态来跟踪您已经遇到的零。

您可以分两个阶段解决这个问题：

1. 检查输入是否正好有三个 0，假设输入后面跟着一个空格（不是输入的一部分）

2. 在磁带上来回走动，每次将最外面的 1 替换为 0，直到没有更多的 1 可以这样配对。在这种情况下，您可以断定原件是否具有所需的图案。

第一阶段：

现状	符号读取	要写的符号	头部移动到	新状态
开始	0	复制	对	到第二0
开始	1，空白	复制	对	拒绝
到第二0	0	复制	对	到第三0
到第二0	1	复制	对	到第二0
到第二0	空白	复制	对	拒绝
到第三0	0	复制	对	断言空白
到第三0	1	复制	对	到第三0
到第三0	空白	复制	对	拒绝
断言空白	空白	复制	左	在第三0
断言空白	0,1	复制	左	拒绝

第二阶段从状态

atThird0

开始，头部位于最后的零。

7517

现状	符号读取	要写的符号	头部移动到	新状态
在第三0	0	复制	左	向左擦拭
向左擦拭	0	复制	左	断言0
向左擦拭	1	0	左	向左中心
断言0	0	复制	左	接受
断言0	1	复制	左	拒绝
向左中心	0	复制	左	开始
向左中心	1	复制	左	向左中心
开始	0	复制	对	向右擦拭
开始	1	复制	左	开始
向右擦拭	0	复制	对	拒绝
向右擦拭	1	0	对	到右中
到右中	0	复制	对	结束
到右中	1	复制	对	到右中
结束	0	复制	对	向左擦拭
结束	1	复制	对	结束

这是一个用 JavaScript 实现的图灵机，它是使用上面的转换表运行的。您可以使用输入来看看您会得到什么：

class Turing {
    constructor(transitions, initState) {
        this.states = {}; // Load transition table in dictionary
        for (const {state, read, write, move, nextState} of transitions) {
            const obj = this.states[state] ??= {};
            for (const chr of read) {
                obj[chr] = { write, move: move === "R" ? 1 : -1, nextState };
            }
        }
        this.initState = initState;
    }
    load(tape) {
        this.tape = [...tape];
        this.state = this.initState;
        this.index = 0;
    }
    step() {
        const transaction = this.transaction();
        if (!transaction) return;
        const {write, nextState, move} = transaction;
        if (write) this.tape[this.index] = write;
        this.state = nextState;
        this.index += move;
    }
    transaction() {
        return this.states[this.state]?.[this.tape[this.index] ?? "_"];
    }
    accepted() {
        this.state === "accept";
    }
}

// Create the Turing machine with the transitions and start state
const turing = new Turing([
    { state: "start"         , read: "0"             , move: "R", nextState: "toSecond0" },
    { state: "start"         , read: "1_"            , move: "R", nextState: "reject" },
    { state: "toSecond0"     , read: "0"             , move: "R", nextState: "toThird0" },
    { state: "toSecond0"     , read: "1"             , move: "R", nextState: "toSecond0" },
    { state: "toSecond0"     , read: "_"             , move: "R", nextState: "reject" },
    { state: "toThird0"      , read: "0"             , move: "R", nextState: "assertBlank" }, 
    { state: "toThird0"      , read: "1"             , move: "R", nextState: "toThird0" },
    { state: "toThird0"      , read: "_"             , move: "R", nextState: "reject" },
    { state: "assertBlank"   , read: "_"             , move: "L", nextState: "atThird0" },
    { state: "assertBlank"   , read: "01"            , move: "L", nextState: "reject" },
    { state: "atThird0"      , read: "0"             , move: "L", nextState: "wipeToLeft" },
    { state: "wipeToLeft"    , read: "0"             , move: "L", nextState: "assert0" },
    { state: "wipeToLeft"    , read: "1", write: "0" , move: "L", nextState: "toCenterLeft" },
    { state: "assert0"       , read: "0"             , move: "L", nextState: "accept" },
    { state: "assert0"       , read: "1"             , move: "L", nextState: "reject" }, 
    { state: "toCenterLeft"  , read: "0"             , move: "L", nextState: "toStart" },
    { state: "toCenterLeft"  , read: "1"             , move: "L", nextState: "toCenterLeft" },
    { state: "toStart"       , read: "0"             , move: "R", nextState: "wipeToRight" },
    { state: "toStart"       , read: "1"             , move: "L", nextState: "toStart" },
    { state: "wipeToRight"   , read: "0"             , move: "R", nextState: "reject" },
    { state: "wipeToRight"   , read: "1", write: "0" , move: "R", nextState: "toCenterRight" },
    { state: "toCenterRight" , read: "0"             , move: "R", nextState: "toEnd" },
    { state: "toCenterRight" , read: "1"             , move: "R", nextState: "toCenterRight" },
    { state: "toEnd"         , read: "0"             , move: "L", nextState: "wipeToLeft" },
    { state: "toEnd"         , read: "1"             , move: "R", nextState: "toEnd" }
], "start");

// I/O handling:
const [loadBtn, stepBtn, playBtn] = document.querySelectorAll("button");
const tapeInp = document.querySelector("input");
const tapeOut = document.querySelector("tr");
const stateOut = document.querySelector("span");
let timer;

function load() {
    clearTimeout(timer);
    const tape = "__" + tapeInp.value + "__";
    tapeOut.innerHTML = Array.from(tape, chr => `<td>${chr}<\/td>`).join("");
    turing.load(tapeInp.value);
    display();
}

function step() {
    clearTimeout(timer);
    turing.step();
    display();
}

function play() {
    clearTimeout(timer);
    timer = setTimeout(() => {
        turing.step();
        display();
        play();
    }, 100);
}

function display() {
    stateOut.textContent = turing.state;
    tapeOut.querySelectorAll("td").forEach((cell, i) => {
        cell.textContent = turing.tape[i - 2] ?? "_";
        cell.classList.toggle("selected", i - 2 === turing.index);
    });
}

loadBtn.addEventListener("click", load);
stepBtn.addEventListener("click", step);
playBtn.addEventListener("click", play);
load();

td { border: 1px solid; padding: 5px; }
.selected { background: lightgreen }

Input: <input value="01111011110"> <button>Load</button><br>
Tape:
<table><tr></tr></table>
State: <span></span><br>
<button>Step</button><button>Play</button>