形式语言、自动机和计算理论/导论

这本教科书主要探讨了无限语言的有限表示，这些表示方法适合进行计算分析和特征化。简而言之，就是如此。本书的其余部分将详细阐述这个简要的概述，并提供更多详细论述的参考。

语言

形式语言是某个字母表上的字符串集合。一个语言，称为 L，可以是有限的或无限的。字母表，通常用 Σ 表示，是有限的原始符号集合，例如 Σ = {a,…,z, A,….,Z} 或 Σ = {0,….,9}。每个字符串都是字母表中符号的序列（即有序）。就像集合通常可以用内涵或外延表示一样，语言也可以。外延表示是对语言中字符串的显式列举，仅与有限语言的表示相关。例如，小于 4 的自然数的二进制表示的有限语言是 L = {0, 1, 10, 11}，或者也可以是 {00, 01, 10, 11}，在字母表 Σ = {0, 1} 上。

相反，语言的内涵表示是对语言中字符串集合的有限描述。这些有限长度的描述用于描述无限的以及有限的语言。“小于 4 的自然数的二进制表示”这个自然语言描述是一个语言的内涵表示，它也可以写成 L = {w | w 是小于 4 的整数的二进制表示}。短语“二进制表示”暗示了相关的字母表 {0, 1}。上面还有其他有限集合的内涵表示。它们是什么？虽然我用 Σ = {a,…,z, A,….,Z} 或 Σ = {0,….,9} 来表示字母表，但我也可以说 L = {0,….,9}，例如，或者 L = “十进制算术中常用的单个数字”。

内涵描述也绝对需要用来有限地表示无限语言。考虑 L = {w | w 是大于 3 的整数的二进制表示}，或者也许是“L 是大于 3 的自然数的二进制表示集合”，其中 Σ = {0, 1}。关于内涵描述的一个有趣的观察是，存在着理解它们所需的隐含的（通常未陈述的）推断。外延表示也需要推断，但我可以说，后一种情况下推断更接近于机械级别，是明确的。

有时，内涵描述经过进一步思考后，不足以让人明确理解。幸运的是，在数字的内涵描述中，我们大多数人都会知道如何解释‘…’，因为我们之前的训练，但其他人将不知道如何解释它。即使对于我们中训练最完善的人来说，大于 3 的自然数的二进制表示的描述，经过反思后，似乎也不完整。也许我们应该添加一个短语，例如 L = {w | w 是大于 3 的整数的二进制表示，其中 w 用最少的二进制位数表示} = {100, 101, 110, 111, 1000, 1001, …}。为什么？即使在这里，我们可能还想说 w 没有前导 0。

据我所知，没有一门关于形式语言的课程会试图形式化一般情况下隐含推断的性质，尽管这将是完全理解语言表示和理解复杂性的必要条件，并且无疑对纯数学非常重要。我们会触及其中的一些问题，特别是在讨论人工智能与形式语言之间的关系时。

如前所述，内涵描述（+ 推断机制，它可能是一个计算机程序）是通常为无限语言的有限表示。实际上，这门课程的大部分内容是关于语言的两种有限表示类 - 语法和自动机（或机器） - 它们都适合机械的、明确的、自动化的推理。粗略地说，语法指定了如何在语言中生成字符串，而自动机指定了如何在语言中识别字符串。这种语言生成器和识别器之间的区别并不像这里提到的那样尖锐，但它是一个很好的起点。

证明

自动机和形式语言课程的传统目标是练习演绎证明技巧，这可能会影响和有益于终身思考。词语“证明”经常被误用，例如，当它用来表明这种或那种自然或社会现象没有证明（例如，没有证明气候变化是人为造成的）。这些领域不适合演绎证明，但正如我们在讨论人工智能时将要看到的，用于进行演绎推理的逻辑机制可以与概率和效用相结合，并被重新解释，以成为其他重要形式的推理的骨架结构：可能性推理（即，什么是可能的？），概率推理（即，什么是可能的？），证据推理（即，给定证据/数据/观察结果，什么是可能的？），以及理性推理（即，行动的预期后果是什么，包括概率，但也包括结果的效用/成本？）。

