$ pi $是否具有一定的数字？

Question

我们得到了以下练习。

让

$ qquad displaystyle f（n）= begin {case} 1＆0^n text {发生在} pi 0＆ text {else} end} end} end} end {cases} $中的十进制表示中

证明$ f $是可计算的。

这怎么可能？据我所知，我们不知道wether $ pi $包含每个数字序列（或哪个）和算法当然不能决定某个序列是 不是 发生。因此，我认为$ f $不可计算，因为基本问题仅是半确定的。

Answer 1

只有两种可能性要考虑。

• 对于每个积极整数 $ n $, ，字符串 $ 0^n $ 出现在十进制 $ pi $. 。在这种情况下，始终返回1的算法总是正确的。

• 有最大的整数 $ n $ 这样 $ 0^n $ 出现在十进制 $ pi $. 。在这种情况下，以下算法（具有值 $ n $ 硬编码）总是正确的：

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

我们有 不 想法这些可能性是正确的，或什么价值 $ n $ 在第二种情况下是正确的。然而，这些算法之一是正确的。因此，有一种算法可以决定是否 $ n $ 零出现在 $ pi $;问题是可决定的。

---

注意与以下证明草图的微妙差异 加拉斯:

1. 取随机的图灵机和随机输入。
2. 该计算将永远继续进行，或者它将在某个时候停止，并且有一个（常数）可计算的函数描述这些行为中的每一个。
3. ???
4. 利润！

亚历克斯十边缘 解释：

注意停止定理的规定：它说没有单个程序可以决定给定程序是否停止。您可以轻松地制作两个程序，以便任何一个程序都可以计算给定程序是否停止：第一个总是说“它停止”，第二个“不停止” - 一个程序始终是正确的，我们只是无法计算哪个程序他们是！

sepp2k 添加：

如果是Alex的示例，则两种算法都不会返回所有输入的正确结果。就这个问题而言，其中一个会。您可以声称问题是可决定的，因为您知道有一种算法为所有输入产生正确的结果。无论您知道哪种算法是什么都没关系。 10

Answer 2

只是在杰夫的答案上稍作阐述。

我们知道存在两个函数/案例可以计算函数f（n）：

1. 始终返回true的函数（对于所有n，存在n个连续0的数量）
2. 如果n小于整数n，将返回true的函数，其中n被定义为给定非理性数字中存在的最大连续0（否则返回false）。

这些功能中只有一个可以正确。我们不知道哪个，但我们可以肯定地知道答案存在。可计算性要求存在一个函数，该函数可以在有限的步骤中确定答案。

案例1中的步骤数在微不足道上绑定到仅返回1。

在情况2中，步骤数也是有限的。对于每个整数$ n $，我们都可以构建一台Turing Machine $ t_n（n）$，如果$ n <n $，则可以在有限的时间内拒绝。因此，不知道$ n $上的上限没关系。对于每一个$ n $来说，都有一台图灵机，即$ t_n（n）$，可以正确计算$ n <n $（我们不知道哪一个是正确的，但这没关系，一个存在） 。

虽然可能无法在两种情况下进行选择（尽管似乎比另一种更有可能），但我们知道其中一个必须是正确的。

附带说明：我们的解决方案假设我们无法确定哪个函数将引起正确的值，但可计算性的本质并不依赖于证明的构造性。纯粹的存在就足够了。

Answer 3

以下证明尝试的步骤5是不合理的，实际上 错误的 - 可以找到反例 这里. 。 （谢谢，Yuval；它确实感觉像是草图中最粗略的部分）。我在这里留下了答案，因为我认为错误是有启发性的。

---

首先：杰夫的答案就足够了； F 无论哪种方式都是可计算的。

但是，短暂的绕道尝试通过归纳来尝试证明证明的草图：
前提 r: ：$ pi $不重复。
1.查看基地的$ pi $ 2.这主要是为了减少案件数量。
2.无论您走多远，您将永远找到另一个 1 某个地方：替代方案是所有的零，这意味着$ pi $开始重复，这反对 r.
3.沿着线路并找到同样的 0.
4.扩展到两位数的序列：您无法停止找到 01 或者 10 （也就是它切换的地方），因为否则$ pi $将开始重复 1的或 0 11 或者 00, ，因为否则它开始重复 1010101...
5.归纳步骤：每个有限序列必须出现无限的次数，因为替代方案是$ pi $开始在一个较短的序列上重复，这与之相矛盾 r.