【正文】 因此計算機系統(tǒng)一樣也具有形式系統(tǒng)的局限性。圖靈證明這類問題是不可判定的。 著名的停機問題就是一個不可判定性的問題。 形式系統(tǒng) 的局限性 ⑴、不完備性 ： 1931 年，哥德爾提出的關于形式系統(tǒng)的“不完備性定理”指出：如果一個形式的數(shù)學理論是足夠復雜的（復雜到所有的遞歸函數(shù)在其中都能夠表示）而且，它是無矛盾的，那么 在這一理論中存在一個語句，而這一語句在這一理論中是既不能證明也不能否證的。 ?計算機系統(tǒng)的軟、硬件都是一種形式系統(tǒng)，它們的結構也可以用形式化方法描述。 ?⑷ 變形規(guī)則：變形規(guī)則亦稱演繹規(guī)則或推導規(guī)則。 ?⑵ 形式規(guī)則：形式規(guī)則規(guī)定一種程序借以判定哪些符號串是本系統(tǒng)中的，公式哪些不是。這時抽象公理系統(tǒng)可以有多種解釋。 ?在抽象公理系統(tǒng)（以 Hilbertd的 《 幾何基礎 》 為代表）中，原始概念的直覺意義被忽視，甚至沒有任何預先設定的意義。 ?在歐氏幾何公理系統(tǒng)中，原始概念（點、線、面）和所有的公理都有直觀的背景或客觀的意義，像這樣有現(xiàn)實世界背景的公理系統(tǒng)，一般被稱為具體公理系統(tǒng)（以歐幾里德的 《 幾何原本 》 為代表）。一般而言，正確的一定是簡單的（注意，這句話是單向的，反之不一定成立）。簡單化將使無矛盾性和獨立性的證明成為可能。 ?其它科學紛紛效法數(shù)學公理化建造理論的模式，出現(xiàn)了各種理論的公理化系統(tǒng)，如理論力學公理化，相對論公理化以及科學計算領域的公理化等等。 ?“ 歐氏幾何 ”和“ 非歐幾何 ”就是在研究和使用公理化方法的過程中產生的。 公理 5: 整體大于部分。 公理 3：等量減等量差相等 。 公理 1：等于同量的量彼此相等 。 原始概念：點、線、面； 原始命題：公設和公理如下： 公設 1：兩點之間可作一條直線； 公設 2：一條有限直線可不斷延長； 公設 3：以任意中心和直徑可以畫圓； 公設 4：凡直角都彼此相等； 公設 5：在平面上，過給定直線之外的一點，存在且僅存在一條平行線。 迭代程序都可以轉換為與它等價的遞歸程序 ； 反之，則不然。 即 ：使 |Sn Sn 1| ε 滿足 精度的要求，計算就結束 。 遞歸 與 迭代 雖然 本質 相同，但實際還是有一些差別。 阿克曼函數(shù)： ?????n + 1A ( m , n ) = A ( ( m 1), 1)A A ( m , n 1)( m 1, ) m = 0n = 0m , n 0若 若 若 解阿克曼函數(shù)的遞歸算法 : Be gin if m=0 th en n+1 el se if n =0 the n A(m 1,1 ) el se A(m 1, A(m ,n 1) ) // 自身調用的遞歸過程 En d 大家完成作業(yè)題： 例 計算 A(1,2) 解 : A(1,2)= A(0, A(1,1)) =A(0, A(0, A(1,0)) =A(0, A(0, A(0,1)) =A(0, A(0,2)) =A(0,3) =4 應注意：這里的阿克曼函數(shù)是一個二元（ m， n）遞歸函數(shù)。 解： 階乘 F (n) = n ! 的遞歸定義如下： F (0)= 1 遞歸基礎 F (n) =n F (n 1) ， n =1,2 ,3, ? 。 請給出其遞歸定義。 ?涉及遞歸定義的證明通常采用數(shù) 學歸納法，數(shù) 學歸納法是遞歸的基礎。 ?數(shù)學歸納法是一種論證方法。 如果已知n1a?就可以確定na， 從 數(shù)學歸納法的角度來看，這相當于數(shù)學歸納法歸納步驟的內容。 例 計算 5 6 計算方法之一： 6 ， 6+ 6= 12 ， 12 + 6= 18 ， 18+ 6= 24 ， 24+ 6= 30 。 遞歸 的實質 體現(xiàn)在函數(shù) Fa ctor oa l() 的自身調用上。 // 遞歸終止條件 E ls e re t ur n n* Fa c to ri al (n 1) / / 遞歸調用過程 } 利用 if ? else ... 語句 把遞歸 “ 結束條件 ” 和需要 “ 繼續(xù)遞歸求解 ” 的情況區(qū)分開來。 任何一個有意義的遞歸總是由兩部分組成： 遞歸調用 與 遞歸終止條件 。 遞歸在科學計算中是大量存在的。 這就是遞歸的基本思想， 即利用前面已有的計算結果和相同的計算公式。 例如：當求前 n個自然數(shù)的和時，可以把它視為 n個自然數(shù)的連加： S(n)＝ 1+2+3+…+(n 1)+n= S(n1)+n 我們給出其形式表達式： S(1)=1。 證明： ① 、 歸納基礎：當 n= 1時，等式成立，即 1=12 ； ②、 歸納步驟：設對任意 k 1， P(k) 成立， 即 ， 1+3+5+…+(2k 1)= k2， 而 1+3+5+…+(2K 1)+[2(K+1)1]= K2+2K+1= (K+1)2 則當 P(k) 成立時， P(K+1)也成立。 ① 歸納基礎： 證明： P(1) [n1p ( n ) |?] 為真； ② 歸納步驟： 證明：對任意的 i 1 ，若 P(i) 為真， 則 ： P(i+1) 也為真。 例如：證明 h層的滿二叉樹共有 2h1結點。 該方法能用有限的步驟，解決無窮對象的論證問題。 數(shù)學歸納法： 數(shù)學歸納法廣泛地應用于計算理論研究之中。 對某個整數(shù) m 來說， 則有 : q = 2m ⑵ 將 ⑵ 式代入 ⑴ 式，可得： (2m)2=2 2p，則有： 2p= 2 m2 就有： 2p為偶數(shù)。 則 ： 22q( 2 ) ( )p? （ p ， q 為正整數(shù)，且 p ， q 互質）。 那么 X 會不會是分數(shù)呢？ 畢達哥拉斯學派用反證法證明了，這個數(shù)不是有理數(shù)（不可公度數(shù)），它就是非有理數(shù)（無理數(shù)）2。他想， X 代表對角線長，而2X2 ? ，那么 X 必定是確定的數(shù)（實際上并由此使西方發(fā)現(xiàn)了“勾股定律”）。 第一個發(fā)現(xiàn)數(shù)2為 “不可公度比” 的數(shù)。 畢達哥拉斯 （ P y th ag o r as ）學派提出了 “萬物皆數(shù)” 的命題， 把所有的 “數(shù)” 都 歸結為：“ 整數(shù)”或“整數(shù)之比”（可公度比數(shù)）。 語言由符號串與文（語）法產生 ， 不 同 類的文法由不同的自動機識別。 “ 自動機 ”就是 為識別形式語言（軟件語言）而產生的 。 ∑3 ＝ {000, 001, 010, 011, 100, 101, 110, 111} … ∑n ＝ 2n 個 n 位二進制數(shù)的全集 語言 、 文法 以及 自動機 有著密切的關系。 ?字母表的閉包： 由字母表的乘積和冪來定義 ?定義式： ∑0＝ {ε} ∑n ＝ ∑n1其中： V 語法變量的非空有窮集；語法變量也 稱 “非終極符”； T 終極符的非空有窮集； 語言最終使用的字符； V U T = Φ； P 產生規(guī)則的非空有窮集； P 中的元素 具有α→β形式；α ( V T )??；*( V T )? ?； S 文法 G 的開始符號； S ∈ V ； 例：（ {A ， B} ， {0 ， 1} ， {A → 0 ， A → 1 ， A → 0A ， A → 1A} ， A ）； 01010 的推導過程： A?0A?01A?010A?0101A?01010。 不包含任何字符串的語言稱作空語言 ， 用Ф表示 。 形式化語言，即 “ 符號 ” 語言。 ⑶、 若α是∑上的符號串， 當且僅當它由 ⑴ 和 ⑵ 導出 直觀來說，∑上的符號串 （ 句子 ） 是由其上的符號以任意次序拼接起來構成的，任何符號都可以在串中重復出現(xiàn)。 字母表∑上的字符串以下列規(guī)則 生成 ： ⑴、 空串：不含任何字符的串；用字符ε表示。 字母表示構成字符串和形成語言的基礎。 字母表中的元素稱 為該字母表的字母（符號、字符） 字母表的內的字母不可拆分，如： {0 ,1 } ； {aa,bb, cc } 字母表可以理解為計算機輸入鍵盤上符號的集合 。 布爾運算真值表 非運算： ? 0=1 ； ? 1=0 ； 與 ( 交 ) 運算： 0 ∧ 0=0 ； 0 ∧ 1=0 ； 1 ∧ 0=0 ； 1 ∧ 1=1 ； 或 ( 并 ) 運算： 0 ∨ 0