形式語言、自動機和計算理論/導論

這本教科書主要探討了無限語言的有限表示，這些表示方法適合進行計算分析和特徵化。簡而言之，就是如此。本書的其餘部分將詳細闡述這個簡要的概述，並提供更多詳細論述的參考。

語言

形式語言是某個字母表上的字串集合。一個語言，稱為 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