CS70Disc 06A

2 Code Reachability

考虑三元组 $(M, x, L)$：

问题是：如果我们执行 $M(x)$，我们是否会命中行 $L$？

证明：

假设存在可判定的过程：假设存在一个程序可以决定是否在执行 $M(x)$ 时会到达行 $L$，我们称这个程序为 Reachable(M, x, L)。

构造程序 $M$：定义一个程序 $M$ 如下：

1
2
3

def M(t):
    run P(x)    // M 的第 1 行
    return      // M 的第 2 行

使用程序判断停机：我们将使用这个程序 $M$ 来判断某个程序 $P(x)$ 是否会停机：
1
2
def Halt(P, x):
return Reachable(M, 0, 2)
分析程序 $M$：
- 程序 $M$ 的第一行执行 $P(x)$，
- 如果 $P(x)$ 停机，程序 $M$ 会执行到第二行，并返回（命中行 2）。
- 如果 $P(x)$ 不停机，程序 $M$ 则不会到达第二行，直接挂起。
矛盾的出现：
- 因此，程序 $M$ 到达行 2 的条件正好是 $P(x)$ 是否停机。
- 如果 Reachable(M, 0, 2) 可以判断到达性，那么我们就可以判断停机问题，这是一个已知的不可判定问题。
结论：
- 因此，假设存在 Reachable(M, x, L) 是矛盾的。即使我们能够判定某行是否可达，这样的过程也会导致对停机问题的判定，因此代码可达性问题是不可判定的。

给定字符串的组成情况，求解以下问题：

答案： $ = $

解释：

字符串的总长度为 $n + m$。
选择其中 $n$ 个位置放置 1，剩下的 $m$ 个位置自然就是 0。
选择 $n$ 个位置的方法数为 $\binom{n+m}{n}$。
另一种思考方式是考虑所有字符的排列。总共有 $(n+m)!$ 种排列，但是由于 $n$ 个 1 和 $m$ 个 0 的顺序不影响最终字符串，所以需要除以 $n!$ 和 $m!$： $ $

答案： $ $

解释：

字符串的总长度为 $n_1 + n_2 + n_3$。
选择其中 $n_1$ 个位置放置 A，剩下的 $n_2 + n_3$ 个位置中选择 $n_2$ 个位置放置 B，最后剩下的位置放置 C。
根据排列组合的思路，字符串的总排列数为 $(n_1+n_2+n_3)!$，但由于相同字符的顺序不影响最终字符串，所以需要除以 $n_1!$、$n_2!$ 和 $n_3!$： $ $
另一种方式是使用选择位置的策略，先选择 A 的位置，然后选择 B 的位置，最终得出相同的结果。