涂林面對的首要問題是，有哪些可能的程序可用來計算一個數？他採取的途徑是：

(一)仔細分析我們的直觀，從而定義出合適的計算機；

(二)證明別人嘗試過的方法和他的方法等價，但是他的方法更接近直觀；

(三)給出大量各式各樣的數，證明它們在新的意義下是可以計算的。

在分析直觀方面，涂林解析一位計算者的狀態，（他稱為 computer 那時電子計算機尚未問世。）從中抽離出最本質的要素，然後模擬定義一個理論的計算機。這個機器能變換的狀態是有限的，因為涂林認為計算者的心靈不應該有無窮多狀態，否則有些狀態會任意接近，以致無法區分其間的差異。機器具備一條要多長就有多長的紙帶，紙帶畫分成一個個小方格。另外有有限個符號，用以寫在小方格上來記錄計算過程。機器在每一刻的動作，取決於當時機器的狀態與所掃瞄的小方格上的符號。機器的基本動作包括：

(一) 在小方格上寫一個符號，如果原來已經有符號，就把那個符號遮掉；

(二) 擦掉原來寫在小方格上的符號；

(三) 把紙帶向左或向右移動一格。

涂林定義理論計算機的方法有相當大的彈性，如果採取一些變化並不會影響可以計算的範圍，因此現在把這一類的理論計算機都稱為涂林機器（Turing machine，下文簡稱涂林機，圖二）。乍看起來令人懷疑這麼簡單的計算工具能算多少東西？當然從如此原始的基礎出發，要想計算日常使用的數學物件，必然會經過冗長的步驟。但涂林的重點不在要花多少精力，而在可不可能做到。最終涂林以極具說服力的論證讓人相信，所有可計算的數都能用涂林機計算。

圖二：涂林機器 (Turing machine)。

在瞭解其計算機功能的過程中，涂林體會到定義一個計算機的方法也是機械性的，因此可以用符號記錄下來。如此便能定義一個所謂的萬用計算機，它可以模擬任何其他涂林機的計算過程。萬用計算機把想模擬的涂林機的定義符號當作輸入吃進來，然後在想要計算的輸入值上，一方面解讀被模擬機器的指令，一方面依樣畫葫蘆執行，最後得出同樣的結果。萬用涂林機賦予當代內儲程式 (stored program) 電子計算機的理論基礎，使得人類在機械發明史上，首次有可能利用軟體的變化，大量擴充硬體的使用效率。

當我們深刻體認出涂林機的威力時，我們會產生一個跟剛開始時態度相反的問題：還有什麼是涂林機不可能計算的呢？當我們啟動涂林機開始計算某個輸入值時，最怕的是它一直運作不停，老是給不出答案而抵達停機的最終狀態。涂林機的定義方法，並不保證每次計算都會在有限時間內完成。於是我們很自然便想知道，有沒有可能造一個特殊的涂林機，來判斷任何涂林機一旦在任何輸入值上開動，是否計算最後會停止。這就是所謂的「停機問題」 (halting problem)。因為所有的涂林機可以有效地、機械化地逐一列隊，涂林便得以使用對角線論證法 (diagonal argument) 證明不可能存在這種特殊的涂林機，也就是說「停機問題」是無解的，再從這裡就可以繼續推論出「判定性問題」也是無解的。

涂林機的正面應用絕不侷限在可計算數的範圍，事實上，通過各種編碼的程序，可以想像的任何機械化演算過程，似乎原則上都可以在涂林機上執行。因此有人主張一切可計算的均是涂林機可計算的，這也就是一般所謂的「丘池－涂林論點」(Church-Turing Thesis)。不過隨著人類對高速及大量計算的經驗累積，這個論點也有重新檢討的需求了。

涂林機的定義，從「認識」的心理圖像上來說，最接近直觀的機械性運算特性。經過後人的繼續開拓，引入計算複雜度的考量，終於發現計算機理論內最核心也最困難的「P=NP?」問題。因此涂林的貢獻超越其他的邏輯學家，成為計算機科學的始祖。