现在回到演绎证明，霍普克罗夫特、莫特瓦尼和乌尔曼（2007）指出

• "在美国 1990 年代，教证明作为对陈述的个人感觉变得流行起来。"（第 5 页，)

但他们继续说

• "虽然对自己的陈述抱有真实感很好，但你所需要使用的重要的证明技巧在高中时不再掌握。然而，证明是每个计算机科学家都需要理解的东西。” (第 5 页，)

将此陈述与同一文本第 12 页的突破性方框“证明需要多么正式？”进行对比，该方框承认，对受众成员的“说服”非常相关，但这将取决于该受众成员拥有什么知识。它继续说，实际上，证明应该说服受众（包括那些有知识的成员），而不仅仅是任意个人。

另一个观点是，证明（我将它描述为“演绎”，波利亚称之为“证明性”和“完成”，包括我们讨论的所有形式的证明）是通过明智的、有知识的猜测进行证明搜索的结果 - 也就是说，数学“正在形成”。

• "数学被认为是一门证明性科学。但这只是它的一方面。以完成形式呈现的完成数学似乎纯粹是证明性的，只包含证明。然而，正在形成的数学类似于任何其他正在形成的人类知识。你必须在证明数学定理之前猜出它；你必须在完成细节之前猜出证明的思路。 " (第 vi 页，)

波利亚明确指出，寻找证明的“猜测”不应该随意，而应该遵循“合理”推理的原则。教科书通常会呈现“完成的”证明，但在讨论中偶尔会有一些关于搜索和规则的见解，以帮助简化和引导寻找最终产品的过程。

例如，考虑哥德巴赫猜想——每个大于 4 的偶数都是两个素数的和。但是，我该如何想出这个命题呢？哥德巴赫是如何得出哥德巴赫猜想的？我通过波利亚认为也是合理推理的一部分来做到这一点——我注意到我可以想到的每个偶数都是两个素数的和。这是一项基于数据的识别模式的经验练习。在识别出合理的模式后，我可以尝试对该命题进行证明（例如，如果 N 是偶数并且大于 4，那么存在 ($\exists$) N-k 和 k 都是素数）。顺便说一句，还没有人证明过哥德巴赫猜想。它很容易陈述，但尚未被证明为真或假。这就是数论的魅力之一——易于理解且难以证明的假设，至少在许多情况下是这样。一个早期的 AI 和机器学习的经典程序被称为 AM，代表“数学家”，由道格拉斯·莱纳特提出。莱纳特的系统不是证明定理（这是 AI 研究在 AM 之前的一个早期重点），而是寻找数论中经验证实的模式，然后由系统将其作为候选定理提出。AM 说明了数学制作过程中的任务，这些任务对于计算理论和数学都是不可分割的。

一旦识别出候选定理，就可以开始寻找证明（或不证明）它。通常，找到一个有效的证明比验证一个给定的证明要困难得多。当对证明进行评分时，会出现一个有趣的寻找和验证的混合问题，表面上任务是验证或否定研究人员（包括学生）提交的“证明”，但这有时需要重点搜索来评估提交的“距离”有效证明有多远（例如，为了分配分数）。对证明尝试进行评分是一个很好的 AI 任务示例，而不是 ALC 领域本身。

归纳证明

图 InductionProof1：一个简单的归纳证明，展示了基本情况和归纳步骤的使用。

图 InductionProof2：第二个归纳证明，展示了基本情况和归纳步骤的使用。

图 InductionProof3：这说明了对字符串的归纳证明。该问题取自霍普克罗夫特和乌尔曼（1979）。该图显示了两个定义之间等价性的证明的第一部分。也就是说，满足定义 1 意味着满足定义 2。虽然这只是等价性证明的一部分（双向蕴涵），但它是一个关于一个方向的整个蕴涵证明的例子。

