本節書摘來自華章計算機《計算複雜性：現代方法》一書中的第1章，第1.1節，作者 ［美］桑傑夫·阿羅拉（sanjeev arora），博阿茲·巴拉克（boaz barak），譯 駱吉洲，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
初看起來，為計算建立數學模型可謂難上加難。這是由于，曆史上人類在解決各種計算任務的過程中用盡了各種各樣的方法——從直覺和靈感到算盤或計算尺，再到現代的計算機。此外，自然界中其他生物或系統也時刻需要處理各種計算任務，而它們的解決之道也是紛亂繁雜。怎樣才能找出一個能抓住這些計算方法共性的簡潔的數學模型呢？如果再考慮到本書要關注的計算效率問題，則模組化問題就更加無從下手了。考慮計算效率問題似乎必須小心地選擇計算模型，因為即便是孩童也知道一款新的視訊遊戲是否能“高效運作”将依賴于他的計算機硬體。
令人驚訝的是，一個簡潔的計算模型——圖靈機足以研究關于計算及其效率的所有問題。将讨論範圍僅限于這種計算模型的理由是充分的，因為它能夠模拟所有能被實體實作的計算方法而僅在計算效率上略有損失。是以，圖靈機“能高效解決”的計算任務至少與其他計算方法能高效解決的計算任務一樣多（一個可能的例外是第10章讨論的量子計算機模型，但目前還不清楚它能否被實體實作）。
本章将給出圖靈機的形式定義，并研究它的一些基本性質。1.1節概述了圖靈機模型及其基本性質。該小節還為普通讀者概述了1.2節至1.5節的結論，以幫助這些讀者跳過圖靈機模型雜亂的細節而直接從1.6節開始進入複雜性理論。
由于複雜性理論 “complexity”一詞譯做“複雜性”或“複雜度”。當比較抽象地論及“complexity”時譯作“複雜性”，當用具體函數論及“complexity”的高低時，譯作“複雜度”。關注的是計算效率，是以1.6節給出了本書最重要的幾個定義之一，亦即複雜性類p的定義，它從數學上刻畫了由所有能被高效求解的判定問題構成的集合。1.6節還就下面的問題展開了一些讨論：類p是否真的刻畫了“高效計算”這一非正式概念的本質。該小節還表明了圖靈機的定義是如何貫穿全書的；同時還指出，類p是定義很多其他模型的出發點，這些模型包括非确定型圖靈機、機率型圖靈機、量子圖靈機、布爾線路、并行計算機、判定樹和通信遊戲，其中有些模型用于研究實體計算的有争議的實作模式，而另一些則主要用于深入了解圖靈機計算的本質。
形式地讨論圖靈機将不可避免地遇到一些單調乏味的概念。我們先概述這些直覺概念，以便普通讀者可以跳過正式的讨論而直接進入從1.6節開始的複雜性理論。當他們在閱讀後續章節的過程中偶爾遇到确實需要圖靈機模型的細節時，可以随時回頭閱讀跳過的小節。
千百年來，“計算”這個詞曾一直被了解為将機械的規則作用于操作數上，其中完成操作的人或機器允許使用演草紙來記錄中間結果。圖靈機是這種直覺概念的具體實作。1.2.1節表明，圖靈機等價于任何一種現代程式設計語言——除了對記憶體大小沒有限制之外。
下面，我們按照本章開頭所引用的圖靈的話非正式地描述圖靈機模型。令f是一個以位串（即{0,1}中的成員）為輸入而以0或1為輸出的函數。計算f的一個算法是一組機械的規則，根據這組規則我們可以為任意輸入x∈{0,1}計算函數值f(x)。所采用的計算規則是固定不變的（即同一組規則必須适用于所有輸入），盡管其中每條規則被使用的次數是任意的。每條規則将用到如下定義的一個或多個“基本”操作：
1.從輸入中讀取一個位；
2.從算法使用的演草紙或工作空間中讀取一個位（也可能是某個更大的字母表中的一個符号，例如集合{0,…,9}中的一個十進制位）。
根據讀取的值，
1.在草稿紙上寫出一個位或符号；
2.要麼停機并輸出0或1，要麼重新選擇下一步要執行的計算規則。
最後，圖靈機的運作時間指的是上述基本操作被執行的次數。我們采用漸進術語描述運作時間。是以，如果圖靈機在長度為n的輸入上至多執行t(n)個基本操作，則稱該圖靈機的運作時間為t(n)。
下面列舉圖靈機模型的一些簡單事實。
4.簡單地利用前面兩個事實可以證明，存在不能被任何圖靈機計算的函數，見1.5節。不可計算性與著名的哥德爾不完全定理關系密切，見1.5.2節。