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

Question

问题图片

目前，我正在尝试研究图灵机。它应该采用序列 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 模拟器

谢谢你。

Answer 1

您可以通过将属于 k 的每个

a

映射到

b

来跟踪 k 的递减数量。标记属于这样一对的角色的想法是个好主意。一旦没有剩余的（未标记的）

a

，您就可以开始删除字符，直到（并包括）第一个未标记的

b

。接下来的

a

应保留。最后删除该系列

a

之后的所有字符。 （可选）将磁头移动到磁带上留下的第一个

a

来结束。

这种方法实际上会选择第 k+1^th 数字，因此只需删除第一个

a

，而不将其映射到

b

来补偿这一点。

这是一个可能的转换表：

状态	阅读	写	摇头	下一个状态
开始	a	_	对	得到
开始	b 或 _		对	拒绝
得到	a	_	对	查找数据库
得到	B	_	对	擦拭
得到	b	_	对	保留
查找数据库	a 或 B		对	查找数据库
查找数据库	b	B	左	快退
查找数据库	_		左	快退
快退	a 或 B		左	快退
快退	_		对	得到
擦拭	a 或 B	_	对	擦拭
擦拭	b	_	对	保留
擦拭	_		左	拒绝
保留	a		对	保留
保留	_		左	结束
保留	b	_	对	修剪
修剪	a 或 b	_	对	修剪
修剪	_		左	结束
结束	a		左	结束
结束	_		对	接受

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

这是带有该转换表的可运行实现：

createTuring({
    transitions: [
        { state: "start",  read: "a",   write: "_", 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: "rewind" },
        { 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: "end"    },
        { state: "keep",   read: "b",   write: "_", move: "R", nextState: "trim"   },
        { state: "trim",   read: "ab",  write: "_", move: "R", nextState: "trim"   },
        { state: "trim",   read: "_",               move: "L", nextState: "end"    },
        { state: "end",    read: "a",               move: "L", nextState: "end"    },
        { state: "end",    read: "_",               move: "R", nextState: "accept" },
    ],
    initState: "start",
    tape: "aaababaaaaabaa"
});

<script src="https://trincot.github.io/turing.js"></script>