您可能已经在离散结构课程中学习过归纳证明，如果是这样，我们在这里的处理是复习。如果我们要证明所有自然数的语句 St，那么我们明确地展示基本情况——St(0) 为真，也许还有其他基本情况——然后我们展示归纳步骤的真值，即“如果 St(k) 为真，那么 St(k+1) 为真”对于所有 k $\geq$ 0 和/或其他一些基本情况。归纳步骤表明归纳证明在形式语言中的重要性，其中字符串具有长度，并且通过建立对长度为 k 的字符串（或小于长度 k 并直到长度 k）的字符串的真实性的假设来证明关于长度为 k+1 的字符串的语句的真实性。图 InductionProof1、InductionProof2 和 InductionProof3 给出了示例证明，两个是算术的，第三个涉及字符串。

归纳证明的演绎有效性取决于数论的公理——特别是其中一个。但是，为了回顾，Peano_axioms of number theory are as follows.

1. 0 是一个自然数。

2. 对于每个自然数 x，x = x。也就是说，等式是自反的。

3. 对于所有自然数 x 和 y，如果 x = y，那么 y = x。也就是说，等式是对称的。

4. 对于所有自然数 x、y 和 z，如果 x = y 且 y = z，那么 x = z。也就是说，等式是传递的。

5. 对于所有 a 和 b，如果 b 是一个自然数并且 a = b，那么 a 也是一个自然数。也就是说，自然数在等式下是封闭的。

6. 对于每个自然数 n，n 的后继者，n+1，是一个自然数。也就是说，自然数在后继者函数下是封闭的。

7. 对于所有自然数 m 和 n，m = n 当且仅当 m 的后继者是 n 的后继者，m+1 = n+1。

8. 对于每个自然数 n，n+1 = 0 是假的。也就是说，没有一个自然数的后继者是 0。

9. 如果 K 是一个集合，使得：0 在 K 中，并且对于每个自然数 n，n 在 K 中意味着 n+1 在 K 中，那么 K 包含每个自然数。”

正是第九条公理证明了归纳证明的合理性。它准确地说明了我们上面所说明的内容，即如果一个命题对 n 为真（即 St(n) 为真；n 属于 St 为真的自然数集合），并且 St(n) $\rightarrow$ St(n+1)，那么该命题 St 对每个自然数都为真。

第九条公理，为特定命题 St 实例化，本身就是可数无限自然数集的有限表示。

反证法

还有其他形式的证明，比如反证法。假设您要证明命题 p，那么等价命题 $\neg$p $\rightarrow$ false（或者简单地说 $\neg$p 是假的）可能更容易证明。

例如，用反证法证明“如果x 大于 2 (p₁) 且x 是质数 (p₂)，则x 是奇数 (q)”。简称为用反证法证明 (p₁ ⋀ p₂)  $\rightarrow$ q，因此对该陈述取反，得到

$\neg$((p₁ ⋀ p₂)  $\rightarrow$ q)，等价于（表示为 $\equiv$)

$\equiv$ $\neg$($\neg$(p₁ ⋀ p₂) ⋁ q)

$\equiv$ $\neg$( ($\neg$p₁⋁ $\neg$p₂) ⋁ q)

$\equiv$ ($\neg$($\neg$p₁⋁ $\neg$p₂) ⋀ $\neg$q)

$\equiv$ (($\neg$p₁⋀ $\neg$p₂) ⋀ $\neg$q)

$\equiv$ ((p₁⋀ p₂) ⋀ $\neg$q)

$\equiv$ (p₁⋀ p₂ ⋀ $\neg$q) // $\neg$(x 为奇数) $\equiv$ (x 为偶数)

是否 (x 大于 2) 且 (x 为质数) 且 (x 为偶数) 会产生矛盾？ 如果 x 为偶数，那么 x = 2y,  其中 y > 1，则 x 根据定义是合数，与 x 为质数 (p₂) 矛盾。

这是另一个用反证法证明的例子。这个例子来自 Hopcroft，Motwani 和 Ullman (2007)。令 S 为无限集 U 的有限子集。令 T 为关于 U 的 S 的补集。用反证法证明 T 是无限的。注意 $|$U$|$ 和 $|$S$|$ 表示集合 U 和 S 的基数或大小。

证明  “如果   S ⊂ U (p₁) 且

  不存在整数 n 使得 $|$U$|$ = n (p₂) 且

  存在整数 m 使得 $|$S$|$ = m (p₃) 且

  S ⋃ T = U (p₄) 且

  S ∩ T = {} (p₅)

  那么 不存在整数 p 使得 $|$T$|$ = p  (q)

