用于检查回文的图灵机转换表

Question

使用图灵机。如果机器的输入磁带由一串 0 和 1 组成，鉴于机器的输出应该分别为 1 或 0，具体取决于它是否是回文，您将如何解决该问题。

我真的很难理解这个想法。

非常感谢任何指导。

我尝试在脑海中和纸上提出这个想法，例如： 1, 0, 1, 0, 1

我会在“开始”状态下从 1 开始，然后检查符号。在这个例子中，符号是1，所以我将符号设置为新的“标记”符号，并在名为“compare_right_1”的新状态中向右移动，在这种状态下机器将到达末尾并读取空白符号因此到达磁带的末尾，因此向左移动并检查符号是否为 1，如果符号是 1，则移动到左侧的下一个空格，如果不是，则退出，因为它不是回文。

我不确定这是否是正确的方法。

Answer 1

我不确定这是否是正确的方法。

我确认这是正确的方法。

有以下转换用于将左侧的 0 与右侧的 1 进行匹配：

现状	符号读取	要写的符号	移动方向	新状态
开始	0	空白	对	找对0
开始	1	空白	对	找到正确的1
开始	空白	复制	对	接受
找对0	0,1	复制	对	找对0
找对0	空白	复制	左	匹配右0
匹配右0	0	空白	左	反向启动
匹配右0	1	复制	左	拒绝
匹配右0	空白	复制	左	接受

当我们需要匹配左侧 1 而不是 0 时添加这些转换（参见上文

findRight1

）：

现状	符号读取	要写的符号	移动方向	新状态
找到正确的1	0,1	复制	对	找到正确的1
找到正确的1	空白	复制	左	匹配右1
匹配右1	0	复制	左	拒绝
匹配右1	1	空白	左	反向启动
匹配右1	空白	复制	左	接受

同样，我们可以在相反的方向上做这一切：

现状	符号读取	要写的符号	移动方向	新状态
反向启动	0	空白	左	找到Left0
反向启动	1	空白	左	找到左1
反向启动	空白	复制	左	接受
找到Left0	0,1	复制	左	找到Left0
找到Left0	空白	复制	对	匹配左0
匹配左0	0	空白	对	开始
匹配左0	1	复制	对	拒绝
匹配左0	空白	复制	对	接受
找到左1	0,1	复制	左	找到左1
找到左1	空白	复制	对	匹配左1
匹配左1	0	复制	对	拒绝
匹配左1	1	空白	对	开始
匹配左1	空白	复制	对	接受

注意：如果您想减少状态数量，您可以直接走到输入的左侧，无需进一步的逻辑，然后从

start

状态重复。这将使执行时间延长大约两倍。

这是一个用 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", write: "_", move: "R", nextState: "findRight0" },
    { state: "start",        read: "1", write: "_", move: "R", nextState: "findRight1" },
    { state: "start",        read: "_",             move: "R", nextState: "accept" },
    { state: "findRight0",   read: "01",            move: "R", nextState: "findRight0" },
    { state: "findRight0",   read: "_",             move: "L", nextState: "matchRight0" },
    { state: "matchRight0",  read: "0", write: "_", move: "L", nextState: "reverseStart" },
    { state: "matchRight0",  read: "1",             move: "L", nextState: "reject" },
    { state: "matchRight0",  read: "_",             move: "L", nextState: "accept" },
    { state: "findRight1",   read: "01",            move: "R", nextState: "findRight1" },
    { state: "findRight1",   read: "_",             move: "L", nextState: "matchRight1" },
    { state: "matchRight1",  read: "0",             move: "L", nextState: "reject" },
    { state: "matchRight1",  read: "1", write: "_", move: "L", nextState: "reverseStart" },
    { state: "matchRight1",  read: "_",             move: "L", nextState: "accept" },
    { state: "reverseStart", read: "0", write: "_", move: "L", nextState: "findLeft0" },
    { state: "reverseStart", read: "1", write: "_", move: "L", nextState: "findLeft1" },
    { state: "reverseStart", read: "_",             move: "L", nextState: "accept" },
    { state: "findLeft0",    read: "01",            move: "L", nextState: "findLeft0" },
    { state: "findLeft0",    read: "_",             move: "R", nextState: "matchLeft0" },
    { state: "matchLeft0",   read: "0", write: "_", move: "R", nextState: "start" },
    { state: "matchLeft0",   read: "1",             move: "R", nextState: "reject" },
    { state: "matchLeft0",   read: "_",             move: "R", nextState: "accept" },
    { state: "findLeft1",    read: "01",            move: "L", nextState: "findLeft1" },
    { state: "findLeft1",    read: "_",             move: "R", nextState: "matchLeft1" },
    { state: "matchLeft1",   read: "0",             move: "R", nextState: "reject" },
    { state: "matchLeft1",   read: "1", write: "_", move: "R", nextState: "start" },
    { state: "matchLeft1",   read: "_",             move: "R", nextState: "accept" },
], "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="10110001101"> <button>Load</button><br>
Tape:
<table><tr></tr></table>
State: <span></span><br>
<button>Step</button><button>Play</button>