1

为什么数字 pi 的有限前缀的语言可以由 TM 决定，而说任何实数都有一个 TM 决定给定数字的有限前缀是错误的？

4

1 回答 1

0

为什么数字 pi 的有限前缀的语言可以由 TM 决定

有一个有效的计算过程可以打印出 pi 数字的有限前缀。sin(x) 的麦克劳林级数是 x - x^3/3！+ x^5/5！- ... 此外，我们知道 sin(pi/2) = 1，所以我们可以设置 1 = x - x^3/3！+ x^5/5！- ...，从某个接近的地方开始（例如 x = 1.5）并找到 x 的最大值，它比其前身增加了。然后，将其乘以 2 并保留前 n 位数字以获得长度为 n 的前缀。例如：

f(1.50) < f(1.51) < f(1.52) < f(1.53) < f(1.54) < f(1.55) < f(1.56) < f(1.57)
f(1.59) < f(1.58) < f(1.57)

这告诉我们 x = 1.57 是最接近 pi/2 的值，并且比我们真正需要的大一点或小一点。我们可以通过检查 cos(x) 的 Maclaurin 级数来判断：我们看到 cos(1.57) 收敛到一个正数，所以我们知道我们在 n 位小于 pi/2 的最大数上。保持计算至少比返回 pi 的数字低一级，一切都会好起来的。

而说任何实数都有一个决定该给定数的有限前缀的 TM 是错误的

这是一个给你的实数：0 到 1 之间的实数，当且仅当第 n 个图灵机（由所有 TM 的 UTM 编码的字典顺序确定）接受空语言时，其十进制表示为第 n 位设置为 1 . 这是一个定义明确的实数——它的每个十进制数字都是 0 或 1——但是如果我们有一个 TM 可以找到这个实数的任何有限前缀，我们就可以回答这个问题“这个 TM 是否接受空语？” 对于任何 TM，通过：

  • 在 UTM 编码中编码 TM
  • 按字典顺序枚举所有字符串并计算我们找到多少有效的 TM 的 UTM 编码
  • 当我们计算我们想要答案的 TM 时停止计算
  • 要求一个前缀，其长度等于我们刚刚得到的计数
  • 检查前缀的最后一位以查看我们的 TM 是否接受空语言

这是一个矛盾，因为无法确定 TM 是否接受空语言。因此，我们可以计算这个实数的有限前缀的假设是不正确的。

对于任何涉及 TM 的不可判定的问题（赖斯定理和对角化参数保证大多数语言的 UTM 编码的 TM），您会得到一个无法计算的唯一实数。事实上，可计算的实数是可数的，就像图灵机一样，但不像语言和实数，它们是不可数的。

于 2017-11-21T21:55:14.843 回答