用反证法

与前面的例子类似，否定整个表达式并简化，得到 p₁ ⋀ p₂ ⋀ p₃ ⋀ p₄ ⋀ p₅ ⋀ $\neg$q.

$\neg$q $\equiv$ 存在整数 p 使得 |T| = p

  p₄ 和 p₅ $\rightarrow$ $|$U$|$ = $|$S$|$ + $|$T$|$ = m + p，与 p₂ 矛盾（即 不存在一个整数 n 使得 $|$U$|$ = n)

对角化

图 对角化：反证法的一个特例是对角化。该图说明了康托尔的对角论证，即 0 到 1 之间的实数不是可数无穷的。

反证法的特例包括反例证明和对角化证明。后一种策略用于证明从无限个类似项目的集合中排除项目。在对角化中，定义一个矩阵，其中可能存在可数无穷多个行，表示集合中的成员。每一行都由矩阵的每一列给出的变量定义。定义矩阵并使用矩阵的对角线来构造一个假设的候选行，但由于候选行的构造方式，它不能属于矩阵中的行集。

康托尔证明实数不是可数无穷的，引入了对角论证，并假设一个矩阵，其中行对应于（可数无穷）自然数（即 0、1、2、3、…），列对应于小数点右侧的数字，如 0.x₁x₂x₃…（例如 0.3271…）。然后可以取此矩阵的对角线，并通过取对角线中的每个数字 x_j,j 并将其更改为（x_j,j+1）mod 10 来创建一个候选行。根据定义，此候选序列无法与任何行匹配，因为其中至少一个数字（沿对角线更改的那个数字）与任何行中对应的数字不同。因此，小数点右侧的数字序列在语法上是有效的，但不能对应于可数无穷个行集中的任何行。这在图 对角化中有所说明。

当这种策略在 19 世纪后期被引入时，它引起了一些争议，因为创建无限长度的反例是新颖的，据说维特根斯坦称对角论证为“障眼法”，但现在它已被长期接受为数学上的有效论证。我们将在证明某些语言不属于某些语言类别时使用它。

构造证明

您将在本书中看到的最常见的“证明”或证明形式涉及构造。例如，如果我们想要证明两个描述 X 和 Y 定义了相同的语言，我们证明可以从 X 构造/转换 Y：X $\rightarrow$ Y，反之亦然，Y $\rightarrow$ X。但我们不能只构造任何东西，并期望它足以证明等价性。您必须确信，从一种表示到另一种表示的转换或构造没有错误，并且是有效的。如果我们想要在形式上严格，我们可能会在构造之后进行证明，例如通过归纳或反证法，证明构造的有效性。我们通常只会暗示或勾勒出证明构造有效的步骤，如果有的化，我们将大部分时间花在解释构造及其有效性上。

自动证明

在 AI 中，自动证明有着丰富的历史，我们花时间讨论 AI 证明，以此来展示思考的重要原理。一个很少在课堂上讲授的重要见解是，要证明某件事，需要搜索有效的证明。您上次看到讲师现场证明以前从未见过的东西是什么时候？这种搜索可能需要很长时间，甚至可能完全不成功。相反，寻找证明（或为给定规范寻找正确的计算机程序）通常会事先发生，可能是从头开始，也可能是通过查找其他人搜索的结果。展示现有证明的有效性（这通常是在课堂上完成的）通常比通过搜索找到有效的证明要容易得多！这种在验证和寻找之间的区别与我们对 *P* 和 *NP* 问题的研究有关，分别。您可能在其他地方（例如算法课程）看到过 P 和 NP，但如果没有，我们将在语言类的属性中讨论它。我们对 AI 证明的讨论将明确地说明搜索的重要性，或者波利亚将什么是合理的理论推理“正在形成”的一部分。

如果您知道要证明的陈述，那么通常有意义的是，通过反转演绎有效步骤，从该陈述反向推理到一组已知公理（以便向前阅读时，步骤是有效的）。*反向推理* 是 AI 和一般思维中一项重要的策略。最早的 AI 论文（如果不是最早的话）将此作为思考策略的是 Shachter 和 Heckerman (1987)，但在 Google 上搜索反向推理或类似术语会发现过去十年中的大量商业文章和演讲。我记得摩托车界的一句老话——“转弯时要看着你想去的地方”，我相信这句比喻适用于你在商业和其他领域阅读的大部分内容。

