图灵机实现：从一元编码序列中按左向右选第k个元素
2026-6-13
图灵机数字选择函数修正问题
数字选择函数定义
输入：序列𝑥₁,𝑥₂,…,𝑥ₙ,𝑘，满足：
- 每个𝑥ᵢ为非负整数；
- 𝑘为正整数；
- 所有数字采用一元编码：用
a的重复次数代表数值，b作为分隔符，输入编码格式为a^x₁ba^x₂…ba^xₙa^k（最后一个元素𝑥ₙ后无b，直接接𝑘的编码）。
输出：第k个数字𝑥ₖ的一元编码a^xₖ，无末尾b。非法输入（如k=0、k>n）需触发崩溃。
当前问题
我的思路是通过标记k的编码a递减计数，但现有代码会从右往左选取第k个元素。例如输入序列1,5,2,3（对应编码abaaaaabaabaaa），代码选取的是从右数第3个元素，而我需要按左向右顺序选取第3个元素（即2）。使用的是仅向右无限扩展的Tuatara模拟器，磁头从磁带最左端开始。
原代码
createTuring({ transitions: [ // First, move to the end of the tape { state: "start", read: "a", move: "R", nextState: "start" }, { state: "start", read: "b", move: "R", nextState: "start" }, { state: "start", read: "_", move: "L", nextState: "init" }, // Begin the algorithm from the end { state: "init", read: "a", write: "A", move: "L", nextState: "get" }, { state: "init", read: "b", move: "L", nextState: "reject" }, { state: "init", read: "_", move: "L", nextState: "reject" }, { state: "get", read: "a", write: "_", move: "L", nextState: "findb" }, { state: "get", read: "B", write: "_", move: "L", nextState: "wipe" }, { state: "get", read: "b", write: "_", move: "L", nextState: "keep" }, { state: "findb", read: "aB", move: "L", nextState: "findb" }, { state: "findb", read: "b", write: "B", move: "R", nextState: "rewind" }, { state: "findb", read: "_", move: "R", nextState: "reject" }, { state: "rewind", read: "aB", move: "R", nextState: "rewind" }, { state: "rewind", read: "_", move: "L", nextState: "get" }, { state: "wipe", read: "aB", write: "_", move: "L", nextState: "wipe" }, { state: "wipe", read: "b", write: "_", move: "L", nextState: "keep" }, { state: "wipe", read: "_", move: "R", nextState: "reject" }, { state: "keep", read: "a", move: "L", nextState: "keep" }, { state: "keep", read: "_", move: "R", nextState: "pickup" }, { state: "keep", read: "b", write: "_", move: "L", nextState: "trim" }, { state: "trim", read: "ab", write: "_", move: "L", nextState: "trim" }, { state: "trim", read: "_", move: "R", nextState: "pickup" }, { state: "pickup", read: "a", write: "_", move: "R", nextState: "roll" }, { state: "pickup", read: "_", move: "R", nextState: "pickup" }, { state: "pickup", read: "A", write: "_", nextState: "accept" }, { state: "roll", read: "a", move: "R", nextState: "roll" }, { state: "roll", read: "_", write: "a", move: "L", nextState: "left" }, { state: "roll", read: "A", write: "a", nextState: "accept" }, { state: "left", read: "a", move: "L", nextState: "left" }, { state: "left", read: "_", move: "R", nextState: "pickup" }, ], initState: "start", tape: "abaaaaabaabaaa" });
<script src="https://trincot.github.io/turing.js"></script>
修改方案
核心思路
- 标记k的编码：先找到最后一个
b之后的所有a（即k的编码），将其替换为标记K，用于后续递减计数。 - 左向右遍历计数：回到磁带最左端，逐个遍历元素，每遇到一个
b就代表完成一个元素的遍历，此时删除一个K（k减1），直到K全部删除（k=0），此时当前遍历的元素就是目标𝑥ₖ。 - 清理磁带输出结果：删除磁带上的其他内容，只保留目标元素的
a编码。
修改后的代码
createTuring({ transitions: [ // 第一步：找到最后一个b，标记k的a为K { state: "start", read: "a", move: "R", nextState: "start" }, { state: "start", read: "b", move: "R", nextState: "mark_k_start" }, { state: "start", read: "_", move: "L", nextState: "reject" }, // 无b说明只有k，非法 // 标记k的所有a为K { state: "mark_k_start", read: "a", write: "K", move: "R", nextState: "mark_k" }, { state: "mark_k_start", read: "_", move: "L", nextState: "reject" }, // k=0，非法 { state: "mark_k", read: "a", write: "K", move: "R", nextState: "mark_k" }, { state: "mark_k", read: "_", move: "L", nextState: "find_last_b" }, // 回到最后一个b的位置，再返回磁带开头 { state: "find_last_b", read: "K", move: "L", nextState: "find_last_b" }, { state: "find_last_b", read: "b", move: "L", nextState: "go_to_start" }, { state: "go_to_start", read: "a", move: "L", nextState: "go_to_start" }, { state: "go_to_start", read: "b", move: "L", nextState: "go_to_start" }, { state: "go_to_start", read: "_", move: "R", nextState: "count_elements" }, // 第二步：逐个遍历元素，递减k计数 { state: "count_elements", read: "a", move: "R", nextState: "count_elements" }, { state: "count_elements", read: "b", move: "R", nextState: "decrement_k" }, { state: "count_elements", read: "K", move: "R", nextState: "reject" }, // k>n，非法 // 递减k：删除一个K，然后回到当前元素的开头 { state: "decrement_k", read: "a", move: "R", nextState: "decrement_k" }, { state: "decrement_k", read: "b", move: "R", nextState: "decrement_k" }, { state: "decrement_k", read: "K", write: "_", move: "L", nextState: "go_back_to_current" }, { state: "decrement_k", read: "_", move: "L", nextState: "reject" }, // k>n，非法 // 返回当前元素的起始位置 { state: "go_back_to_current", read: "a", move: "L", nextState: "go_back_to_current" }, { state: "go_back_to_current", read: "b", move: "R", nextState: "check_k" }, { state: "go_back_to_current", read: "_", move: "R", nextState: "check_k" }, // 检查k是否已减到0 { state: "check_k", read: "a", move: "R", nextState: "check_k" }, { state: "check_k", read: "b", move: "R", nextState: "check_k" }, { state: "check_k", read: "K", move: "L", nextState: "count_elements" }, // k还没到0，继续遍历 { state: "check_k", read: "_", move: "L", nextState: "target_found" }, // k=0，找到目标元素 // 第三步：清理磁带，保留目标元素的a { state: "target_found", read: "a", move: "L", nextState: "target_found" }, { state: "target_found", read: "b", move: "R", nextState: "clear_left" }, { state: "target_found", read: "_", move: "R", nextState: "clear_left" }, // 删除目标元素左侧的所有内容 { state: "clear_left", read: "a", write: "_", move: "L", nextState: "clear_left" }, { state: "clear_left", read: "b", write: "_", move: "L", nextState: "clear_left" }, { state: "clear_left", read: "_", move: "R", nextState: "clear_right" }, // 删除目标元素右侧的所有内容（包括K和b） { state: "clear_right", read: "a", move: "R", nextState: "clear_right" }, { state: "clear_right", read: "b", write: "_", move: "R", nextState: "clear_right" }, { state: "clear_right", read: "K", write: "_", move: "R", nextState: "clear_right" }, { state: "clear_right", read: "_", move: "L", nextState: "accept" }, // 拒绝状态 { state: "reject", read: "_", move: "R", nextState: "reject" } ], initState: "start", tape: "abaaaaabaabaaa" });
关键修改说明
- 新增
mark_k相关状态：专门标记k的编码为K，避免和元素的a混淆。 - 调整遍历方向：从磁带最左端开始，逐个元素计数，每完成一个元素就递减k的标记
K，直到k为0。 - 新增非法输入判断：比如k=0（无
a标记）、k>n（遍历完所有元素后还有K剩余）都会触发reject状态。 - 清理逻辑优化：精准保留目标元素的
a，删除其他所有内容，输出符合要求的结果。
内容的提问来源于stack exchange，提问作者Tien Hung Nguyen
相关产品推荐
相关产品推荐
