Hello World 可计算性、代码可达性、字符串计数

(a) 不可计算（Uncomputable）。将 \(\text{TestHalt}(P,x)\) 归约到 \(\text{PrintsHW}(P,x)\)：

\[\text{TestHalt}(P, x):\] 构造辅助程序 \(P'(x)\)：运行 \(P(x)\) 同时屏蔽所有打印语句；最后执行 print("Hello World!")。

\[\text{if PrintsHW}(P', x): \text{ return true else return false}\]

若 \(\text{PrintsHW}\) 存在，则上述构造给出 \(\text{TestHalt}\) 的一个实现，矛盾。故 \(\text{PrintsHW}\) 不存在。

(b) 不可计算（Uncomputable）。将 (a) 的 \(\text{PrintsHW}(P,x)\) 归约到本问的 \(\text{PrintsByK}(P,x,k)\)：

\[\text{PrintsHW}(P, x): \text{ for } i \text{ in range(len}(P\text{)): if PrintsByK}(P, x, i\text{): return true; return false}\]

若 \(\text{PrintsByK}\) 存在则 \(\text{PrintsHW}\) 可判定，矛盾。

(c) 可计算（Computable）。直接模拟运行程序直到执行完 \(k\) 步：若期间 \(P\) 打印了 "Hello World!" 返回真，否则返回假。

(b) 不可计算而 (c) 可计算的原因：是否执行过源代码的某一特定行取决于程序逻辑，无法通用判定；而执行的机器指令条数是可以被计数的。

假设存在过程 \(\text{Reachable}(M, x, L)\) 能判定上述问题。考虑如下用于判定 \(P(x)\) 是否停机的程序：

\[\begin{aligned} \texttt{def Halt}(P, x):\\ \quad \texttt{def M}(t):\\ \quad \quad \texttt{run P(x)} \quad \# \text{line 1 of } M\\ \quad \quad \texttt{return} \quad \quad \# \text{line 2 of } M\\ \quad \texttt{return Reachable}(M, 0, 2) \end{aligned}\]

程序 \(M\) 会到达第 \(2\) 行当且仅当 \(P(x)\) 停机。于是我们实现了一个停机问题的解法——矛盾。故原问题不可判定。

(a) \(\displaystyle \binom{n+m}{n}\)。

(b) \(\displaystyle \frac{(n_1 + n_2 + n_3)!}{n_1! \cdot n_2! \cdot n_3!}\)。

(c) \(\displaystyle \frac{(n_1 + n_2 + \cdots + n_k)!}{n_1! \cdot n_2! \cdots n_k!}\)。

(a) 在这个 9 字母单词中，L 与 O 各出现 2 次，其余字母各出现 1 次。\(9!\) 因两个 L 的互换多计了 \(2!\) 倍，又因两个 O 的互换多计了 \(2!\) 倍。故不同重排数为

\[\frac{9!}{(2!)^2}.\]

(b) \(\displaystyle \binom{n+k}{k}\)。把它想象成由 \(n\) 个 1 与 \(k\) 个加号组成的序列：\(y_0\) 是第一个加号之前的 1 的个数，\(y_1\) 是第一个与第二个加号之间的 1 的个数，依此类推。由"balls and bins"（stars and bars）方法计得 \(\binom{n+k}{k}\)。

(c) \(\displaystyle \binom{(n-(k+1))+k}{k} = \binom{n-1}{k}\)。对全部 \(k+1\) 个变量各自减 1，并从总和里减去 \(k+1\)，即可化为与 (b) 同型的非负整数问题；求得解后再对每个变量加 1，即得到正整数解。

等价地，由 stars and bars 直接推导：正整数约束意味着不能有空组。考察 \(n\) 个星号之间的 \(n-1\) 个"空隙"，从中选出 \(k\) 个放置隔板（两个隔板不能占同一空隙，否则会出现空组），得到 \(\binom{n-1}{k}\) 种分组方式。