一个更技术性的例子是，如果我正在规划前往特定目的地的路线，我可能会从路线图上的目的地开始，沿通往目的地的道路向后工作，选择那些朝着我当前位置方向的道路。有趣的是，自动路线规划器可能会在两个方向上工作，从目的地到起点，反之亦然，以寻找搜索“边界”中的交叉点。

自动证明（也称为定理证明）基于形式逻辑。您在上面的反证法中看到了命题逻辑中使用的命题（例如，“p”和“q”）。命题逻辑中的两个基本推理操作是 *modus ponens* 和 *resolution*。 *modus ponens* 推理规则指出，如果您知道 'p'（即，命题 p 为真），并且您知道 'p $\rightarrow$ q'（即，p 蕴含 q），那么您可以演绎得出命题 'q'（即，q 为真）。现在您既知道 p 又知道 q，即 **(p $\land$ q)**。*modus ponens* 是最著名的演绎推理规则。

分辨率规则依赖于蕴涵和析取之间的等价关系，即 (p $\rightarrow$ q) $\equiv$ ($\neg$p $\lor$ q)。如果你知道 'p' 并且你知道 '($\neg$p $\lor$ q)'，那么你当然就知道 q。就好像 p 和 $\neg$p 相互抵消，从逻辑上讲，你可以明白为什么：如果 p $\land$ ($\neg$p $\lor$ q) $\equiv$ (p $\land$ $\neg$p $\lor$ q) $\equiv$ (p $\land$ $\neg$p) $\lor$ (p $\land$ q) $\equiv$ false $\lor$ (p $\land$ q)，这又等价于 **(p $\land$ q)**。

在简单层面上，肯定式推理和分辨率是等价的推理规则，但它们对演绎推理提供了不同的视角。我们将在讨论计算理论时再次看到它们，在最后一章关于应用的章节中再次看到它们，在那里我们将讨论命题逻辑和一阶逻辑中的自动定理证明。

问题、过程和算法

在深入探讨各种类型的语法和自动机以有限地表示语言之前，让我们简要地预览一些我们已经知道的计算理论，即过程和算法。过程是可以通过计算机自动执行的一系列有限步骤。算法是一种在所有输入上都能保证停止的过程。

可判定性和不可判定性

过程，无论是否是算法，都可以用来识别语言。字符串w是否属于语言L是一个是/否问题，而用于回答该问题的过程是L的有限表示，当且仅当 (a) 过程对L中的每个w说'是'（并停止），以及 (b) 过程从不对任何不属于L的w说'是'。如果此外过程对L中每个w说'否'（并停止），那么该过程就是一个算法。请注意，这些条件共同允许一个过程是L的有限表示，但不是一个算法。这样的非算法过程在w属于L时说'是'并停止，但存在不属于L的w，对于这些w，过程不会回答'否'，也不会停止。如果对于语言L，不存在用于正确回答语言成员资格是/否问题的算法，那么L中的成员资格被称为不可判定。如果一个算法确实存在，可以针对所有可能的输入字符串（成员和非成员）正确回答L中的成员资格问题，那么L中的成员资格是可判定的。

据推测，大多数读者都可以编写一个过程来识别输入整数是否为素数，分别输出是或否。如果编写正确，该过程当然会在所有情况下停止，因此它是一个算法，它识别素数语言。也可以编写一个算法来确定一个整数是否为完全数。完全数是一个等于其所有因子之和的数（不包括自身，但包括 1）。因此，素数语言中的成员资格是可判定的，完全数语言中的成员资格也是可判定的。

判定问题

正式地说，判定问题指的是是/否问题。语言成员资格问题是一种判定问题，我们已经给出了测试素数和测试“完美”的示例。让我们考虑另外两个判定问题。您可以编写一个算法来回答是否存在大于您作为输入提供的数字的素数。由于素数是无限的，因此这是一个简单的算法——无论输入是什么，只需回答'是'！但为了说明起见，假设除了是之外，您还想给出大于作为输入传递的数字的最小素数。您可以编写一个算法来执行此操作，该算法可以使用素数成员资格测试算法作为子例程。

