圖靈機(jī)的形式化
一臺圖靈機(jī)是一個七元組?[2]?酸茴，{Q，Σ兢交，Γ薪捍，δ，q0,qaccept,qreject}配喳，其中 Q飘诗，Σ，Γ 都是有限集合界逛，且滿足
1.Q 是狀態(tài)集合昆稿；
2.Σ 是輸入字母表，其中不包含特殊的空白符息拜；
3.Γ 是帶字母表溉潭，其中 □∈Γ且Σ∈Γ 净响；
4. δ：Q×「→Q×Γ×{L,R}是轉(zhuǎn)移函數(shù)喳瓣，其中L,R 表示讀寫頭是向左移還是向右移馋贤；
5.q0∈Q是起始狀態(tài)；
6. qaccept是接受狀態(tài)畏陕。
7.qreject是拒絕狀態(tài)配乓，且qreject≠qaccept。?[3]
圖靈機(jī) M = (Q惠毁，Σ犹芹，Γ，δ鞠绰，q0,qaccept,qreject) 將以如下方式運(yùn)作：
開始的時候?qū)⑤斎敕柎?從左到右依此填在紙帶的第 號格子上腰埂， 其他格子保持空白（即填以空白符）。M 的讀寫頭指向第 0 號格子蜈膨， M 處于狀態(tài) q0屿笼。機(jī)器開始運(yùn)行后，按照轉(zhuǎn)移函數(shù) δ 所描述的規(guī)則進(jìn)行計算翁巍。例如驴一，若當(dāng)前機(jī)器的狀態(tài)為 q，讀寫頭所指的格子中的符號為 x灶壶， 設(shè) δ（q,x) = (q',x',L）肝断， 則機(jī)器進(jìn)入新狀態(tài) q'， 將讀寫頭所指的格子中的符號改為 x'例朱， 然后將讀寫頭向左移動一個格子孝情。若在某一時刻鱼蝉，讀寫頭所指的是第 0 號格子洒嗤， 但根據(jù)轉(zhuǎn)移函數(shù)它下一步將繼續(xù)向左移，這時它停在原地不動魁亦。換句話說渔隶，讀寫頭始終不移出紙帶的左邊界。若在某個時刻 M 根據(jù)轉(zhuǎn)移函數(shù)進(jìn)入了狀態(tài) qaccept洁奈， 則它立刻停機(jī)并接受輸入的字符串间唉； 若在某個時刻 M 根據(jù)轉(zhuǎn)移函數(shù)進(jìn)入了狀態(tài) qreject， 則它立刻停機(jī)并拒絕輸入的字符串利术。
注意呈野，轉(zhuǎn)移函數(shù) δ 是一個部分函數(shù)， 換句話說對于某些 q,x印叁， δ（q,x) 可能沒有定義被冒， 如果在運(yùn)行中遇到下一個操作沒有定義的情況军掂， 機(jī)器將立刻停機(jī)。
