本文目的：

1.研究可計(jì)算性的四個(gè)主要模型以及四個(gè)模型彼此之間的關(guān)系；

2.介紹了計(jì)算復(fù)雜性的基本概念和重要的研究方法與一些研究成果担锤。

-----------------------------------------------------廢話分割線-----------------------------------------

基本概念：

1.遞歸函數(shù) 編程語言中迷殿，函數(shù)Func(Type a,……)直接或間接調(diào)用函數(shù)本身儿礼，則該函數(shù)稱為遞歸函數(shù)。遞歸函數(shù)不能定義為內(nèi)聯(lián)函數(shù)庆寺。 在數(shù)學(xué)上蚊夫，關(guān)于遞歸函數(shù)的定義如下：對(duì)于某一函數(shù)f(x)，其定義域是集合A懦尝，那么若對(duì)于A集合中的某一個(gè)值X0知纷，其函數(shù)值f(x0)。

2.圖靈機(jī) 又稱圖靈計(jì)算陵霉、圖靈計(jì)算機(jī)琅轧，是由數(shù)學(xué)家艾倫·麥席森·圖靈（1912～1954）提出的一種抽象計(jì)算模型，即將人們使用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程進(jìn)行抽象踊挠，由一個(gè)虛擬的機(jī)器替代人們進(jìn)行數(shù)學(xué)運(yùn)算乍桂。 所謂的圖靈機(jī)就是指一個(gè)抽象的機(jī)器，它有一條無限長(zhǎng)的紙帶效床，紙帶分成了一個(gè)一個(gè)的小方格睹酌，每個(gè)方格有不同的顏色。有一個(gè)機(jī)器頭在紙帶上移來移去扁凛。機(jī)器頭有一組內(nèi)部狀態(tài)忍疾，還有一些固定的程序。在每個(gè)時(shí)刻谨朝，機(jī)器頭都要從當(dāng)前紙帶上讀入一個(gè)方格信息卤妒，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格

3.λ演算 λ(Lambda（大寫Λ字币，小寫λ）讀音：lan b（m） da（蘭畝達(dá)）['l?;md?])演算是一套用于研究函數(shù)定義则披、函數(shù)應(yīng)用和遞歸的形式系統(tǒng)。它由 Alonzo Church 和 Stephen Cole Kleene 在 20 世紀(jì)三十年代引入洗出，Church 運(yùn)用 lambda 演算在 1936 年給出 判定性問題 (Entscheidungsproblem) 的一個(gè)否定的答案士复。這種演算可以用來清晰地定義什么是一個(gè)可計(jì)算函數(shù)。關(guān)于兩個(gè) lambda 演算表達(dá)式是否等價(jià)的命題無法通過一個(gè)通用的算法來解決。這是不可判定性能夠證明的頭一個(gè)問題阱洪，甚至還在停機(jī)問題之先便贵。后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上冗荸，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)承璃，然后進(jìn)行移動(dòng)。由f(f(x0))決定蚌本，那么就稱f(x)為遞歸函數(shù)盔粹。

4.馬爾可夫算法 馬爾可夫算法是使用類似形式文法的規(guī)則在符號(hào)串上操作的字符串重寫系統(tǒng)。馬爾可夫算法被證明是圖靈完全的程癌，這意味著它們適合作為一般的計(jì)算模型舷嗡，并可以用它的簡(jiǎn)單概念表示任何數(shù)學(xué)表達(dá)式。 Refal是基于馬爾可夫算法的編程語言嵌莉。

5.NP完全理論 NP完全問題(NP-C問題)进萄，是世界七大數(shù)學(xué)難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題烦秩，即多項(xiàng)式復(fù)雜垮斯。

6.復(fù)雜性理論（complexity theory）是理論計(jì)算機(jī)科學(xué)和數(shù)學(xué)的一個(gè)分支郎仆，它致力于將可計(jì)算問題根據(jù)它們本身的復(fù)雜性分類只祠，以及將這些類別聯(lián)系起來。一個(gè)可計(jì)算問題被認(rèn)為是一個(gè)原則上可以用計(jì)算機(jī)解決的問題扰肌，亦即這個(gè)問題可以用一系列機(jī)械的數(shù)學(xué)步驟解決抛寝，例如算法。

------------------------------------------簡(jiǎn)單介紹已結(jié)束曙旭，高難度符號(hào)即將到來-------------------------------------

一.可計(jì)算函數(shù)

原語言的５條基本指令和約定　　　

可計(jì)算函數(shù)２個(gè)常用函數(shù)

考核：用原語言證明函數(shù)是可計(jì)算函數(shù)盗舰。

二　遞歸函數(shù)

算子有３種，分別是附和算子桂躏，遞歸算子钻趋，取極小算子。全函數(shù)與正則函數(shù)剂习。

原始的遞歸函數(shù)蛮位，只能用符合和遞歸算子得到的函數(shù)稱為原始遞歸函數(shù)。例如：

原始遞歸謂詞鳞绕，謂詞P的特征函數(shù)是原始遞歸函數(shù)失仁。

可計(jì)算謂詞，謂詞P的特征函數(shù)是可計(jì)算的们何。相關(guān)定理：

遞歸與可計(jì)算性的關(guān)系：可計(jì)算遞歸萄焦；部分可計(jì)算部分遞歸

考核：1 證明函數(shù)是原始遞歸函數(shù)；

?????????? 2 用原語言程序5條基本指令計(jì)算謂詞的特征函數(shù)

三　POST-TURING程序和TURING機(jī)

P-T程序冤竹，雙向無窮帶符號(hào)B和1拂封，指令6個(gè)如下：

數(shù)X在帶上的表示 : X (0=1,1=11,3=1111)

F(X1,X2.....Xn)的初值在帶上表示：X1BX2B.....Bxn?? (2,0,3)=111B1B1111

結(jié)果：帶上的1的個(gè)數(shù)減 1茬射。

P-T部分可就算與P-T可計(jì)算。

廣義的P-T機(jī)：

四　半圖厄系統(tǒng)

半圖厄系統(tǒng)semi-thue system冒签，半圖厄系統(tǒng)現(xiàn)在考慮處理符號(hào)串的一種系統(tǒng),這部分的內(nèi)容和形式語言理論有密切聯(lián)系躲株。

希望通過結(jié)構(gòu)化知識(shí)，提高學(xué)習(xí)效率镣衡，讓你的工作時(shí)間更值錢霜定，賺錢更高效！------------《 數(shù)據(jù)分析筆記》