您还可以编写一个过程来回答是否存在大于作为输入传递的数字的完全数的问题，但不知道完全数是否是无限的，因此不知道该过程是否是算法——不知道它是否会在所有输入上停止。在输入大于当前已知最大完全数的情况下，如果最终找到更大的完全数，该过程将停止并给出是，但同样，如果不存在更大的完全数，该过程将不会停止。这个关于下一个完全数的判定问题，尚不清楚是可判定的还是不可判定的，但与迄今为止所有不可判定判定问题的例子一样，问题的'不可判定性'在于对'否'情况的处理。

请注意，素数是无限的以及完全数是否是（或不是）无限的知识分别位于下一个素数和下一个完全数的过程之外。我们可以用非常相似的方式编写每个下一个类型问题的过程，而一个过程是算法，另一个过程不是已知的算法，这在过程本身中并没有揭示出来。

作为判定问题的其他示例，让我们考虑一下哥德巴赫猜想的启发。考虑大于 4 的偶数语言。称之为L_Even。考虑L_EvenSum语言，它包含大于 4 的偶数，这些偶数是两个素数的和。现在，考虑L_EvenNotSum语言，它包含大于 4 的偶数，这些偶数不是两个素数的和。一个判定问题是L_EvenSum $=$ L_Even吗？第二个判定问题是L_EvenNotSum $=$ $\phi$，即空语言？直观地说，这两个问题看起来很相似，也许是等价的。作为一个练习，证明这两个问题确实是等价的。

鉴于哥德巴赫猜想仍然是一个猜想，不知道L_EvenSum ${\overset {\underset {\mathrm {?} }{}}{=}}$ L_Even 和 L_EvenNotSum ${\overset {\underset {\mathrm {?} }{}}{=}}$ $\phi$ 是否是可判定的还是不可判定的。并非巧合的是，不知道如何编写一个过程来回答这些问题！这样的过程将构成证明中关于这些判定问题的可判定性或不可判定性的构造的主要部分。

L_EvenSum ${\overset {\underset {\mathrm {?} }{}}{=}}$ L_Even 只是一个用来测试两种语言是否相等的判定问题。类似地，L_EvenNotSum ${\overset {\underset {\mathrm {?} }{}}{=}}$ $\phi$ 只是一个用来测试语言是否为空的判定问题。在关于性质和语言类的章节中，我们将研究判定问题在语言类的背景下（也称为语言集）而非仅仅针对特定语言。例如，对于给定的语言类中的所有语言 L， L ${\overset {\underset {\mathrm {?} }{}}{=}}$ $\phi$ 是否可判定或不可判定？

有趣的是，判定问题本身定义了语言——“语言”的语言！令 L_meta$\phi$ 为空语言的识别程序的集合（也称为语言）。说服自己这是有道理的。毕竟，语言的识别程序是一系列有限的步骤，它是在某种编程语言中的一种有限字符串。L_meta$\phi$ $=$ $\phi$ 吗？L_meta$\phi$ 的成员资格可判定吗？甚至存在一个可以正确回答所有肯定情况和否定情况的 L_meta$\phi$ 的识别程序吗？

无法有限表示的语言

如果不存在 L_meta$\phi$ 的识别程序（即，不存在可以识别 L_meta$\phi$ 的所有成员，并且只有成员的程序），那么 L_meta$\phi$ 的识别将是不可判定的，这甚至比我们迄今讨论的其他不可判定判定问题更强，在这些问题中，问题的“不可判定性”仅在于“否”情况。

直观地说，无法完全有限表示的语言的例子将是那些没有构建识别器基础的语言。一个成员随机选择的语言就是一个直观的说明性例子：L_R = {w | w in Σ* and random(w) == true} 可以通过以某种系统的方式枚举字母表 Σ 上的字符串，并在每种情况下随机决定字符串 w 是否在语言中来形成。构建识别器无法识别此语言的原因是假定 random(w) 在识别器中应用时没有记住它在创建语言时的应用。我们不能简单地记住成员，因为它们有无限多个。相反，如果 random(w) 是一个伪随机过程，那么这些过程是可重复的，在这种情况下我们可以实现一个识别器，但是如果我们有一个真正的随机过程，那么就无法构建识别器来在所有情况下都正确地说“是”。

