确定实数的有限前缀语言

Question

为什么数字pi的有限前缀的语言可由TM确定，而假定存在TM的真实数字是错误的，该实数决定了该数字的有限前缀给定数量？

Answer 1

为什么数PI可判定的有限前缀由TM

语言有打印出的pi的位数有限前缀的有效计算过程。 sin（x）的Maclaurin系列是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，或者是稍微大一点或小一点，比我们真正需要的。我们可以通过检查Maclaurin系列中的cos（x）来看出：我们看到cos（1.57）收敛于正数，所以我们知道我们处于n位数小于pi/2的最大数。保持计算至少比你需要返回pi数字低一级，一切都会变好。

，而它是假的说，对于任何实数，其决定了给定数量的

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

• 在UTM编码
• 枚举字典顺序所有字符串，并计算TM的许多有效的UTM编码，我们如何找到
• 暂停计算时，我们算TM我们编码TM想为
• 要求前缀的长度等于我们刚刚得到
• 检查前缀的最后一位看到我们的TM是否接受空的语言或不

计数答案

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

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