圖靈在科學、特別在數理邏輯和計算機科學方面，取得了舉世矚目的成就，他的壹些科學成果，構成了現代計算機技術的基礎。計算，可以說是人類最先遇到的數學課題，並且在漫長的歷史年代裏，成為人們社會生活中不可或缺的工具．那麽，什麽是計算呢？直觀地看，計算壹般是指運用事先規定的規則，將壹組數值變換為另壹(所需的)數值的過程．對某壹類問題，如果能找到壹組確定的規則，按這組規則，當給出這類問題中的任壹具體問題後，就可以完全機械地在有限步內求出結果，則說這類問題是可計算的。這種規則就是算法，這類可計算問題也可稱之為存在算法的問題。這就是直觀上的能行可計算或算法可計算的概念．
在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上設計出世界上第壹個電腦程序的象棋。