5.17 2024-10-01 题目 Show that the Post Correspondence Problem is decidable over the unary alphabet . 思路 点击展开 只需要上下 的个数相同，记录 第 个骨牌中，下方 个数与上方 个数的差为 , 第 个骨牌选取了 次（, 不全为 ），问题就是判断是否存在这样的 使得 解答 点击展开 如果存在 , 那么令 即可，也就是只选取这一个骨牌，下面考虑其余情况： 将 分为正负两部分，不妨设 时, . 时, 那么取 Misplaced &\sum_{i=m+1}^n{-a_i} &,\quad i\leq m\\ \sum_{i=1}^m{a_i} &,\quad i> m\end{aligned}\right.$$ 这就满足了条件，需要特判的是只有正数或只有负数的情况 因此，图灵机工作方式如下： 1. $a_i$ 中存在 $0$ 就接受 2. $a_i$ 中有正有负就接受 3. 否则拒绝 </details>
评论区
最新评论
--