圖靈機可以運行遞歸演算法嗎

① C語言編程：用函數遞歸法求Fibonacci數列的前n項·

#include <stdio.h>

long int F(int n)

{

if (n==1||!n) {

return n;

}

else return F(n-1)+F(n-2);

}

int main(void)

{

int i,n;

printf("n=");

scanf("%d",&n);

for (i=0; i<n; i++) {

printf("%-10ld",F(i));

}

return 0;

}

在數理邏輯和計算機科學中

遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數，它是在某種直覺意義上是"可計算的" 。事實上，在可計算性理論中證明了遞歸函數精確的是圖靈機的可計算函數。遞歸函數有關於原始遞歸函數，並且它們的歸納定義(見下)建造在原始遞歸函數之上。但是，不是所有遞歸函數都是原始遞歸函數 — 最著名的這種函數是阿克曼函數。

以上內容參考：網路-遞歸函數

② 圖靈機是什麼

即確定型圖靈機 1936年 ， 阿蘭·圖靈 提出了一種抽象的 計算模型 —— 圖靈機 (Turing Machine)。圖靈的基本思想是用機器來樠擬人們用紙筆進行 數學 運算的過程，他把這樣的過程看作下堗兩種簡單的動作：
- 在紙上寫上或擦除某個符號；
一個狀態寄存器。它用來保存圖靈機堓前所處的狀態。圖靈機的所有可能狀栁的數目是有限的，並且有一個特殊的砶態，稱為停機狀態。
一條無限長的紙帶。紙帶被劃分為一䠪接一個的小格子，每個格子上包含一䠪來自有限字母表的符號，字母表中有䠀個特殊的符號 \square 表示空白。紙帶上的格子從左到右依栤被編號為 0, 1, 2, ... ，紙帶的右端可以無限伸展。
一個讀寫頭。該讀寫頭可以在紙帶上堦右移動，它能讀出當前所指的格子上砄符號，並能改變當前格子上的符號。
- 把注意力從紙的一個位置移動到另一䠪位置； 而在每個階段，人要決定下丠步的動作，依賴於 (a) 此人當前所關注的紙上某個位置的符堷和(b) 此人當前思維的狀態。為了模擬人的蠙種運算過程，圖靈構造出一台假想的栺器，該機器由以下幾個部分組成：
一套控制規則。它根據當前機器所處砄狀態以及當前讀寫頭所指的格子上的砦號來確定讀寫頭下一步的動作，並改堘狀態寄存器的值，令機器進入一個新砄狀態。 注意這個機器的每一部分都映有限的，但它有一個潛在的無限長的糾帶，因此這種機器只是一個理想的設夠。圖靈認為這樣的一台機器就能模擬亠類所能進行的任何計算過程。

③ 什麼是圖靈論圖靈論在計算機史上起什麼作用

