IS CS-2019S2-03

题目来源：Problem 3 日期：2024-08-02 题目主题：CS-计算理论-可计算性

未完成

解题思路

这道题目涉及可计算性理论的核心概念。我们需要理解计算实数的定义，并运用递归函数的性质来解答各个小问。关键点包括：

1. 构造递归函数来逼近特定实数（如 $\sqrt{2}$）
2. 使用对角线论证法证明不可计算实数的存在
3. 利用已知的可计算实数来构造新的可计算实数
4. 理解 $\phi$-递归函数的定义和性质，并使用反证法

Solution

1. Show that $\sqrt{2}$ is computable

To prove $\sqrt{2}$ is computable, we need to construct a recursive function $f$ such that $f\downarrow \sqrt{2}$.

Let’s define $f(n)$ as follows:

1. Initialize $x_0=1$, $g(x)=x^2-2$
2. For $i$ from 1 to $n$: $x_i=x_{i-1}-\frac{g(x_{i-1})}{g^{\prime }(x_{i-1})}=\frac{1}{2}(x_{i-1}+\frac{2}{x_{i-1}})$
3. Return $\lfloor 2^n\cdot x_n\rfloor$

This is the Newton-Raphson method for approximating $\sqrt{2}$. We can prove that:

1. $f$ is recursive as it only involves basic arithmetic operations and a bounded loop.
2. $|x_n-\sqrt{2}|<\frac{1}{2^{n+1}}$ for all $n\ge 1$.

Therefore, $|\sqrt{2}-f(n)/2^n|<1/2^n$ for all $n\ge 1$, satisfying the definition of $f\downarrow \sqrt{2}$.

2. Show that there exists a non-negative real number that is not computable

We can prove this using a diagonalization argument:

1. Let $\{f_i{\}}_{i=1}^{\infty }$ be an enumeration of all recursive functions.
2. Define a real number $r\in [0,1]$ as follows:
   • The $i$-th bit of $r$ is 1 if $f_i(i)/2^i<0.5$, and 0 otherwise.
3. $r$ is not computable because it differs from every $f_i$ in at least the $i$-th bit.
4. If $r$ were computable, there would be some $f_j$ such that $f_j\downarrow r$, but this leads to a contradiction.

Therefore, $r$ is a non-negative real number that is not computable.

3. Show that if there exists a recursive function $f$ that satisfies $f\downarrow x$, then there exists a recursive function $g$ that satisfies $g\downarrow x^2$

Given $f\downarrow x$, we can construct $g$ as follows:

$g(n)=\lfloor (f(n+1)/2^{n+1}{)}^2\cdot 2^n\rfloor$

Now, we need to prove that $g\downarrow x^2$:

1. $g$ is recursive because $f$ is recursive and it only involves basic arithmetic operations.
2. $|x-f(n+1)/2^{n+1}|<1/2^{n+1}$ (given)
3. $|x^2-(f(n+1)/2^{n+1}{)}^2|<2x/2^{n+1}+1/4^{n+1}$ (by squaring the inequality)
4. $|x^2-g(n)/2^n|<2x/2^{n+1}+1/4^{n+1}+1/2^n<1/2^n$ (for sufficiently large $n$)

Therefore, $g\downarrow x^2$.

4. Show that there exists no $\phi$-recursive function $h$ that satisfies the given condition

We will prove this by contradiction. Assume such an $h$ exists.

1. Define a $\phi$-recursive function $k$ as follows:

   0 & \text{if } h(\varphi, n) = 0 \\ \text{undefined} & \text{otherwise} \end{cases}$$

2. Now, consider the function $f(n)=k(f,n)$. This is a well-defined recursive function.

3. If $f\downarrow 0$, then by the condition, $h_f\downarrow H(0)=0$. This means $k(f,n)$ is always 0, so $f\downarrow 0$.

4. If $f/\downarrow 0$, then $f$ is not total, so $H(0)=0$. By the condition, $h_f\downarrow 0$, which means $k(f,n)$ is always 0, so $f\downarrow 0$.

5. We have reached a contradiction: $f\downarrow 0⟺f/\downarrow 0$.

Therefore, our assumption must be false, and no such $\phi$-recursive function $h$ can exist.

知识点

可计算性理论递归对角线论证Newton-Raphson方法反证法

难点思路

第 4 小问是这道题的难点。关键在于构造一个巧妙的 $\phi$-递归函数，使其导致矛盾。这种构造方法在可计算性理论中经常使用，类似于停机问题的证明。

解题技巧和信息

1. 对于可计算实数的问题，通常可以通过构造一个逼近序列来证明。
2. 证明不可计算对象存在时，对角线论证是一个强大的工具。
3. 在处理递归函数时，要注意函数的定义域和值域，特别是在处理部分函数时。
4. 反证法在计算理论中是一个常用的证明技巧，尤其是在证明某些性质不存在时。

重点词汇

• computable number 可计算数
• recursive function 递归函数
• diagonalization argument 对角线论证
• primitive recursion 原始递归
• minimization 极小化
• contradiction 矛盾

参考资料

1. Computability: An Introduction to Recursive Function Theory by Nigel Cutland, Chapter 3-4
2. Theory of Computation by Michael Sipser, Chapter 3
3. Computability and Logic by George S. Boolos, John P. Burgess, Richard C. Jeffrey, Chapter 5-6