确定实数的有限前缀语言
为什么数字 pi 的有限前缀的语言可以由 TM 决定，而说任何实数存在一个 TM 来决定该给定数字的有限前缀是错误的？
why is the language of finite prefixes of the number pi decidable by a TM whereas it is false to say there is a TM for any real number that which decides the finite prefixes of that given number?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有一个有效的计算过程可以打印出 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 的前缀。例如：
这告诉我们 x = 1.57 是最接近 pi/2 的值，并且比我们真正需要的稍大或稍小。我们可以通过检查 cos(x) 的麦克劳林级数来判断：我们看到 cos(1.57) 收敛到一个正数，因此我们知道我们处于小于 pi/2 的 n 位最大数。保持计算量至少比返回 pi 数字所需的低一级，一切都会好起来的。
这里有一个实数给您：0 到 1 之间的实数，其十进制表示形式为第 n 位设置为 1，如果并且仅当第 n 个图灵机（由所有 TM 的 UTM 编码的字典顺序确定）接受空语言时。这是一个明确定义的实数 - 它的每个十进制数字要么是 0 要么 1 - 但如果我们有一个 TM 可以找到这个实数的任何有限前缀，我们就可以回答这个问题“这个 TM 是否接受空的”语言？”对于任何 TM，通过以下方式进行：
这是一个矛盾，因为无法确定 TM 是否接受空语言。因此，我们认为可以计算该实数的有限前缀的假设是不正确的。
对于任何涉及 TM 的不可判定问题（赖斯定理和对角化参数保证大多数语言的 TM UTM 编码都是如此），您会得到一个无法计算的唯一实数。事实上，可计算的实数是可数的，就像图灵机一样，但与语言和实数不同，它们是不可数的。
There is an effective computational procedure to print out finite prefixes of the digits of pi. The Maclaurin series for sin(x) is x - x^3/3! + x^5/5! - ... Furthermore, we know that sin(pi/2) = 1, so we can set 1 = x - x^3/3! + x^5/5! - ..., start somewhere close (like x = 1.5) and find the largest value of x that increased over its predecessor. Then, multiply this by 2 and keep the first n digits to get a prefix of length n. For instance:
This tells us that x = 1.57 is the closest value to pi/2 and is either a little bigger or a little smaller than we really need. We can tell by checking the Maclaurin series for cos(x): we see that cos(1.57) converges to a positive number, so we know we are on the largest number with n digits that is less than pi/2. Keep the computation at least one level lower than you need to return digits of pi and everything will turn out fine.
Here is a real number for you: the real number between 0 and 1 whose decimal representation as the nth digit set to 1 if and only if the nth Turing machine (determined by lexicographical ordering of the UTM encoding of all TMs) accepts the empty language. This is a well-defined real number - each of its decimal digits is either 0 or 1 - and yet if we had a TM that could find any finite prefix of this real number, we could answer the question "does this TM accept the empty language?" for any TM by:
This is a contradiction since it is undecidable whether a TM accepts the empty language or not. Therefore, our assumption that we could compute finite prefixes of this real number was incorrect.
For any undecidable problem involving TMs (Rice's theorem and diagonalization arguments guarantee that most languages of UTM encodings of TMs are) you get a unique real number which cannot be computed. Indeed, the computable real numbers are countable, just like Turing machines, but unlike languages and real numbers, which are uncountable.