千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2015年8月実施 専門 B10

标签：

• Decidability-and-Undecidability

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

$\mathbb N$ 上の一変数部分計算可能関数を重複を許して全て並べた列を $\{\varphi_e\}$ とする。$\simeq$ は両辺が同時に未定義、または共に定義され値が等しいことを意味する。次を仮定する。

• 対角関数 $n\mapsto\varphi_n(n)$ は部分計算可能。
• 二変数部分計算可能関数 $g(n,m)$ に対して、全域計算可能な $S$ が存在し、$\varphi_{S(n)}(m)\simeq g(n,m)$。

(1) $D=\{n:n\notin\operatorname{dom}\varphi_n\}$ はどの $\varphi_e$ の定義域にもならないことを示せ。

(2) $A=\{m:0\notin\operatorname{dom}\varphi_m\}$ もどの $\varphi_e$ の定義域にもならないことを示せ。

题目描述

设 $\{\varphi_e\}$ 枚举全部一元部分可计算函数，允许重复，$\simeq$ 表示同时无定义或同时有定义且相等。假设对角函数 $n\mapsto\varphi_n(n)$ 部分可计算，并满足参数化性质：每个二元部分可计算函数 $g$ 都有全可计算函数 $S$，使 $\varphi_{S(n)}(m)\simeq g(n,m)$。

(1) 证明 $D=\{n:\varphi_n(n)\text{ 无定义}\}$ 不是任何部分可计算函数的定义域。

(2) 对 $A=\{m:\varphi_m(0)\text{ 无定义}\}$ 证明同样结论。

Kai

(1)

$D=\operatorname{dom}\varphi_e$ と仮定すると

$$e\in D\iff e\notin\operatorname{dom}\varphi_e\iff e\notin D$$

となり矛盾する。

(2)

$g(n,m)\simeq\varphi_n(n)$ と定める。第一の仮定からこれは部分計算可能であり、第二の仮定により全域計算可能な $S$ で

$$\varphi_{S(n)}(m)\simeq\varphi_n(n)$$

となるものが存在する。特に

$$n\in D\iff\varphi_n(n)\text{ が未定義}\iff\varphi_{S(n)}(0)\text{ が未定義}\iff S(n)\in A.$$

仮に $A=\operatorname{dom}\varphi_e$ なら、部分計算可能関数 $h(n)\simeq\varphi_e(S(n))$ の定義域は $D$ となる。これは (1) に矛盾する。