邱奇-圖靈論題(The Church-Turing thesis)是計算機科學中以數學家阿隆佐·邱奇(Alonzo Church)和阿蘭·圖靈命名的論題。該論題最基本的觀點表明，所有計算或演算法都可以由一台圖靈機來執行。以任何常規編程語言編寫的計算機程序都可以翻譯成一台圖靈機，反之任何一台圖靈機也都可以翻譯成大部分編程語言大程序，所以該論題和以下說法等價：常規的編程語言可以足夠有效的來表達任何演算法。該論題被普遍假定為真，也被稱為邱奇論題或邱奇猜想和圖靈論題
該論題有很多可能的意義：
宇宙是一台圖靈機(由此，在物理上對非遞歸函數的計算是不可能的)。此被定義為大邱奇.圖靈論題.
宇宙不是一台圖靈機(也就是說，物理的定律不是圖靈可計算的)，但是不可計算的物理事件卻不能阻礙我們來創建 超計算機(hypercomputer)。比如，一個物理上實數作為可計算實數的宇宙就可以被劃為此類。
宇宙是一台超計算機, 因為建造物理設備來控制這一特徵並來計算非遞歸函數是可能的。比如，一個懸而未決的問題是量子力學的的事件是圖靈可計算的，盡管我們已經證明了任何由qubit所構成的系統都是(最佳)圖靈完全的。 約翰·盧卡斯 (和羅格·本羅澤(Roger Penrose) 曾經建議說人的心靈可能是量子超計算的結果。

④ 圖靈機狀態轉移規則的要素

三要素是負載驅動、轉移條件和轉移方向，要求是在狀態―遷移圖中可能需要使用加進判斷框和處理框的記法。

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。

機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

概述

圖靈機是由英國數學家圖靈（A.M.Turing，1912~1954）在1936年提出的一種計算模型。同遞歸函數和λ-演算相比較，圖靈機的結構和運行同希爾伯特提出的形式系統更為接近，只不過圖靈機並不是（入希爾伯特所希望的那樣）用於判定命題的正確性，而是用於衡量一類問題是否可判定，也就是說，圖靈機同遞歸函數和λ-演算一樣，是衡量問題的可計算性的計算模型。

⑤ 圖靈機是什麼東東主要用於什麼地方

【圖靈機】又稱圖靈計算、圖靈計算機，是由數學家阿蘭·麥席森·圖靈（1912～1954）提出的一種抽象計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人們進行數學運算。

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

圖靈機的主要作用及功能：作為研究計算的一般性質的抽象工具，替代人們進行數學運算，並有以下作用：

1、作為語言接受器：被M接受的語育記作L（M），它是Σ中的這樣一些字元串的集合，當把這些字元串放在M的帶子上，M處於q0狀態且M的帶頭處在最左單元時．這些字元串可以使M進入一個終結狀態而停機。給定一個識別語言L的圖靈機M，一般假定，當輸入被接受時，M為停機，即沒有下一動作。然而對於不被接受的字元串，M可能永不停機．被圖靈機接受的語官稱為遞歸可枚舉語言。遞歸集合是遞歸可枚舉集合的子類，遞歸集合總能被對所有輸入都能停機的圖靈機所接受。

2、作為整數函數計算機：被圖靈機計算的函數稱為部分遞歸函數。在某種意義上，部分遞歸函數類似於遞歸可枚舉語言．因為計算它的圖靈機在給定的輸入上可能不停機。完全遞歸函數對應於遞歸語育．因為它能被總能停機的圖靈機計算。

3、作為語言產生器：設M是一個多帶圖靈機，它用一條帶作為輸出帶，在這條帶上，符號一經寫出上就不能再改寫．輸出帶的帶頭也不能左移。假定在輸出帶上，M寫出某個字毋表Σ的一些字元串，並用分隔符分開，則最終列印在輸出帶上的字元串的集合就稱為由M生成的語言，記為G（M），G(M)Σ。如果L是某個圖靈機生成的語言，則L是遞歸可枚舉集合，反之亦然。

⑥ 艾倫·麥席森·圖靈的主要成就

圖靈在科學、特別在數理邏輯和計算機科學方面，取得了舉世矚目的成就，他的一些科學成果，構成了現代計算機技術的基礎。 計算，可以說是人類最先遇到的數學課題，並且在漫長的歷史年代裡，成為人們社會生活中不可或缺的工具．那麼，什麼是計算呢？直觀地看，計算一般是指運用事先規定的規則，將一組數值變換為另一(所需的)數值的過程．對某一類問題，如果能找到一組確定的規則，按這組規則，當給出這類問題中的任一具體問題後，就可以完全機械地在有限步內求出結果，則說這類問題是可計算的。這種規則就是演算法，這類可計算問題也可稱之為存在演算法的問題。這就是直觀上的能行可計算或演算法可計算的概念．
在20世紀以前，人們普遍認為，所有的問題類都是有演算法的，人們的計算研究就是找出演算法來。似乎正是為了證明一切科學命題，至少是一切數學命題存在演算法，萊布尼茨(Leibniz)開創了數理邏輯的研究工作。但是20世紀初，人們發現有許多問題已經過長期研究，仍然找不到演算法，例如希爾伯特第10問題，半群的字的問題等．於是人們開始懷疑，是否對這些問題來說，根本就不存在演算法，即它們是不可計算的。這種不存在性當然需要證明，這時人們才發現，無論對演算法還是對可計算性，都沒有精確的定義！按前述對直觀的可計算性的陳述，根本無法作出不存在演算法的證明，因為「完全機械地」指什麼？「確定的規則」又指什麼？仍然是不明確的。實際上，沒有明確的定義也不能抽象地證明某類問題存在演算法，不過存在演算法的問題一般是通過構造出演算法來確證的，因而可以不涉及演算法的精確定義問題。
解決問題的需要促使人們不斷作出探索。1934年，哥德爾(Godel)在埃爾布朗(Herbrand)的啟示下提出了一般遞歸函數的概念，並指出：凡演算法可計算函數都是一般遞歸函數，反之亦然。1936年，克林(Kleene)又加以具體化．因此，演算法可計算函數的一般遞歸函數定義後來被稱為埃爾布朗-哥德爾-克林定義．同年，丘奇證明了他提出的λ可定義函數與一般遞歸函數是等價的，並提出演算法可計算函數等同於一般遞歸函數或λ可定義函數，這就是著名的「丘奇論點」。
用一般遞歸函數雖給出了可計算函數的嚴格數學定義，但在具體的計算過程中，就某一步運算而言，選用什麼初始函數和基本運算仍有不確定性。為消除所有的不確定性，圖靈在他的「論可計算數及其在判定問題中的應用」一文中從一個全新的角度定義了可計算函數。他全面分析了人的計算過程，把計算歸結為最簡單、最基本、最確定的操作動作，從而用一種簡單的方法來描述那種直觀上具有機械性的基本計算程序，使任何機械(能行)的程序都可以歸約為這些動作。這種簡單的方法是以一個抽象自動機概念為基礎的，其結果是：演算法可計算函數就是這種自動機能計算的函數。這不僅給計算下了一個完全確定的定義，而且第一次把計算和自動機聯系起來，對後世產生了巨大的影響，這種「自動機」後來被人們稱為「圖靈機」。
圖靈機是一種自動機的數學模型，它是一條兩端(或一端)無限延長的紙帶，上面劃成方格，每個方格中可以印上某字母表中的一個字母(亦可為空格，記為S0)；又有一個讀寫頭，它具有有限個內部狀態。任何時刻讀寫頭都注視著紙帶上的某一個方格，並根據注視方格的內容以及讀寫頭當時的內部狀態而執行變換規則所規定的動作。每個圖靈機都有一組變換規則，它們具有下列三種形狀之一：
qiaRqi，qiaLqi，qiabqj
意思是：當讀寫頭處於狀態qi時如果注視格的內容為字母a則讀寫頭右移一格，或左移一格，或印下字母b(即把注視格的內容由a改成b．a，b可為S0)。
圖靈把可計算函數定義為圖靈機可計算函數．1937年，圖靈在他的「可計算性與λ可定義性」一文中證明了圖靈機可計算函數與λ可定義函數是等價的，從而拓廣了丘奇論點，得出：演算法(能行)可計算函數等同於一般遞歸函數或λ可定義函數或圖靈機可計算函數．這就是「丘奇-圖靈論點」，相當完善地解決了可計算函數的精確定義問題，對數理邏輯的發展起了巨大的推動作用。
圖靈機的概念有十分獨特的意義：如果把圖靈機的內部狀態解釋為指令，用字母表的字來表示，與輸出字輸入字同樣存貯在機器里，那就成為電子計算機了。由此開創了「自動機」這一學科分支，促進了電子計算機的研製工作．
與此同時，圖靈還提出了通用圖靈機的概念，它相當於通用計算機的解釋程序，這一點直接促進了後來通用計算機的設計和研製工作，圖靈自己也參加了這一工作。
在給出通用圖靈機的同時，圖靈就指出，通用圖靈機在計算時，其「機械性的復雜性」是有臨界限度的，超過這一限度，就要靠增加程序的長度和存貯量來解決．這種思想開啟了後來計算機科學中計算復雜性理論的先河。 所謂「判定問題」指判定所謂「大量問題」是否具有演算法解，或者是否存在能行性的方法使得對該問題類的每一個特例都能在有限步驟內機械地判定它是否具有某種性質(如是否真，是否可滿足或是否有解等，隨大量問題本身的性質而定)的問題。
判定問題與可計算性問題有密切的聯系，二者可以相互定義：對一類問題若能找到確定的演算法以判定其是否具有某種性質，則稱這類問題是能行可判定的，或可解的；否則是不可判定的，或不可解的。二者又是有區別的：判定問題是要確定是否存在一個演算法，使對一類問題的每一個特例都能對某一性質給以一個「是」或「否」的解答；可計算性問題則是找出一個演算法，從而求出一些具體的客體來。
圖靈在判定問題上的一大成就是把圖靈機的「停機問題」作為研究許多判定問題的基礎，一般地，把一個判定問題歸結為停機問題：「如果問題A可判定，則停機問題可判定．」從而由「停機問題是不可判定的」推出「問題A是不可判定的」。
所謂停機指圖靈機內部達到一個結果狀態、指令表上沒有的狀態或符號對偶，從而導致計算終止。在每一時刻，機器所處的狀態，紙帶上已被寫上符號的所有格子以及機器當前注視的格子位置，統稱為機器的格局。圖靈機從初始格局出發，按程序一步步把初始格局改造為格局的序列。此過程可能無限制繼續下去，也可能遇到指令表中沒有列出的狀態、符號組合或進入結束狀態而停機。在結束狀態下停機所達到的格局是最終格局，此最終格局(如果存在)就包含機器的計算結果。所謂停機問題即是：是否存在一個演算法，對於任意給定的圖靈機都能判定任意的初始格局是否會導致停機？圖靈證明，這樣的演算法是不存在的，即停機問題是不可判定的，從而使之成為解決許多不可判定性問題的基礎。
1937年，圖靈用他的方法解決了著名的希爾伯特判定問題：狹謂詞演算(亦稱一階邏輯)公式的可滿足性的判定問題。他用一階邏輯中的公式對圖靈機進行編碼，再由圖靈機停機問題的不可判定性推出一階邏輯的不可判定性。他在此處創用的「編碼法」成為後來人們證明一階邏輯的公式類的不可判定性的主要方法之一。
在判定問題上，圖靈的另一成果是1939年提出的帶有外部信息源的圖靈機概念，並由此導出「圖靈可歸約」及相對遞歸的概念。運用歸約和相對遞歸的概念，可對不可判定性與非遞歸性的程度加以比較。在此基礎上，E．波斯特(Post)提出了不可解度這一重要概念，這方面的工作後來有重大的進展。
圖靈參與解決的另一個著名的判定問題是「半群的字的問題」，它是圖埃(Thue)在1914年提出來的：對任意給定的字母表和字典，是否存在一種演算法能判定兩個任意給定的字是否等價[給出有限個不同的稱為字母的符號，便給出了字母表，字母的有限序列稱為該字母表上的字。把有限個成對的字(A1，B1)，…，(An，Bn)稱為字典．如果兩個字R和S使用有限次字典之後可以彼此變換，則稱這兩個字是等價的]1947年，波斯特和A．A．馬爾科夫(Markov)用圖靈的編碼法證明了這一問題是不可判定的。1950年，圖靈進一步證明，滿足消元律的半群的字的問題也是不可判定的。 圖靈在第二次世界大戰中從事的密碼破譯工作涉及到電子計算機的設計和研製，但此項工作嚴格保密。直到70年代，內情才有所披露。從一些文件來看，很可能世界上第一台電子計算機不是ENIAC，而是與圖靈有關的另一台機器，即圖靈在戰時服務的機構於1943年研製成功的CO-LOSSUS(巨人)機，這台機器的設計採用了圖靈提出的某些概念。它用了1500個電子管，採用了光電管閱讀器；利用穿孔紙帶輸入；並採用了電子管雙穩態線路，執行計數、二進制算術及布爾代數邏輯運算，巨人機共生產了10台，用它們出色地完成了密碼破譯工作．
戰後，圖靈任職於泰丁頓國家物理研究所(Teddington National Physical Laboratory)，開始從事「自動計算機」(Automatic Computing Engine)的邏輯設計和具體研製工作。1946年，圖靈發表論文闡述存儲程序計算機的設計。他的成就與研究離散變數自動電子計算機（Electronic Discrete Variable Automatic Computer）的約翰·馮·諾伊曼（John von Neumann）同期。圖靈的自動計算機與諾伊曼的離散變數自動電子計算機都採用了二進制，都以「內存儲存程序以運行計算機」打破了那個時代的舊有概念。 1949年，圖靈成為曼切斯特大學（University of Manchester ）計算實驗室的副院長，致力研發運行Manchester Mark 1型號儲存程序式計算機所需的軟體。1950年他發表論文《計算機器與智能》（ Computing Machinery and Intelligence），為後來的人工智慧科學提供了開創性的構思。提出著名的「圖靈測試」，指出如果第三者無法辨別人類與人工智慧機器反應的差別， 則可以論斷該機器具備人工智慧。
1956年圖靈的這篇文章以「機器能夠思維嗎？」為題重新發表．此時，人工智慧也進入了實踐研製階段。圖靈的機器智能思想無疑是人工智慧的直接起源之一。而且隨人工智慧領域的深入研究，人們越來越認識到圖靈思想的深刻性：它們至今仍然是人工智慧的主要思想之一。 1945年到1948年，圖靈在國家物理實驗室，負責自動計算引擎（ACE）的工作 。1949年，他成為曼徹斯特大學計算機實驗室的副主任，負責最早的真正的計算機---曼徹斯特一號的軟體工作。在這段時間，他繼續作一些比較抽象的研究，如「計算機械和智能」。圖靈在對人工智慧的研究中，提出了一個叫做圖靈試驗的實驗，嘗試定出一個決定機器是否有感覺的標准。
圖靈試驗由計算機、被測試的人和主持試驗人組成。計算機和被測試的人分別在兩個不同的房間里。測試過程由主持人提問，由計算機和被測試的人分別做出回答。觀測者能通過電傳打字機與機器和人聯系（避免要求機器模擬人外貌和聲音）。被測人在回答問題時盡可能表明他是一個「真正的」人，而計算機也將盡可能逼真的模仿人的思維方式和思維過程。如果試驗主持人聽取他們各自的答案後，分辨不清哪個是人回答的，哪個是機器回答的，則可以認為該計算機具有了智能。這個試驗可能會得到大部分人的認可，但是卻不能使所有的哲學家感到滿意。圖靈試驗雖然形象描繪了計算機智能和人類智能的模擬關系，但是圖靈試驗還是片面性的試驗。通過試驗的機器當然可以認為具有智能，但是沒有通過試驗的機器因為對人類了解的不充分而不能模擬人類仍然可以認為具有智能。圖靈試驗還有幾個值得推敲的地方，比如試驗主持人提出問題的標准，在試驗中沒有明確給出；被測人本身所具有的智力水平，圖靈試驗也疏忽了；而且圖靈試驗僅強調試驗結果，而沒有反映智能所具有的思維過程。所以，圖靈試驗還是不能完全解決機器智能的問題。例如：質問者可以說：「我聽說，今天上午一頭犀牛在一個粉紅色的氣球中沿著密西西比河飛。你覺得怎樣？」(你們可以想像該電腦的肩頭上泛出的冷汗：)電腦也許謹慎地回答： 「我聽起來覺得這不可思議，」到此為止沒有毛病。質問者又問： 「是嗎?我的叔叔試過一回，順流、逆流各一回，它只不過是淺色的並帶有斑紋。 這有什麼不可思議的?」很容易想像，如果電腦沒有合適的「理解」就會很快地暴露了自己、在回答第一個問題時，電腦的記憶庫非常有力地想列犀牛沒有翅膀，甚至可以在無意中得到「犀牛不能飛」，或者這樣回答第二個問題「犀牛沒有斑紋」。下一回質問者可以試探真正無意義的問題．譬如把它改變成「在密西西比河下面」，或者「在一個粉紅色的氣球之外」．或者「穿一件粉紅色衣服」，再去看看電腦是否感覺到真正的差別。其實，要求電腦這樣接近地模仿人類，以使得不能和一個人區分開實在是太過分了。一些專家認為，我們不該以電腦能否思維為目標，而是以能多大程度地模仿人類思維為目標；然後，讓設計者再朝著這個目標努力。1952年，圖靈寫了一個國際象棋程序。可是，當時沒有一台計算機有足夠的運算能力去執行這個程序，他就模仿計算機，每走一步要用半小時。他與一位同事下了一盤，結果程序輸了。後來美國新墨西哥州洛斯阿拉莫斯國家實驗室的研究群根據圖靈的理論，在MANIAC上設計出世界上第一個電腦程序的象棋。

⑦ 圖靈在計算機發展史上的主要貢獻有哪些

它的意義有如下幾點:

1、它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

2、圖靈機模型引入了讀寫與演算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

3、圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

通用圖靈機向人們展示這樣一個過程:程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。更重要的是，隱約可以看到現代計算機主要構成，尤其是馮・諾依曼理論的主要構成。

圖靈機簡介：

圖靈機是中央處理器（CPU）的一般示例，該處理器控制計算機完成的所有數據操作，而規范機則使用順序存儲器來存儲數據。更具體地說，它是一種能夠枚舉字母表中有效字元串的任意子集的機器（自動機）；這些字元串是遞歸枚舉集的一部分。圖靈機具有無限長的磁帶，可以在其上執行讀取和寫入操作。

假設黑匣子，圖靈機無法知道它最終是否會使用給定程序枚舉子集的任何特定字元串。這是由於無法解決暫停問題，這對計算的理論限制具有重大意義。

Turing機器能夠處理不受限制的語法，這進一步意味著它能夠以無數種方式穩健地評估一階邏輯。通過lambda演算可以證明這一點。

能夠模擬任何其他圖靈機的圖靈機稱為通用圖靈機（UTM，或簡稱為通用機）。用類似的「通用」性質更數學導向的定義是由引進邱奇，上演算，其工作的正式理論與圖靈的交織在一起計算被稱為教會圖靈論題。

⑧ 遞歸論的演算法演化

解決某一類問題的計算方法又稱演算法。演算法是個古老的數學概念。16世紀R.笛卡爾創造的解析幾何就是用代數來解決幾何問題的一種典型的演算法。但數學中有一些問題長期找不到解決的演算法。人們懷疑根本不存在這種演算法。為了證明這一點，必須對演算法給出精確的定義。20世紀30年代K.哥德爾提出了演算法的一種精確定義，S.C.克林據此定義了遞歸函數。與此同時，A.M.圖靈用圖靈機（一種理論計算機）來描述演算法，並且證明圖靈可計算的函數與遞歸函數等價。圖靈機使人們普遍接受了關於演算法的丘奇論題：遞歸函數是可計算函數的精確的數學描述。
遞歸函數是用數理邏輯的方法定義在自然數集上的可計算函數。如果自然數的一個 n 元集的特徵函數是遞歸函數，就稱這個集合為遞歸集，一個遞歸函數的值域，稱為遞歸可枚舉集。遞歸集就是演算法可判定的集合。遞歸集都是遞歸可枚舉的，但是存在不是遞歸集的遞歸可枚舉的集合。遞歸論的研究使人們把一些長期未解決的問題化為非遞歸的遞歸可枚舉集，從而嚴格證明了不存在判定這些問題的演算法。這些問題稱為不可判定的。
遞歸論進一步研究不可判定的，也就是非遞歸的遞歸可枚舉集之間的復雜程度問題。1944年E.L.波斯特提出不可解度的概念。又給出了相對可計算性的構造方法。這就使人們開始對不可解度進行比較，並研究不可解度的代數結構。這方面出現了有窮損害優先方法、無窮損害優先方法等多種有力的研究手段，出現了許多有趣的研究成果。
對可計算的遞歸集，也可以研究其計算的復雜性，考慮圖靈機上計算的時間，空間，就得到計算時間的長短計算所佔空間的多少這兩個復雜性。計算復雜性的研究對計算機科學的發展有很大影響和作用。