随机语言，如上所述，是为了给你一个无法有限表示的语言的例子，这些语言可能比 L_meta$\phi$ 让人不那么头疼。当我们更多地谈论计算理论时，我们将回到这些问题。

生成语言

像素数和完全数这样的识别算法也可以用作生成语言的子例程。素数的语言可以通过将“字符串”集合初始化为 {2} 并将识别程序嵌入到一个循环中来生成，该循环从 3 开始迭代越来越大的奇数整数，测试每个数的素数性，并仅添加发现为素数的那些数字。请注意，由于已知素数是无限的，因此此生成过程不会终止，因此它不是一个算法，但当然它也不是一个是非问题。我们可以通过使用一个计数器来从生成器中创建一个不等效的算法，该计数器在指定次数的迭代后人工停止迭代过程。这将不再是无限语言的生成器，而只是生成器到指定长度的语言中的字符串，这将是一个有限语言。

我们可以使用相同的策略来系统地生成更大的数字，在本例中，不是只生成奇数，而是对每个数字使用完美数识别算法。这将是一个完美数的生成器。同样地，除非它受到迭代次数最大值的限制，否则它将永远运行。

旨在“永远运行”的过程被称为随时算法，因为可以在任何时候暂停它，并在继续向前运行算法之前检查到该点的输出。任何经历过系统崩溃的人都知道，随时算法最好被认为是一种理论构造，即使在发生崩溃的情况下，计算机系统通常也会保存其状态并可以从该保存状态重新启动，因此随时算法可以无限期地继续，即使不是永远。

有一些方法可以将语言的生成过程转换为在每次算法运行时生成语言L的一个字符串w的过程。一个练习要求你勾勒出一个这样做的方案，它将保证语言中的每个字符串都以非零概率生成。

练习、项目和讨论

图归纳法练习1：用归纳法证明。清楚地说明基础情况和归纳假设/步骤的使用，以及其他工作。

归纳法练习1：用归纳法证明图归纳法练习1中给出的等式。

归纳法练习2：（由于 Hopcroft 和 Ullman (1979) ）。简要说明以下归纳“证明”中有什么问题：任何集合中的所有元素都必须相同。基础是对于只有一个元素的集合，该语句显然是正确的。假设该语句对于具有n-1个元素的集合是正确的，并考虑一个具有n个元素的集合 S。令a为 S 的一个元素。令 S = S₁ $\cup$ S₂，其中 S₁ 和 S₂ 各自具有n-1个元素，并且都包含a。根据归纳假设，S₁ 中的所有元素都与a相同，S₂ 中的所有元素都与 a 相同。因此，S 中的所有元素都与a相同。

归纳法练习3：用归纳法证明，非空完全二叉树中的叶子数恰好比内部节点数多 1。

证明讨论1：与一个 AI 大型语言模型讨论“证明”的历史和哲学，可能包括似是而非的推理、无穷大或你特别感兴趣的其他问题。包括你的提示和响应，或者要求 LLM 用 X 个字或更少（例如，X = 500）来总结讨论。

判定问题练习1：证明L_EvenSum ${\overset {\underset {\mathrm {?} }{}}{=}}$ L_Even 和L_EvenNotSum ${\overset {\underset {\mathrm {?} }{}}{=}}$ $\phi$ 是等价的判定问题。

判定问题练习2：有一些方法可以将语言的生成过程转换为在每次算法运行时生成语言L的一个字符串w的过程。勾勒出一个这样做的方案，它将保证语言中的每个字符串都以非零概率生成。你的“一次性”版本的生成可以使用L的识别过程作为子例程。

证明项目1：了解 AI 证明助手，并在整个学期使用它们来解决你被分配的和未分配的问题。在一个证明组合中报告结果和经验。 https://www.nytimes.com/2023/07/02/science/ai-mathematics-machine-learning.html