1935年，22歲的圖靈寫出了《論可計算數(shù)及其在判定問題上的應用》，并從數(shù)學和邏輯上定義了著名的“圖靈機”缕允。今天所有的計算機，包括全世界正在設(shè)計的新的計算機蹭越，從解決問題的能力來講障本，都沒有超出圖靈機的范疇。
圖靈為什么會提出這種數(shù)學模型响鹃，是因為他受到了兩個人的影響驾霜。
在1900年的巴黎國際數(shù)學大會上，數(shù)學大師希爾伯特提出23個重要的买置、根本性的數(shù)學問題粪糙，其中第十個是“隨便給一個不確定的方程，能夠通過有限步的運算堕义，判斷它是否存在整數(shù)解猜旬？”如果這個問題的答案是否定的脆栋，那么意味著有些問題時無解的倦卖。正是因為對這個問題的深刻認識，讓圖靈認識到計算機的能力存在極限椿争。后來在1970年怕膛，前蘇聯(lián)偉大的數(shù)學家馬季亞謝維奇從數(shù)學上解決了希爾伯特的那個問題。也就是說秦踪，的的確確有很多數(shù)學問題褐捻，根本沒有答案，而且這樣的問題比有答案的問題還要多得多椅邓。
1936年柠逞，圖靈應邀到美國普林斯頓高級研究院學習，在他讀了馮?諾依曼的《量子力學的數(shù)學原理》一書后景馁，意識到計算來自于確定性的機械的運動板壮。同時，圖靈猜測人的意識來自于測不準原理合住，這是宇宙本身的規(guī)律绰精。圖靈從此得出結(jié)論撒璧，計算是確定的，而意識可以是不定的笨使，兩者不可能劃等號卿樱。
正是長在數(shù)學大師希爾伯特和馮·諾依曼的影響下，圖靈將精力全力放在確定的可計算問題上硫椰，這相當于給其他人和后人指明了一條計算機的發(fā)展方向繁调，以避免人們走彎路。而他在《論可計算數(shù)及其在判定問題上的應用》論文中提出的可實施自動計算的思維機器靶草，便是對這類問題的一種通用解法涉馁，其由以下幾部分組成：
1．一條無限長的紙帶，它被劃分為一個接一個的小格子爱致，每一個格子有一個編號烤送，比如從左到右依次為0, 1, 2. …，其實我們今天在計算機中所說的地址糠悯，就可以理解為這種編號的一種實現(xiàn)方式帮坚。注意：這個紙帶可以無限往右延伸，它相當于我們做數(shù)學運算的紙互艾，但這種運算紙的數(shù)量可以是無限的试和，而計算機的存儲容量是有限的。
2．一個可以左右自由移動的讀寫頭纫普，它能讀取當前所指格子中的符號阅悍，并能改變它們。這個讀寫頭昨稼，就相當于筆和橡皮节视。
3．一套控制規(guī)則，它根據(jù)當前機器所處的狀態(tài)和當前格子中的內(nèi)容假栓，確定讀寫頭下一步的動作寻行。這套規(guī)則就相當于做題的法則，比如我們做珠算時使用的“三下五除二”這樣的口訣匾荆，就是運算規(guī)則拌蜘。
4．一組狀態(tài)寄存器，它用來保存圖靈機當前所處的狀態(tài)牙丽。我們在紙上計算數(shù)學題時简卧，經(jīng)常要問自己，算到哪兒了烤芦？寄存器所記錄的就是這樣的狀態(tài)举娩。當它遇到一個特殊狀態(tài)，即所謂的停機狀態(tài)時，整個運算就結(jié)束了晓铆。
圖靈機的操作過程如下：
1．一開始勺良，將輸入符號串從左到右依次填入紙帶的前n個格子中（其他格子保持空白）。
2．讀寫頭指向第0號格子骄噪，圖靈機處于初始狀態(tài)q0尚困。
3．機器開始運行后，按照轉(zhuǎn)移函數(shù)所描述的規(guī)則進行計算链蕊。
例如事甜，假定當前機器的狀態(tài)為q，讀寫頭所指的格子中的符號為x滔韵，根據(jù)轉(zhuǎn)移函數(shù)δ（q, x）逻谦，我們得到其函數(shù)值（q', x',左移/右移）。于是陪蜻，接下來進入q'狀態(tài)邦马，當前格子的內(nèi)容改為x'，然后將指針左移或右移宴卖。這樣圖靈機就進入了一個新的狀態(tài)滋将。如果q'是終止狀態(tài)集合F中的一個元素，則圖靈機停機症昏，如果正好是成功狀態(tài)随闽，則運算完成，否則說明運算不下去肝谭。如果運算到某一步掘宪，遇到了沒有定義轉(zhuǎn)移函數(shù)的情況，也說明運算失敗攘烛，立即停機魏滚。
這完全是一臺思維機器，圖靈當時并不關(guān)系具體的物理實現(xiàn)医寿，甚至很排斥和別人討論這些“細枝末節(jié)”的問題栏赴。這是因為他在用邏輯模擬大腦的思考過程蘑斧，只要這個邏輯過程被證明是合理且完整的靖秩，那么后面可以對其進行無限擴展。
圖靈這種高屋建瓴式的“頂層設(shè)計”對計算機日后的高速發(fā)展奠定了基本的理論基礎(chǔ)竖瘾。當然沟突，被譽為計算機科學之父和人工智能之父的他還要很多杰出成就，不過他的人生卻過得并不順利——過早的隕落捕传，對整個人類都是一種損失惠拭。
