可計(jì)算性理論(數(shù)據(jù)庫)

時(shí)間：2022-10-30 14:30:02 | 來源：信息時(shí)代

時(shí)間：2022-10-30 14:30:02 來源：信息時(shí)代

    可計(jì)算性理論 : 研究關(guān)于計(jì)算一般性質(zhì)的數(shù)學(xué)理論,它起源于對(duì)數(shù)學(xué)基礎(chǔ)問題的研究。在過去多少年中,人們對(duì)“數(shù)學(xué)”與“計(jì)算”這兩個(gè)不同概念一直沒有區(qū)分,而且都沉淀于“數(shù)學(xué)問題都能計(jì)算”的誤區(qū)中,但是當(dāng)數(shù)學(xué)發(fā)展到一定階段后人們發(fā)現(xiàn),“數(shù)學(xué)”與“計(jì)算”是不同概念,于是就提出了: “計(jì)算的實(shí)質(zhì)是什么? ” “是否所有數(shù)學(xué)問題都可計(jì)算? ”這就出現(xiàn)了可計(jì)算性理論。
可計(jì)算性理論屬數(shù)理邏輯中的遞歸論,它出現(xiàn)于20世紀(jì)30年代,研究計(jì)算的數(shù)學(xué)模型,是使用一種數(shù)學(xué)模型來給“計(jì)算”作精確的定義。在1936年,Godel、Herbrand和Kleene定義了遞歸函數(shù);Church于1935年提出了λ換位演算;Turing于1936年定義了圖靈機(jī),其主要內(nèi)容是:
(1) 圖靈機(jī)是一種抽象計(jì)算機(jī),它可以精確描述計(jì)算的特性。一臺(tái)標(biāo)準(zhǔn)圖靈機(jī)由三部分組成: 一條雙向無限長且被分為一個(gè)個(gè)小方格的磁帶、一個(gè)有限狀態(tài)控制器以及一個(gè)讀寫磁頭。機(jī)器的工作是根據(jù)控制器狀態(tài)及磁頭定位所在磁帶方格上的信息決定的,讀寫磁頭在磁帶上打印一個(gè)符號(hào),磁頭向左或向右移動(dòng)一格,機(jī)器由原有的一個(gè)狀態(tài)轉(zhuǎn)向另一個(gè)狀態(tài)。按照此原理不斷工作,直至停機(jī)。表面看來,圖靈機(jī)功能簡單,但是它有無限的空間(磁帶方格)與時(shí)間(計(jì)算步數(shù)),因此只要有足夠的時(shí)間與空間,它能處理任何一個(gè)可計(jì)算函數(shù)。
(2)λ換位演算是一種定義函數(shù)的形式演算系統(tǒng),在此演算中引入了符號(hào)“λ”,以明確區(qū)分函數(shù)與函數(shù)值,并把函數(shù)值的計(jì)算歸結(jié)為按一定規(guī)則進(jìn)行的一系列轉(zhuǎn)換,最后得到函數(shù)值,按照λ換位演算能得到函數(shù)值的函數(shù)稱為λ可定義函數(shù)。λ換位演算是由λ項(xiàng)所組成的一種數(shù)學(xué)演算系統(tǒng)。λ換位演算是1935年由A.church提出用于精確定義可計(jì)算性的一種理論。
(3)遞歸函數(shù)是一種數(shù)論函數(shù),在其中引入了“遞歸”概念后所定義的函數(shù)稱遞歸函數(shù)。遞歸函數(shù)的自變量與函數(shù)值均為自然數(shù)。遞歸函數(shù)中的最簡單部分稱原始遞歸函數(shù),原始遞歸函數(shù)的組成如下:①零函數(shù):函數(shù)值為0的函數(shù)C₀;②后繼函數(shù):S(x);③投影函數(shù):P_i(n);④原始遞歸函數(shù)的組合是原始遞歸函數(shù); ⑤原始遞歸函數(shù)通過簡單遞歸式所構(gòu)成的函數(shù)是原始遞歸函數(shù)。
在原始遞歸函數(shù)上作適當(dāng)擴(kuò)充可構(gòu)成部分遞歸函數(shù),亦即是說,設(shè)g(y,x₁,x₂,…,x_n)是原始遞歸函數(shù),如存在z使g(x₁,x₂,…,x_n,z)=0,就取f(x₁,x₂,…,x_n)值為滿足g(x₁,x₂,…,x_n,z)=0的最小的自然數(shù)z; 如不存在使g(x₁,x₂,…,x_n,z)=0的自然數(shù),就稱f(x₁,x₂,…,x_n)無定義。將此f加到原始遞歸函數(shù)中就得到部分遞歸函數(shù)?？梢宰C明部分遞歸函數(shù)是可計(jì)算函數(shù)。
在20世紀(jì)30年代以后陸續(xù)證明了圖靈機(jī)、λ可定義函數(shù)以及部分遞歸函數(shù)它們都是等價(jià)的,同時(shí)Church還提出了一個(gè)著名的Church論題,該論題說:λ可定義函數(shù)與一般直觀所理解的可計(jì)算函數(shù)是相同的。這樣就得到了可計(jì)算的三個(gè)數(shù)學(xué)模型:圖靈機(jī)、λ換位演算及部分遞歸函數(shù)。此外,以后還有Markov提出的正規(guī)算法、Post提出的Post演算等,它們也都是可計(jì)算的數(shù)學(xué)模型。
由于計(jì)算機(jī)是一種可計(jì)算模型,數(shù)據(jù)庫的模型也是可計(jì)算模型,因此,可計(jì)算性理論對(duì)計(jì)算機(jī)科學(xué)及數(shù)據(jù)庫的影響與作用極其深遠(yuǎn),而一般而言,不可計(jì)算函數(shù)一定不能在計(jì)算機(jī)中求解。