主页 / coding / 问题 / 79030968
Accepted
Gwin Lim
Asked: 2024-09-27 18:40:27 +0800 CST

图灵机 - 根据输入查找第 k 个元素

  • 772

问题图片

目前，我正在尝试开发图灵机。它应该接受一个序列 k、x1、x2、...、xn，其中 k 是正整数，对于每个 i，xi 是非负整数作为输入。所有数字都将以 的形式编码a^k b a^x1 b a^x2 b ..... b a^xn。

对于输出，它应该输出第k个元素的值。

例如：如果我的输入是 aaababaaaaabaa(k = 3, 第一个元素 = 1, 第二个元素 = 5, 第三个元素 = 2)

在这种情况下，图灵机应将输出显示为 aa(2)。我目前面临的问题是，我不知道如何跟踪数字 k，因为没有计数器/内存来存储值 k。此外，即使我跟踪了第 k 个元素，我也不知道如何输出该值

我曾尝试使用标记符号技术，即每次从 k 中读取 a 时，它都会将其写为 A 并向右查找 b。如果找到 b，则将其写为 B 并返回查找 A。在这种情况下，我可以跟踪每个 A 和 B（我的想法就像用每个 b 取消每个 a）。但最后，当没有更多的 A 和 B 时，我不知道如何转到第 k 个元素并输出值。

希望有人能帮助我。

p/s: 我正在使用 Tuatara 模拟器

谢谢。

function

1 个回答

  1. Best Answer

    a您可以通过将属于 𝑘 编码的每个字符映射到 来跟踪 𝑘 的减少数量b。标记属于这种对的字符的想法很好。一旦没有剩余的（未标记的）字符a，您就可以开始删除字符，直到（包括）第一个未标记的b。a后面的 应该保留。最后删除该系列 后面的任何字符a。

    这种方法实际上会选择第k+1 个数字，因此只需删除第一个数字a而不将其映射到 ab来补偿这一点。

    您在评论中提到，您使用的是单侧图灵机，其右侧无限，但左侧有一个起点，头部也从那里开始。正如您所指出的，预期输出应在磁带的开头左对齐，因此您需要一些额外的状态和转换来将找到的序列“移动”a到左侧。您可以用不同的方式做到这一点。一种是删除最右边的序列a，并在序列的左侧写入一个。重复此操作，直到到达磁带的开头，我们可以用字母“A”标记。

    我还会删除a属于 𝑘 的，而不是用大写字母标记它们，因为最终你还是会想要删除或替换它们。

    这是一个可能的转换表：

    状态 读 写 移动头部 下一状态
    开始 一个 一个 正确的 得到
    开始 b 或 _ 正确的 拒绝
    得到 一个 _ 正确的 查找数据库
    得到 乙 _ 正确的 擦拭
    得到 b _ 正确的 保持
    查找数据库 a 或 B 正确的 查找数据库
    查找数据库 b 乙 左边 倒带
    查找数据库 _ 左边 拒绝
    倒带 a 或 B 左边 倒带
    倒带 _ 正确的 得到
    擦拭 a 或 B _ 正确的 擦拭
    擦拭 b _ 正确的 保持
    擦拭 _ 左边 拒绝
    保持 一个 正确的 保持
    保持 _ 左边 捡起
    保持 b _ 正确的 修剪
    修剪 a 或 b _ 正确的 修剪
    修剪 _ 左边 捡起
    捡起 一个 _ 左边 卷
    捡起 _ 左边 捡起
    捡起 一个 _ 接受
    卷 一个 左边 卷
    卷 _ 一个 正确的 正确的
    正确的 一个 正确的 正确的
    正确的 _ 左边 捡起
    卷 一个 一个 接受

    初始状态为“start”，空白用“_”表示。如果输入有解决方案，最终状态将为“accept”。

    以下是使用该转换表的可运行实现：

    createTuring({
    transitions: [
        { state: "start",  read: "a",   write: "A", move: "R", nextState: "get"    },
        { state: "start",  read: "b_",              move: "R", nextState: "reject" },
        { state: "get",    read: "a",   write: "_", move: "R", nextState: "findb"  },
        { state: "get",    read: "B",   write: "_", move: "R", nextState: "wipe"   },
        { state: "get",    read: "b",   write: "_", move: "R", nextState: "keep"   },
        { state: "findb",  read: "aB",              move: "R", nextState: "findb"  },
        { state: "findb",  read: "b",   write: "B", move: "L", nextState: "rewind" },
        { state: "findb",  read: "_",               move: "L", nextState: "reject" },
        { state: "rewind", read: "aB",              move: "L", nextState: "rewind" },
        { state: "rewind", read: "_",               move: "R", nextState: "get"    },
        { state: "wipe",   read: "aB",  write: "_", move: "R", nextState: "wipe"   },
        { state: "wipe",   read: "b",   write: "_", move: "R", nextState: "keep"   },
        { state: "wipe",   read: "_",               move: "L", nextState: "reject" },
        { state: "keep",   read: "a",               move: "R", nextState: "keep"   },
        { state: "keep",   read: "_",               move: "L", nextState: "pickup" },
        { state: "keep",   read: "b",   write: "_", move: "R", nextState: "trim"   },
        { state: "trim",   read: "ab",  write: "_", move: "R", nextState: "trim"   },
        { state: "trim",   read: "_",               move: "L", nextState: "pickup" },
        { state: "pickup", read: "a",   write: "_", move: "L", nextState: "roll"   },
        { state: "pickup", read: "_",               move: "L", nextState: "pickup" },
        { state: "pickup", read: "A",   write: "_",            nextState: "accept" },
        { state: "roll",   read: "a",               move: "L", nextState: "roll"   },
        { state: "roll",   read: "_",   write: "a", move: "R", nextState: "right"  },
        { state: "right",  read: "a",               move: "R", nextState: "right"  },
        { state: "right",  read: "_",               move: "L", nextState: "pickup" },
        { state: "roll",   read: "A",   write: "a",            nextState: "accept" },
    ],
    initState: "start",
    tape: "aaababaaaaabaa"
});
    <script src="https://trincot.github.io/turing.js"></script>

    • 1

相关问题