คลาสของออโตมาตา

เครื่องจักรทัวริงเป็นแบบจำลองทางคณิตศาสตร์ของการคำนวณที่อธิบายเครื่องจักรนามธรรม^{[ 1 ]}ที่จัดการสัญลักษณ์บนแถบเทปตามตารางกฎ^{[ 2 ]}แม้ว่าแบบจำลองจะเรียบง่าย แต่ก็สามารถนำอัลกอริทึมคอมพิวเตอร์ ใดๆ มาใช้ ก็ได้^{[ 3 ]}

เครื่องจักรทำงานบนเทปหน่วยความจำอนันต์^{[ 4 ]}ที่แบ่งออกเป็นเซลล์แยกกัน^{[ 5 ]}แต่ละเซลล์สามารถเก็บสัญลักษณ์เดียวที่ดึงมาจาก ชุด สัญลักษณ์ที่จำกัด ซึ่งเรียกว่า ตัวอักษรของเครื่องจักร เครื่องจักรมี "หัว" ที่ ณ จุดใดจุดหนึ่งของการทำงานของเครื่องจักร จะวางอยู่เหนือเซลล์ใดเซลล์หนึ่งเหล่านี้ และมี "สถานะ" ที่เลือกจากชุดสถานะที่จำกัด ในแต่ละขั้นตอนของการทำงาน หัวจะอ่านสัญลักษณ์ในเซลล์ จากนั้น โดยอิงจากสัญลักษณ์และสถานะปัจจุบันของเครื่องจักร เครื่องจักรจะเขียนสัญลักษณ์ลงในเซลล์เดียวกัน และเลื่อนหัวไปทางซ้ายหรือขวาหนึ่งขั้น^{[ 6 ]}หรือหยุดการคำนวณ การเลือกสัญลักษณ์ทดแทนที่จะเขียน ทิศทางที่จะเลื่อนหัว และว่าจะหยุดหรือไม่นั้นขึ้นอยู่กับตารางที่จำกัดซึ่งระบุสิ่งที่ต้องทำสำหรับแต่ละการรวมกันของสถานะปัจจุบันและสัญลักษณ์ที่อ่านได้ เช่นเดียวกับโปรแกรมคอมพิวเตอร์จริง เครื่องจักรทัวริงสามารถเข้าสู่ลูปอนันต์ซึ่งจะไม่หยุดลงได้

เครื่องจักรทัวริงถูกประดิษฐ์ขึ้นในปี พ.ศ. 2479 โดยอลัน ทัวริง [ ^{7 ] [ 11 ] ซึ่ง}เรียกมันว่า "เครื่องจักรอัตโนมัติ" ^{[ 12 ]}อลอนโซ เชิร์ชที่ปรึกษาปริญญาเอกของทัวริงเป็นผู้บัญญัติศัพท์ "เครื่องจักรทัวริง" ในบทวิจารณ์ในภายหลัง^{[ 13 ]}ด้วยแบบจำลองนี้ ทัวริงสามารถตอบคำถามสองข้อในเชิงลบได้:

• มีเครื่องจักรใดบ้างที่สามารถตรวจสอบได้ว่าเครื่องจักรใดๆ บนเทปของมัน "ทำงานผิดปกติ" (เช่น ค้าง หรือไม่สามารถดำเนินการคำนวณต่อได้)?
• มีเครื่องจักรที่สามารถระบุได้หรือไม่ว่าเครื่องจักรใดๆ บนเทปของมันเคยพิมพ์สัญลักษณ์ที่กำหนดหรือไม่? ^{[ 14 ] [ 15 ]}

ดังนั้นด้วยการให้คำอธิบายทางคณิตศาสตร์ของอุปกรณ์ที่เรียบง่ายมากซึ่งสามารถคำนวณได้ตามอำเภอใจ เขาจึงสามารถพิสูจน์คุณสมบัติของการคำนวณโดยทั่วไปได้ และโดยเฉพาะอย่างยิ่งความไม่สามารถคำนวณได้ของปัญหาEntscheidungsproblemหรือ 'ปัญหาการตัดสินใจ' (ไม่ว่าข้อความทางคณิตศาสตร์ทุกข้อความจะพิสูจน์ได้หรือหักล้างไม่ได้) ^{[ 16 ]}

เครื่องจักรทัวริงพิสูจน์ให้เห็นถึงข้อจำกัดพื้นฐานเกี่ยวกับพลังของการคำนวณเชิงกล^{[ 3 ]}

แม้ว่าเครื่องจักรทัวริงจะสามารถแสดงผลการคำนวณใดๆ ก็ได้ แต่การออกแบบที่เรียบง่ายทำให้มันช้าเกินไปสำหรับการคำนวณในทางปฏิบัติคอมพิวเตอร์ ในโลกแห่งความเป็นจริง นั้นใช้การออกแบบที่แตกต่างออกไป ซึ่งแตกต่างจากเครื่องจักรทัวริงตรงที่ใช้หน่วยความจำแบบเข้าถึงโดยสุ่ม (RAM )

ความสมบูรณ์แบบของทัวริง (Turing completeness)คือความสามารถของแบบจำลองการคำนวณหรือระบบคำสั่งในการจำลองเครื่องจักรทัวริง ภาษาโปรแกรมที่สมบูรณ์แบบของทัวริงนั้น ในทางทฤษฎีแล้วสามารถแสดงงานทั้งหมดที่คอมพิวเตอร์สามารถทำได้ ภาษาโปรแกรมเกือบทั้งหมดมีความสมบูรณ์แบบของทัวริง หากไม่คำนึงถึงข้อจำกัดของหน่วยความจำที่มีจำกัด

เครื่องจักรทัวริงเป็นแบบจำลองในอุดมคติของหน่วยประมวลผลกลาง (CPU) ที่ควบคุมการประมวลผลข้อมูลทั้งหมดที่ดำเนินการโดยคอมพิวเตอร์ โดยเครื่องจักรต้นแบบใช้หน่วยความจำแบบลำดับเพื่อจัดเก็บข้อมูล โดยทั่วไป หน่วยความจำแบบลำดับจะถูกแทนด้วยเทปที่มีความยาวอนันต์ ซึ่งเครื่องจักรสามารถดำเนินการอ่านและเขียนข้อมูลได้

ในบริบทของ ทฤษฎี ภาษาเชิงรูปธรรมเครื่องจักรทัวริง ( ออโตมาตอน ) สามารถแจงนับชุดย่อยใดๆ ของสตริงที่ถูกต้องของตัวอักษร ได้ ชุดของสตริงที่สามารถแจงนับได้ในลักษณะนี้เรียกว่าภาษาที่แจงนับได้แบบเรียกซ้ำเครื่องจักรทัวริงสามารถนิยามได้อีกอย่างหนึ่งว่าเป็นแบบจำลองที่รับรู้สตริงอินพุตที่ถูกต้อง แทนที่จะแจงนับสตริงเอาต์พุต

เมื่อกำหนดเครื่องจักรทัวริงMและสตริงs ใดๆ แล้ว โดยทั่วไปแล้วเป็นไปไม่ได้ที่จะตัดสินว่าMจะสร้างs ออกมาในที่สุดหรือไม่ เนื่องจากปัญหาการหยุดทำงานนั้นไม่สามารถแก้ไขได้ ซึ่งส่งผลกระทบอย่างมากต่อขีดจำกัดทางทฤษฎีของการคำนวณ

เครื่องจักรทัวริงที่สามารถจำลองเครื่องจักรทัวริงอื่นๆ ได้ทุกเครื่อง เรียกว่าเครื่องจักรทัวริงสากล (UTM หรือเรียกง่ายๆ ว่า เครื่องจักรสากล) อีกรูปแบบทางคณิตศาสตร์หนึ่งที่มีลักษณะ "สากล" คล้ายกัน คือแคลคูลัสแลมบ์ดา ซึ่งคิดค้นโดย อลอนโซ เชิร์ชงานของเชิร์ชผสานกับงานของทัวริงจนก่อให้เกิดพื้นฐานของวิทยานิพนธ์เชิร์ช-ทัวริงวิทยานิพนธ์นี้กล่าวว่า เครื่องจักรทัวริง แคลคูลัสแลมบ์ดา และรูปแบบการคำนวณ อื่นๆ ที่คล้ายคลึงกัน นั้น สามารถจับแนวคิดที่ไม่เป็นทางการของวิธีการที่มีประสิทธิภาพในตรรกศาสตร์และคณิตศาสตร์ ได้ และด้วยเหตุนี้จึงเป็นแบบจำลองที่สามารถใช้ในการให้เหตุผลเกี่ยวกับอัลกอริทึมหรือ "กระบวนการเชิงกล" ในเชิงคณิตศาสตร์ที่แม่นยำโดยไม่ต้องผูกติดกับรูปแบบใดรูปแบบหนึ่งโดยเฉพาะ การศึกษา คุณสมบัติเชิงนามธรรมของเครื่องจักรทัวริงได้ก่อให้เกิดความเข้าใจอย่างลึกซึ้งมากมายในวิทยาศาสตร์คอมพิวเตอร์ทฤษฎีความสามารถในการคำนวณและ ทฤษฎีความซับซ้อน

ในบทความเรื่อง "เครื่องจักรที่ชาญฉลาด" ที่เขียนขึ้นในปี 1948 ทิวริงเขียนไว้ว่าเครื่องจักรของเขานั้นประกอบด้วย:

...ความจุหน่วยความจำไม่จำกัดที่ได้มาในรูปแบบของเทปอนันต์ที่ทำเครื่องหมายเป็นช่องสี่เหลี่ยม ซึ่งแต่ละช่องสามารถพิมพ์สัญลักษณ์ได้ ในแต่ละช่วงเวลาจะมีสัญลักษณ์หนึ่งตัวอยู่ในเครื่อง เรียกว่าสัญลักษณ์ที่สแกนแล้ว เครื่องสามารถเปลี่ยนแปลงสัญลักษณ์ที่สแกนแล้วได้ และพฤติกรรมของเครื่องส่วนหนึ่งถูกกำหนดโดยสัญลักษณ์นั้น แต่สัญลักษณ์บนเทปที่อื่นจะไม่ส่งผลต่อพฤติกรรมของเครื่อง อย่างไรก็ตาม เทปสามารถเลื่อนไปมาผ่านเครื่องได้ ซึ่งเป็นหนึ่งในการทำงานพื้นฐานของเครื่อง ดังนั้นสัญลักษณ์ใดๆ บนเทปจึงอาจมีรอบการเล่นได้ในที่สุด^{[ 17 ]}

เครื่องจักรทัวริงเป็นแบบจำลองทางคณิตศาสตร์ของเครื่องจักรที่ทำงานเชิงกลบนเทป บนเทปนี้มีสัญลักษณ์ ซึ่งเครื่องจักรสามารถอ่านและเขียนได้ทีละตัวโดยใช้หัวอ่านเทป การทำงานถูกกำหนดอย่างสมบูรณ์โดยชุดคำสั่งพื้นฐานจำนวนจำกัด เช่น "ในสถานะ 42 ถ้าสัญลักษณ์ที่เห็นคือ 0 ให้เขียน 1; ถ้าสัญลักษณ์ที่เห็นคือ 1 ให้เปลี่ยนเป็นสถานะ 17; ในสถานะ 17 ถ้าสัญลักษณ์ที่เห็นคือ 0 ให้เขียน 1 และเปลี่ยนเป็นสถานะ 6" เป็นต้น ในบทความต้นฉบับ (" เกี่ยวกับจำนวนที่คำนวณได้ พร้อมการประยุกต์ใช้กับปัญหาการตัดสินใจ " โปรดดูเอกสารอ้างอิงด้านล่าง ) ทัวริงไม่ได้จินตนาการถึงกลไก แต่เป็นบุคคลที่เขาเรียกว่า "คอมพิวเตอร์" ซึ่งดำเนินการตามกฎเชิงกลที่กำหนดไว้เหล่านี้อย่างเคร่งครัด (หรือตามที่ทัวริงกล่าวไว้ว่า "ในลักษณะที่ไม่เป็นระบบ")

กล่าวโดยละเอียดแล้ว เครื่องจักรทัวริงประกอบด้วย:

• เทป ถูกแบ่งออกเป็นช่องๆ เรียงต่อกัน แต่ละช่องบรรจุสัญลักษณ์จากชุดตัวอักษรจำกัด ชุดตัวอักษรนี้ประกอบด้วยสัญลักษณ์ว่างพิเศษ (ในที่นี้เขียนว่า '0') และสัญลักษณ์อื่นๆ อีกหนึ่งตัวหรือมากกว่านั้น เทปนั้นถือว่าสามารถขยายออกไปทางซ้ายและขวาได้อย่างไม่จำกัด เพื่อให้เครื่องจักรทัวริงได้รับเทปเพียงพอสำหรับการคำนวณเสมอ ช่องที่ยังไม่ได้เขียนข้อมูลจะถือว่าเต็มไปด้วยสัญลักษณ์ว่าง ในบางแบบจำลอง เทปจะมีปลายด้านซ้ายที่ทำเครื่องหมายด้วยสัญลักษณ์พิเศษ เทปจะขยายออกไปหรือสามารถขยายออกไปทางขวาได้อย่างไม่จำกัด
• หัวอ่านและเขียนสัญลักษณ์บนเทป และเลื่อนเทปไปทางซ้ายและขวาครั้งละหนึ่งเซลล์ (และเพียงหนึ่งเซลล์เท่านั้น) ในบางรุ่น หัวอ่านจะเคลื่อนที่ แต่เทปจะอยู่กับที่
• รีจิสเตอร์สถานะที่เก็บสถานะของเครื่องจักรทัวริง ซึ่งเป็นหนึ่งในสถานะจำนวนจำกัด หนึ่งในนั้นคือสถานะเริ่มต้น พิเศษ ซึ่งใช้ในการเริ่มต้นรีจิสเตอร์สถานะ ทัวริงเขียนไว้ว่า สถานะเหล่านี้เข้ามาแทนที่ "สภาวะจิตใจ" ที่บุคคลที่ทำการคำนวณโดยปกติจะมี
• ตารางคำสั่งจำกัด^{[ 19 ] [ 20 ]}ที่กำหนดสถานะ (q _i ) ที่เครื่องอยู่ในปัจจุบันและสัญลักษณ์(a _{j ) ที่กำลังอ่านบนเทป (} สัญลักษณ์ที่อยู่ใต้หัวอ่านในปัจจุบัน) จะบอกให้เครื่องทำสิ่งต่อไปนี้ตามลำดับ (สำหรับโมเดล 5- tuple ):

1. ลบหรือเขียนสัญลักษณ์ (แทนที่_jด้วย_j1 )
2. ขยับหัว (ซึ่งอธิบายด้วย d _kและสามารถมีค่าได้ดังนี้: 'L' สำหรับก้าวซ้ายหนึ่งก้าวหรือ 'R' สำหรับก้าวขวาหนึ่งก้าวหรือ 'N' สำหรับอยู่กับที่)
3. สมมติสถานะเดิมหรือสถานะใหม่ตามที่กำหนด (ไปที่สถานะ q _i1 )

ในแบบจำลอง 4-tuple การลบหรือเขียนสัญลักษณ์ (a _j1 ) และการเคลื่อนหัวอ่านไปทางซ้ายหรือขวา (d _k ) จะถูกกำหนดเป็นคำสั่งแยกกัน ตารางจะบอกให้เครื่อง (ia) ลบหรือเขียนสัญลักษณ์หรือ (ib) เคลื่อนหัวอ่านไปทางซ้ายหรือขวาแล้ว (ii) เปลี่ยนสถานะเป็นสถานะเดิมหรือสถานะใหม่ตามที่กำหนด แต่ไม่ใช่การกระทำทั้งสอง (ia) และ (ib) ในคำสั่งเดียวกัน ในบางแบบจำลอง หากไม่มีรายการในตารางสำหรับสัญลักษณ์และสถานะปัจจุบัน เครื่องจะหยุดทำงาน ในขณะที่แบบจำลองอื่นๆ กำหนดให้ต้องกรอกข้อมูลในทุกรายการ

ทุกส่วนของเครื่องจักร (เช่น สถานะ ชุดสัญลักษณ์ และเทปที่ใช้ในแต่ละช่วงเวลา) และการกระทำต่างๆ (เช่น การพิมพ์ การลบ และการเคลื่อนที่ของเทป) นั้นมีขอบเขตจำกัดแยกจากกันและสามารถแยกแยะได้ แต่ปริมาณเทปและเวลาการทำงานที่ไม่จำกัดต่างหากที่ทำให้เครื่องจักร มีพื้นที่จัดเก็บข้อมูลไม่ จำกัด

ตาม Hopcroft & Ullman (1979) ^{[ 21 ]}เครื่องจักรทัวริง (เทปเดียว) สามารถกำหนดอย่างเป็นทางการได้เป็น 7- tuple โดยที่ ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle Q}$เป็นเซตของ สถานะที่มีจำนวนจำกัดและไม่ว่างเปล่า
• ${\displaystyle \Gamma }$เป็นเซตจำกัดที่ไม่ว่างเปล่าของสัญลักษณ์ตัวอักษรเทป
• ${\displaystyle b\in \Gamma }$คือสัญลักษณ์ว่าง (สัญลักษณ์เดียวที่อนุญาตให้ปรากฏบนเทปได้ไม่จำกัดจำนวนครั้งในทุกขั้นตอนของการคำนวณ)
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$คือเซตของสัญลักษณ์อินพุตซึ่งก็คือเซตของสัญลักษณ์ที่อนุญาตให้ปรากฏในเนื้อหาเทปเริ่มต้น
• ${\displaystyle \delta :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}}$เป็นฟังก์ชันบางส่วนที่เรียกว่าฟังก์ชันการเปลี่ยนผ่านโดยที่ L คือการเลื่อนไปทางซ้าย และ R คือการเลื่อนไปทางขวา หากไม่ได้กำหนดไว้ในสถานะปัจจุบันและสัญลักษณ์เทปปัจจุบัน เครื่องจะหยุดทำงาน^{[ 22 ]}โดยสัญชาตญาณ ฟังก์ชันการเปลี่ยนผ่านจะระบุสถานะถัดไปที่เปลี่ยนผ่านจากสถานะปัจจุบัน สัญลักษณ์ที่จะเขียนทับสัญลักษณ์ปัจจุบันที่ชี้โดยหัวอ่าน และการเคลื่อนที่ของหัวอ่านครั้งต่อไป${\displaystyle \delta }$
• ${\displaystyle q_{0}\in Q}$คือสถานะเริ่มต้น ;
• ${\displaystyle F\subseteq Q}$คือเซตของสถานะสุดท้ายหรือสถานะที่ยอมรับได้เนื้อหาเทปเริ่มต้นจะถือว่าได้รับการยอมรับโดยหากในที่สุดมันหยุดลงในสถานะใดสถานะหนึ่งจาก${\displaystyle M}$${\displaystyle F}$

รูปแบบหนึ่งอนุญาตให้ "ไม่มีการเลื่อน" เช่น N เป็นองค์ประกอบที่สามของชุดทิศทาง ${\displaystyle \{L,R\}}$

ทูเพิล 7 ตัวสำหรับ Busy Beaver 3 สถานะมีลักษณะดังนี้ (ดูรายละเอียดเพิ่มเติมเกี่ยวกับ Busy Beaver นี้ได้ที่ตัวอย่างเครื่องจักรทัวริง ):

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$(รัฐต่างๆ);
• ${\displaystyle \Gamma =\{0,1\}}$(สัญลักษณ์ตัวอักษรเทป);
• ${\displaystyle b=0}$(สัญลักษณ์ว่างเปล่า);
• ${\displaystyle \Sigma =\{1\}}$(สัญลักษณ์อินพุต);
• ${\displaystyle \delta =}$ดูตารางสถานะด้านล่าง (ฟังก์ชันการเปลี่ยนสถานะ)
• ${\displaystyle q_{0}={\mbox{A}}}$(สถานะเริ่มต้น);
• ${\displaystyle F=\{{\mbox{HALT}}\}}$(สถานะสุดท้าย);

ในขั้นต้น เซลล์เทปทั้งหมดจะถูกทำเครื่องหมายด้วย. ${\displaystyle 0}$

ตามคำกล่าวของ van Emde Boas (1990): "วัตถุเชิงทฤษฎีเซต [คำอธิบายเจ็ดทูเพิลอย่างเป็นทางการของเขาที่คล้ายกับข้างต้น] ให้ข้อมูลเพียงบางส่วนเกี่ยวกับพฤติกรรมของเครื่องจักรและลักษณะของการคำนวณ" ^{[ 23 ]}

ตัวอย่างเช่น

• จะต้องมีการตัดสินใจหลายอย่างเกี่ยวกับลักษณะของสัญลักษณ์เหล่านั้น และจะต้องมีวิธีการอ่านและเขียนสัญลักษณ์ที่เชื่อถือได้ตลอดไป
• การดำเนินการเลื่อนไปทางซ้ายและเลื่อนไปทางขวาอาจทำให้หัวอ่านเทปเลื่อนไปตามเทป แต่ในการสร้างเครื่องจักรทัวริงจริง ๆ แล้ว การทำให้เทปเลื่อนไปมาใต้หัวอ่านนั้นมีความเหมาะสมมากกว่า
• เทปอาจมีขนาดจำกัด และสามารถขยายออกโดยอัตโนมัติด้วยช่องว่างตามต้องการ (ซึ่งใกล้เคียงกับคำจำกัดความทางคณิตศาสตร์มากที่สุด) แต่โดยทั่วไปแล้วมักจะคิดว่ามันยืดออกไปอย่างไม่มีที่สิ้นสุดที่ปลายด้านใดด้านหนึ่งหรือทั้งสองด้าน และถูกเติมด้วยช่องว่างไว้ล่วงหน้า ยกเว้นในส่วนที่จำกัดซึ่งระบุไว้อย่างชัดเจนซึ่งหัวอ่านเทปอยู่ (แน่นอนว่าในทางปฏิบัติแล้วไม่สามารถนำไปใช้ได้จริง) เทปไม่สามารถมีความยาวคงที่ได้ เนื่องจากจะไม่สอดคล้องกับคำจำกัดความที่กำหนดไว้ และจะจำกัดขอบเขตการคำนวณที่เครื่องสามารถทำได้ให้เหลือเพียงการคำนวณของออโตมาตาเชิงเส้นที่มีขอบเขตหากเทปเป็นสัดส่วนกับขนาดของอินพุต หรือเครื่องสถานะจำกัดหากเทปมีความยาวคงที่อย่างเคร่งครัด

ในเอกสารทางวิชาการบางครั้งคำจำกัดความอาจแตกต่างกันเล็กน้อย เพื่อให้การโต้แย้งหรือการพิสูจน์ง่ายขึ้นหรือชัดเจนขึ้น แต่การเปลี่ยนแปลงนี้จะทำในลักษณะที่เครื่องที่ได้มีกำลังการคำนวณเท่าเดิมเสมอ ตัวอย่างเช่น ชุดอาจเปลี่ยนจากเป็น โดยที่N ("ไม่มี" หรือ "ไม่มีการดำเนินการ") จะทำให้เครื่องอยู่บนเซลล์เทปเดิมแทนที่จะเลื่อนไปทางซ้ายหรือขวา ซึ่งจะไม่เพิ่มกำลังการคำนวณของเครื่อง ${\displaystyle \{L,R\}}$${\displaystyle \{L,R,N\}}$

ธรรมเนียมปฏิบัติที่พบได้บ่อยที่สุดจะแสดง "คำสั่ง Turing" แต่ละคำสั่งใน "ตาราง Turing" โดยใช้ 5-tuple หนึ่งในเก้าชุด ตามธรรมเนียมของ Turing/Davis (Turing (1936) ^{[ 24 ]}และ Davis (2000) ^{[ 25 ]} ):

(นิยาม 1): (q _i , S _j , S _k /E/N, L/R/N, q _m )

(สถานะปัจจุบันq _i ,สัญลักษณ์ที่สแกนS _j ,พิมพ์สัญลักษณ์S _k /ลบE /ไม่มีN ,ย้ายเทปหนึ่งช่องซ้ายL /ขวาR /ไม่มีN ,สถานะใหม่q _m )

ผู้เขียนอื่นๆ (Minsky (1967), ^{[ 26 ]} Hopcroft และ Ullman (1979), ^{[ 27 ]} Stone (1972), ^{[ 28 ]}ใช้ธรรมเนียมที่แตกต่างออกไป โดยระบุสถานะใหม่q _mไว้ทันทีหลังจากสัญลักษณ์ที่สแกน S _j :

(นิยาม 2): (q _i , S _j , q _m , S _k /E/N, L/R/N)

(สถานะปัจจุบันq _i ,สัญลักษณ์ที่สแกนS _j ,สถานะใหม่q _m ,พิมพ์สัญลักษณ์S _k /ลบE /ไม่มีN ,ย้ายเทปหนึ่งช่องซ้ายL /ขวาR /ไม่มีN )

สำหรับส่วนที่เหลือของบทความนี้ จะใช้ "นิยามที่ 1" (ตามแบบแผนของทัวริง/เดวิส)

ในตารางต่อไปนี้ โมเดลต้นฉบับของ Turing อนุญาตให้ใช้เพียงสามบรรทัดแรกที่เขาเรียกว่า N1, N2, N3 เท่านั้น^{[ 29 ]}เขาอนุญาตให้ลบ "สี่เหลี่ยมที่สแกน" โดยการตั้งชื่อสัญลักษณ์ที่ 0 ว่า S ₀ = "ลบ" หรือ "ว่างเปล่า" เป็นต้น อย่างไรก็ตาม เขาไม่อนุญาตให้ไม่พิมพ์ ดังนั้นทุกบรรทัดคำสั่งจึงรวมถึง "สัญลักษณ์การพิมพ์ S _k " หรือ "ลบ" ^{[ 31 ]}ตัวย่อเหล่านี้เป็นของ Turing ^{[ 32 ]}หลังจากบทความต้นฉบับของ Turing ในปี 1936–1937 โมเดลเครื่องจักรได้อนุญาตให้ใช้ 5-tuple ทั้งเก้าประเภทที่เป็นไปได้ทั้งหมด:

ตารางทัวริง (รายการคำสั่ง) ใดๆ ก็สามารถสร้างขึ้นได้จากทูเพิล 5 ตัวทั้งเก้าข้างต้น ด้วยเหตุผลทางเทคนิค คำสั่งที่ไม่แสดงผลหรือ "N" สามคำสั่ง (4, 5, 6) มักจะสามารถละเว้นได้ สำหรับตัวอย่าง โปรดดูที่ตัวอย่างเครื่องจักรทัวริง

การใช้ทูเพิล 4 ตัวนั้นพบได้ไม่บ่อยนัก: ซึ่งแสดงถึงการแยกย่อยคำสั่งของ Turing ออกไปอีก^{[ 33 ]}

คำว่า "สถานะ" ที่ใช้ในบริบทของเครื่องจักรทัวริงอาจทำให้เกิดความสับสนได้ เนื่องจากมีความหมายได้สองอย่าง นักวิจารณ์ส่วนใหญ่หลังจากทัวริงใช้คำว่า "สถานะ" ในความหมายของชื่อ/ตัวกำหนดคำสั่งปัจจุบันที่จะดำเนินการ นั่นคือ เนื้อหาของรีจิสเตอร์สถานะ แต่ทัวริง (1936) ได้แยกความแตกต่างอย่างชัดเจนระหว่างบันทึกสิ่งที่เขาเรียกว่า "การกำหนดค่า m" ของเครื่องจักร และ "สถานะความคืบหน้า" ของเครื่องจักร (หรือบุคคล) ในการคำนวณ ซึ่งก็คือสถานะปัจจุบันของระบบทั้งหมด สิ่งที่ทัวริงเรียกว่า "สูตรสถานะ" นั้นรวมทั้งคำสั่งปัจจุบันและสัญลักษณ์ ทั้งหมด บนเทปด้วย

ดังนั้น สถานะความคืบหน้าของการคำนวณในแต่ละขั้นตอนจึงถูกกำหนดโดยคำสั่งและสัญลักษณ์บนเทปอย่างสมบูรณ์ กล่าวคือสถานะของระบบสามารถอธิบายได้ด้วยนิพจน์เดียว (ลำดับของสัญลักษณ์) ที่ประกอบด้วยสัญลักษณ์บนเทป ตามด้วย Δ (ซึ่งถือว่าไม่ปรากฏที่อื่น) และจากนั้นตามด้วยคำสั่ง นิพจน์นี้เรียกว่า "สูตรสถานะ"

ก่อนหน้านี้ในบทความของเขา ทิวริงได้ก้าวไปไกลกว่านั้นอีก: เขาให้ตัวอย่างที่เขาวางสัญลักษณ์ของ "การกำหนดค่า m" ปัจจุบัน —ป้ายกำกับคำสั่ง— ไว้ใต้สี่เหลี่ยมที่สแกน พร้อมกับสัญลักษณ์ทั้งหมดบนเทป^{[ 35 ]}เขาเรียกมันว่า " การกำหนดค่าที่สมบูรณ์ " ^{[ 36 ]}เพื่อพิมพ์ "การกำหนดค่าที่สมบูรณ์" บนบรรทัดเดียว เขาวางป้ายกำกับสถานะ/การกำหนดค่า m ไว้ทางซ้ายของสัญลักษณ์ที่สแกน

รูปแบบที่แตกต่างออกไปนี้พบได้ใน Kleene (1952) ซึ่งKleeneแสดงวิธีการเขียนหมายเลข Gödelของ "สถานการณ์" ของเครื่องจักร: เขาวางสัญลักษณ์ "การกำหนดค่า m" q ₄ไว้เหนือช่องสี่เหลี่ยมที่สแกนแล้วซึ่งอยู่กึ่งกลางของช่องสี่เหลี่ยมที่ไม่ว่าง 6 ช่องบนเทปโดยประมาณ (ดูรูปเทป Turing ในบทความนี้) และวางไว้ทางด้านขวาของช่องสี่เหลี่ยมที่สแกนแล้ว^{[ 37 ]}แต่ Kleene อ้างถึง "q ₄ " เองว่าเป็น "สถานะของเครื่องจักร" Hopcroft และ Ullman เรียกส่วนประกอบนี้ว่า "คำอธิบายทันที" และปฏิบัติตามธรรมเนียมของ Turing ในการวาง "สถานะปัจจุบัน" (ป้ายกำกับคำสั่ง การกำหนดค่า m) ไว้ทางด้านซ้ายของสัญลักษณ์ที่สแกนแล้ว (หน้า 149) นั่นคือ คำอธิบายทันทีเป็นส่วนประกอบของสัญลักษณ์ที่ไม่ว่างทางด้านซ้าย สถานะของเครื่องจักร สัญลักษณ์ปัจจุบันที่หัวสแกน และสัญลักษณ์ที่ไม่ว่างทางด้านขวา

ตัวอย่าง: สถานะรวมของ Busy Beaver 3 สถานะ 2 สัญลักษณ์ หลังจาก 3 "การเคลื่อนไหว" (นำมาจากตัวอย่าง "การทำงาน" ในรูปด้านล่าง):

1 A 1

นี่หมายความว่า: หลังจากเคลื่อนที่สามครั้ง เทปจะมี ... 000110000 ... อยู่บนนั้น หัวอ่านกำลังสแกนเลข 1 ตัวขวาสุด และสถานะคือAช่องว่าง (ในกรณีนี้แทนด้วย "0") สามารถเป็นส่วนหนึ่งของสถานะทั้งหมดได้ดังที่แสดงไว้ที่นี่: B 01; เทปมีเลข 1 เพียงตัวเดียว แต่หัวอ่านกำลังสแกนเลข 0 ("ช่องว่าง") ทางด้านซ้าย และสถานะคือ B

ในบริบทของเครื่องจักรทัวริง ควรมีการชี้แจงให้ชัดเจนว่า "สถานะ" นั้นหมายถึงอะไร: คำสั่งปัจจุบัน หรือรายการสัญลักษณ์บนเทปพร้อมกับคำสั่งปัจจุบัน หรือรายการสัญลักษณ์บนเทปพร้อมกับคำสั่งปัจจุบันที่วางอยู่ทางด้านซ้ายของสัญลักษณ์ที่สแกน หรือทางด้านขวาของสัญลักษณ์ที่สแกน

ด้านขวา: ตารางด้านบนที่แสดงในรูปแบบแผนภาพ "การเปลี่ยนสถานะ"

โดยทั่วไปแล้ว ตารางขนาดใหญ่ควรปล่อยไว้ในรูปแบบตาราง (Booth, หน้า 74) เพราะคอมพิวเตอร์สามารถจำลองได้ง่ายกว่าในรูปแบบตาราง (Booth, หน้า 74) อย่างไรก็ตาม แนวคิดบางอย่าง เช่น เครื่องจักรที่มีสถานะ "รีเซ็ต" และเครื่องจักรที่มีรูปแบบซ้ำๆ (ดู Hill และ Peterson หน้า 244 เป็นต้นไป) สามารถมองเห็นได้ชัดเจนยิ่งขึ้นเมื่อดูในรูปแบบภาพวาด

ผู้อ่านต้องเป็นผู้ตัดสินใจเองว่าภาพวาดนั้นแสดงถึงการปรับปรุงจากตารางเดิมหรือไม่ โดยพิจารณาจากบริบทเฉพาะนั้นๆ

ผู้อ่านควรได้รับการเตือนอีกครั้งว่า แผนภาพดังกล่าวแสดงภาพนิ่งของตารางที่หยุดนิ่ง ณ เวลาหนึ่งไม่ใช่เส้นทาง ("วิถี") ของการคำนวณผ่านกาลเวลาและพื้นที่ ในขณะที่เครื่องจักร Busy Beaver ทำงานทุกครั้ง มันจะดำเนินตามวิถีสถานะเดียวกันเสมอ แต่สิ่งนี้ไม่เป็นจริงสำหรับเครื่องจักร "คัดลอก" ที่สามารถป้อน "พารามิเตอร์" ตัวแปรได้

แผนภาพ "ความคืบหน้าของการคำนวณ" แสดงความคืบหน้าของ "สถานะ" (คำสั่ง) ของ Busy Beaver สามสถานะในการคำนวณตั้งแต่ต้นจนจบ ทางด้านขวาสุดคือ "การกำหนดค่าที่สมบูรณ์ของ Turing" ("สถานการณ์" ของ Kleene, "คำอธิบายทันที" ของ Hopcroft–Ullman) ในแต่ละขั้นตอน หากเครื่องหยุดทำงานและล้างทั้ง "รีจิสเตอร์สถานะ" และเทปทั้งหมด "การกำหนดค่า" เหล่านี้สามารถใช้เพื่อเริ่มการคำนวณใหม่ได้ทุกที่ในความคืบหน้า^{[ 38 ]}

เครื่องจักรหลายชนิดที่อาจคิดว่ามีขีดความสามารถในการคำนวณมากกว่าเครื่องจักรทัวริงสากลแบบง่ายๆ นั้น สามารถพิสูจน์ได้ว่าไม่มีพลังการคำนวณมากกว่า (Hopcroft และ Ullman หน้า 159, ดู Minsky (1967)) พวกมันอาจคำนวณได้เร็วกว่า หรือใช้หน่วยความจำน้อยกว่า หรือชุดคำสั่งอาจมีขนาดเล็กกว่า แต่พวกมันไม่สามารถคำนวณได้อย่างมีประสิทธิภาพมากกว่า (เช่น คำนวณฟังก์ชันทางคณิตศาสตร์ได้มากกว่า) ( ทฤษฎีบท Church–Turing ตั้งสมมติฐานว่าสิ่งนี้เป็นจริงสำหรับเครื่องจักรทุกชนิด: สิ่งใดก็ตามที่สามารถ "คำนวณ" ได้ ก็สามารถคำนวณได้โดยเครื่องจักรทัวริงบางเครื่อง)

เครื่องจักรทัวริงเทียบเท่ากับ เครื่องจักรแบบพุชดาวน์ออโตมาตา (PDA) แบบสแต็กเดี่ยวที่มีความยืดหยุ่นและกระชับมากขึ้นโดยการผ่อนคลาย ข้อกำหนด การเข้าหลังออกก่อน (LIFO) ของสแต็ก นอกจากนี้ เครื่องจักรทัวริงยังเทียบเท่ากับ PDA แบบสองสแต็กที่มีความหมาย LIFO มาตรฐาน โดยใช้สแต็กหนึ่งเพื่อจำลองเทปทางด้านซ้ายของหัวอ่าน และอีกสแต็กหนึ่งสำหรับเทปทางด้านขวา

ในทางตรงกันข้าม แบบจำลองที่เรียบง่ายบางแบบกลับกลายเป็นว่าเทียบเท่ากับเครื่องจักรทัวริงกล่าวคือ มีกำลังการคำนวณเท่ากับแบบจำลองเครื่องจักรทัวริง

แบบจำลองที่เทียบเท่ากันโดยทั่วไป ได้แก่เครื่องจักรทัวริงแบบหลายเทปเครื่องจักรทัวริงแบบหลายแทร็กเครื่องจักรที่มีอินพุตและเอาต์พุต และเครื่องจักรทัวริงแบบไม่กำหนด (NDTM) ซึ่งแตกต่างจาก เครื่องจักรทัวริง แบบกำหนด (DTM) ที่ตารางการกระทำมีรายการอย่างมากที่สุดหนึ่งรายการสำหรับแต่ละการรวมกันของสัญลักษณ์และสถานะ

เครื่องจักรทัวริงแบบอ่านอย่างเดียวและเคลื่อนที่ไปทางขวาเทียบเท่ากับDFA (รวมถึงNFA ด้วย โดยการแปลงโดยใช้ อัลกอริธึม การแปลง NFA เป็น DFA )

เพื่อวัตถุประสงค์เชิงปฏิบัติและการสอน สามารถใช้เครื่องรีจิสเตอร์เทียบเท่าได้เช่น เดียวกับ ภาษาการเขียนโปรแกรมแอสเซมบลี ทั่วไป

คำถามที่เกี่ยวข้องคือ แบบจำลองการคำนวณที่แสดงโดยภาษาโปรแกรมที่เป็นรูปธรรมนั้น เทียบเท่ากับเครื่องจักรทัวริงหรือไม่ แม้ว่าการคำนวณของคอมพิวเตอร์จริงจะขึ้นอยู่กับสถานะจำกัดและไม่สามารถจำลองเครื่องจักรทัวริงได้ แต่ภาษาโปรแกรมเองนั้นไม่จำเป็นต้องมีข้อจำกัดนี้ Kirner และคณะ (2009) ได้แสดงให้เห็นว่า ในบรรดาภาษาโปรแกรมอเนกประสงค์ บางภาษามีความสมบูรณ์แบบทัวริง ในขณะที่บางภาษาไม่เป็นเช่นนั้น ตัวอย่างเช่นANSI Cไม่สมบูรณ์แบบทัวริง เนื่องจากทุกการใช้งานของ ANSI C (การใช้งานที่แตกต่างกันนั้นเป็นไปได้ เนื่องจากมาตรฐานจงใจปล่อยให้พฤติกรรมบางอย่างไม่ถูกกำหนดไว้ด้วยเหตุผลด้านความเข้ากันได้กับระบบเดิม) ล้วนเกี่ยวข้องกับหน่วยความจำที่มีพื้นที่จำกัด เนื่องจากขนาดของชนิดข้อมูลอ้างอิงหน่วยความจำที่เรียกว่าพอยเตอร์สามารถเข้าถึงได้ภายในภาษา อย่างไรก็ตาม ภาษาโปรแกรมอื่นๆ เช่นปาสคาลไม่มีคุณลักษณะนี้ ซึ่งทำให้พวกมันสมบูรณ์แบบทัวริงได้ในทางทฤษฎี โดยหลักการแล้วมันก็คือภาษาที่สมบูรณ์แบบตามทฤษฎีของทัวริง (Turing complete) นั่นเอง เพราะการจัดสรรหน่วยความจำในภาษาโปรแกรมนั้นสามารถล้มเหลวได้ ซึ่งหมายความว่าภาษาโปรแกรมนั้นจะสมบูรณ์แบบตามทฤษฎีของทัวริงได้เมื่อไม่นับรวมการจัดสรรหน่วยความจำที่ล้มเหลว แต่โปรแกรมที่คอมไพล์แล้วและสามารถทำงานบนคอมพิวเตอร์จริงได้นั้นไม่เป็นเช่นนั้น

ในตอนต้นของบทความของเขา (ปี 1936) ทิวริงได้แยกแยะความแตกต่างระหว่าง "เครื่องจักรแบบอัตโนมัติ" ซึ่ง "การเคลื่อนที่...ถูกกำหนดโดยการกำหนดค่าอย่างสมบูรณ์" กับ "เครื่องจักรแบบเลือกได้":

...ซึ่งการเคลื่อนที่ของมันถูกกำหนดเพียงบางส่วนจากโครงสร้าง... เมื่อเครื่องจักรดังกล่าวไปถึงโครงสร้างที่ไม่ชัดเจนอย่างใดอย่างหนึ่ง มันจะไม่สามารถทำงานต่อไปได้จนกว่าผู้ปฏิบัติงานภายนอกจะทำการเลือกโดยพลการ นี่จะเป็นกรณีที่เราใช้เครื่องจักรเพื่อจัดการกับระบบสัจพจน์

Turing (1936) ไม่ได้อธิบายเพิ่มเติม ยกเว้นในเชิงอรรถที่เขาอธิบายวิธีการใช้เครื่องจักรอัตโนมัติเพื่อ "ค้นหาสูตรที่พิสูจน์ได้ทั้งหมดของแคลคูลัส [Hilbert]" แทนที่จะใช้เครื่องจักรแบบเลือก เขา "สมมติว่าตัวเลือกจะอยู่ระหว่างสองความเป็นไปได้ 0 และ 1 เสมอ การพิสูจน์แต่ละครั้งจะถูกกำหนดโดยลำดับของตัวเลือก i ₁ , i ₂ , ..., i _n (i ₁ = 0 หรือ 1, i ₂ = 0 หรือ 1, ..., i _n = 0 หรือ 1) และด้วยเหตุนี้ จำนวน 2 ⁿ + i ₁ 2 ^n-1 + i ₂ 2 ^n-2 + ... +i _nจึงกำหนดการพิสูจน์ได้อย่างสมบูรณ์ เครื่องจักรอัตโนมัติดำเนินการพิสูจน์ 1, พิสูจน์ 2, พิสูจน์ 3, ..." ตามลำดับ^{[ 39 ]}

นี่เป็นเทคนิคที่เครื่องจักรทัวริงแบบกำหนดได้ (เช่น แบบ a-) สามารถใช้เลียนแบบการทำงานของเครื่องจักรทัวริงแบบไม่กำหนดได้ทัวริงได้แก้ปัญหานี้ไว้ในเชิงอรรถและดูเหมือนจะไม่พิจารณาเพิ่มเติมอีกต่อไป

เครื่องออราเคิลหรือเครื่องโอ-แมชชีนคือเครื่องทัวริงที่หยุดการคำนวณไว้ที่สถานะ " โอ " ในขณะที่รอ "การตัดสินใจ" ของ "ออราเคิล" เพื่อให้การคำนวณเสร็จสมบูรณ์ ซึ่งเป็นสิ่งที่ทัวริงไม่ได้ระบุ "นอกเหนือจากการกล่าวว่ามันไม่สามารถเป็นเครื่องจักรได้" (ทัวริง (1939)) ^{[ 40 ]}

ตามที่ Turing เขียนไว้ในThe Undecidable (ตัวเอียง): ^{[ 41 ]}

เป็นไปได้ที่จะประดิษฐ์เครื่องจักรเพียงเครื่องเดียวที่สามารถใช้คำนวณลำดับใดๆ ก็ได้ หากเครื่องจักร U นี้ ได้รับเทปที่มีสตริงของห้าตัวเลขคั่นด้วยเครื่องหมายเซมิโคลอนจากเครื่องจักรคำนวณM เขียนไว้ที่ตอนต้นของเทป เครื่องจักร Uก็จะสามารถคำนวณลำดับเดียวกันกับเครื่องจักร Mได้

แบบจำลองการคำนวณที่ทิวริงเรียกว่า "เครื่องจักรสากล" ของเขา— เรียกสั้นๆ ว่า " U "—ได้รับการพิจารณาโดยบางคน ^{[ 42 ]}ว่าเป็นความก้าวหน้าทางทฤษฎีพื้นฐานที่นำไปสู่แนวคิดของคอมพิวเตอร์โปรแกรมที่จัดเก็บไว้

บทความของทิวริง...โดยเนื้อหาหลักแล้วคือการประดิษฐ์คอมพิวเตอร์สมัยใหม่และเทคนิคการเขียนโปรแกรมบางส่วนที่เกี่ยวข้องกับมัน

ในแง่ของความซับซ้อนในการคำนวณเครื่องทัวริงสากลแบบหลายเทปจะต้องช้าลงเพียง ปัจจัย ลอการิทึมเมื่อเทียบกับเครื่องที่จำลอง ผลลัพธ์นี้ได้รับในปี 1966 โดย FC Hennie และRE Stearns ^{[ 44 ] [ 45 ]}

เครื่องจักรทัวริงมีประสิทธิภาพมากกว่าเครื่องจักรอัตโนมัติชนิดอื่นๆ เช่นเครื่องจักรสถานะจำกัดและเครื่องจักรอัตโนมัติแบบพุชดาวน์ตามทฤษฎีบทของเชิร์ช-ทัวริง เครื่องจักรทัวริงมีประสิทธิภาพเทียบเท่ากับเครื่องจักรจริง และสามารถดำเนินการใดๆ ก็ได้ที่โปรแกรมจริงสามารถทำได้ สิ่งที่ถูกละเลยในข้อความนี้คือ เนื่องจากเครื่องจักรจริงมีสถานะได้ เพียงจำนวนจำกัด เท่านั้น มันจึงเป็นเพียงเครื่องจักรสถานะจำกัด ในขณะที่เครื่องจักรทัวริงมีพื้นที่จัดเก็บข้อมูลสำหรับการคำนวณอย่างไม่จำกัด

มีหลายวิธีที่จะอธิบายว่าเหตุใดเครื่องจักรทัวริงจึงเป็นแบบจำลองที่มีประโยชน์ของคอมพิวเตอร์จริง:

• สิ่งใดก็ตามที่คอมพิวเตอร์จริงสามารถคำนวณได้ เครื่องจักรทัวริงก็สามารถคำนวณได้เช่นกัน ตัวอย่างเช่น: "เครื่องจักรทัวริงสามารถจำลองซับรูทีนทุกประเภทที่พบในภาษาโปรแกรม รวมถึงขั้นตอนแบบเรียกซ้ำและกลไกการส่งผ่านพารามิเตอร์ที่รู้จักทั้งหมด" (Hopcroft and Ullman หน้า 157) FSA ที่มีขนาดใหญ่พอสามารถจำลองคอมพิวเตอร์จริงใดๆ ก็ได้ โดยไม่คำนึงถึงอินพุต/เอาต์พุต ดังนั้น ข้อความเกี่ยวกับข้อจำกัดของเครื่องจักรทัวริงจึงใช้ได้กับคอมพิวเตอร์จริงด้วย
• ความแตกต่างอยู่ที่ความสามารถของเครื่องจักรทัวริงในการประมวลผลข้อมูลจำนวนมหาศาลได้อย่างไม่จำกัด แต่หากมีเวลาจำกัด เครื่องจักรทัวริง (เช่นเดียวกับเครื่องจักรจริง) ก็สามารถประมวลผลข้อมูลได้เพียงจำนวนจำกัดเท่านั้น
• เช่นเดียวกับเครื่องจักรทัวริง เครื่องจักรจริงสามารถขยายพื้นที่จัดเก็บข้อมูลได้ตามต้องการ โดยการซื้อดิสก์หรือสื่อจัดเก็บข้อมูลอื่นๆ เพิ่มเติม
• คำอธิบายโปรแกรมเครื่องจักรจริงโดยใช้แบบจำลองนามธรรมที่เรียบง่ายกว่า มักจะซับซ้อนกว่าคำอธิบายที่ใช้เครื่องจักรทัวริงมาก ตัวอย่างเช่น เครื่องจักรทัวริงที่อธิบายอัลกอริทึมอาจมีสถานะเพียงไม่กี่ร้อยสถานะ ในขณะที่ออโตมาตาจำกัดเชิงกำหนด (DFA) ที่เทียบเท่ากันบนเครื่องจักรจริงที่กำหนด อาจมีสถานะเป็นล้านล้านล้าน ซึ่งทำให้การวิเคราะห์การแสดงผลแบบ DFA เป็นไปไม่ได้ในทางปฏิบัติ
• เครื่องจักรทัวริงอธิบายอัลกอริทึมโดยไม่ขึ้นอยู่กับปริมาณหน่วยความจำที่ใช้ เครื่องจักรในปัจจุบันมีขีดจำกัดของหน่วยความจำ แต่ขีดจำกัดนี้สามารถเพิ่มขึ้นได้ตามอำเภอใจเมื่อเวลาผ่านไป เครื่องจักรทัวริงช่วยให้เราสามารถกล่าวถึงอัลกอริทึมซึ่ง (ในทางทฤษฎี) จะคงอยู่ตลอดไป โดยไม่ขึ้นอยู่กับความก้าวหน้าของสถาปัตยกรรมเครื่องคำนวณแบบดั้งเดิม
• อัลกอริทึมที่ทำงานบนเครื่องจักรนามธรรมที่เทียบเท่ากับเครื่องจักรทัวริง สามารถเข้าถึงชนิดข้อมูลที่มีความแม่นยำสูงได้ตามต้องการ และไม่จำเป็นต้องรับมือกับสภาวะที่ไม่คาดคิด (รวมถึงแต่ไม่จำกัดเพียง การหน่วยความจำหมด )

ข้อจำกัดของเครื่องจักรทัวริงคือมันไม่สามารถจำลองจุดแข็งของการจัดเรียงแบบใดแบบหนึ่งได้ดี ตัวอย่างเช่น คอมพิวเตอร์แบบเก็บโปรแกรมสมัยใหม่นั้นแท้จริงแล้วเป็นตัวอย่างของเครื่องจักรนามธรรม รูปแบบเฉพาะ ที่เรียกว่าเครื่องจักรแบบเก็บโปรแกรมเข้าถึงแบบสุ่มหรือแบบจำลองเครื่องจักร RASP เช่นเดียวกับเครื่องจักรทัวริงสากล RASP จะเก็บ "โปรแกรม" ไว้ใน "หน่วยความจำ" ภายนอก "คำสั่ง" ของเครื่องจักรสถานะจำกัด แต่ต่างจากเครื่องจักรทัวริงสากลตรงที่ RASP มี "รีจิสเตอร์" ที่สามารถแยกแยะได้ มีหมายเลข แต่ไม่จำกัดจำนวนจำนวนอนันต์ ซึ่งเป็น "เซลล์" หน่วยความจำที่สามารถบรรจุจำนวนเต็มใดๆ ก็ได้ (ดู Elgot และ Robinson (1964), Hartmanis (1971) และโดยเฉพาะอย่างยิ่ง Cook-Rechow (1973); อ้างอิงที่เครื่องจักรเข้าถึงแบบสุ่ม ) เครื่องจักรสถานะจำกัดของ RASP มีความสามารถในการกำหนดแอดเดรสทางอ้อม (เช่น เนื้อหาของรีจิสเตอร์หนึ่งสามารถใช้เป็นแอดเดรสเพื่อระบุรีจิสเตอร์อื่นได้) ดังนั้น "โปรแกรม" ของ RASP จึงสามารถเข้าถึงรีจิสเตอร์ใดก็ได้ในลำดับรีจิสเตอร์ ผลลัพธ์ของความแตกต่างนี้คือ มีการปรับปรุงประสิทธิภาพการคำนวณที่สามารถทำได้โดยอาศัยดัชนีหน่วยความจำ ซึ่งเป็นไปไม่ได้ในเครื่องทัวริงทั่วไป ดังนั้น เมื่อใช้เครื่องทัวริงเป็นพื้นฐานในการกำหนดขอบเขตเวลาการทำงาน อาจมีการพิสูจน์ "ขอบเขตล่างที่ผิดพลาด" เกี่ยวกับเวลาการทำงานของอัลกอริทึมบางอย่าง (เนื่องจากสมมติฐานที่ทำให้ง่ายขึ้นอย่างผิดพลาดของเครื่องทัวริง) ตัวอย่างเช่นการค้นหาแบบไบนารี ซึ่งเป็น อัลกอริทึมที่แสดงให้เห็นว่าทำงานได้เร็วกว่าเมื่อใช้แบบจำลองการคำนวณ RASP แทนที่จะใช้แบบจำลองเครื่องทัวริง

ในยุคแรกเริ่มของการคำนวณ การใช้งานคอมพิวเตอร์มักจำกัดอยู่เพียงการประมวลผลแบบกลุ่ม (batch processing)กล่าวคือ งานที่ไม่ต้องมีการโต้ตอบกัน โดยแต่ละงานจะสร้างข้อมูลเอาต์พุตจากข้อมูลอินพุตที่กำหนดให้ ทฤษฎีความสามารถในการคำนวณ (Computability theory) ซึ่งศึกษาความสามารถในการคำนวณของฟังก์ชันจากอินพุตไปยังเอาต์พุต และเป็นที่มาของการคิดค้นเครื่องจักรทัวริง (Turing machine) สะท้อนให้เห็นถึงการปฏิบัติเช่นนี้

นับตั้งแต่ทศวรรษ 1970 การใช้งานคอมพิวเตอร์แบบโต้ตอบได้ กลายเป็นเรื่องปกติมากขึ้น ในทางทฤษฎีแล้ว เป็นไปได้ที่จะจำลองสิ่งนี้โดยให้ตัวแทนภายนอกอ่านจากเทปและเขียนลงในเทปพร้อมๆ กับเครื่องจักรทัวริง แต่สิ่งนี้แทบจะไม่ตรงกับวิธีการโต้ตอบที่เกิดขึ้นจริง ดังนั้น เมื่ออธิบายถึงการโต้ตอบ จึงมักนิยมใช้ทาง เลือกอื่นๆ เช่น ออโตมาตาอินพุต/เอาต์พุต มากกว่า

แบบจำลองการคำนวณทางเลขคณิตแตกต่างจากแบบจำลองของทัวริงในสองประเด็น: ^{[ 46 ]}

• ในแบบจำลองทางเลขคณิต จำนวนจริงทุกจำนวนต้องการเซลล์หน่วยความจำเพียงเซลล์เดียว ในขณะที่ในแบบจำลองของทัวริง ขนาดพื้นที่จัดเก็บของจำนวนจริงจะขึ้นอยู่กับจำนวนบิตที่จำเป็นในการแสดงจำนวนนั้น
• ในแบบจำลองเลขคณิต การดำเนินการทางคณิตศาสตร์พื้นฐานทุกอย่างบนจำนวนจริง (การบวก การลบ การคูณ และการหาร) สามารถทำได้ในขั้นตอนเดียว ในขณะที่ในแบบจำลองทัวริง เวลาในการทำงานของการดำเนินการทางคณิตศาสตร์แต่ละครั้งขึ้นอยู่กับความยาวของตัวดำเนินการ

อัลกอริทึมบางตัวทำงานในเวลาพหุนามในแบบจำลองหนึ่ง แต่ไม่ใช่ในอีกแบบจำลองหนึ่ง ตัวอย่างเช่น:

• อัลกอริทึมยุคลิดทำงานในเวลาพหุนามในแบบจำลองทัวริง แต่ไม่ใช่ในแบบจำลองเลขคณิต
• อัลกอริทึมที่อ่าน ตัวเลข n ตัว แล้วคำนวณโดยการยกกำลังสองซ้ำๆนั้น ทำงานในเวลาพหุนามในแบบจำลองเลขคณิต แต่ไม่ใช่ในแบบจำลองทัวริง ทั้งนี้เพราะจำนวนบิตที่จำเป็นในการแสดงผลลัพธ์นั้นเป็นแบบเลขชี้กำลังตามขนาดของข้อมูลนำเข้า${\displaystyle 2^{2^{n}}}$

อย่างไรก็ตาม หากอัลกอริทึมทำงานได้ในเวลาพหุนามในแบบจำลองทางคณิตศาสตร์ และยิ่งไปกว่านั้น ความยาวไบนารีของตัวเลขทั้งหมดที่เกี่ยวข้องเป็นพหุนามของความยาวของข้อมูลป้อนเข้า อัลกอริทึมนั้นก็จะทำงานได้ในเวลาพหุนามในแบบจำลองทัวริงเสมอ อัลกอริทึมดังกล่าวเรียกว่าทำงานได้ในเวลาพหุนามอย่างเข้มข้น

โรบิน แกนดี (1919–1995) ศิษย์ของอลัน ทัวริง (1912–1954) และเพื่อนสนิทตลอดชีวิตของเขา ได้สืบย้อนที่มาของแนวคิดเรื่อง "เครื่องคำนวณ" ไปถึงชาร์ลส์ แบ็บเบจ (ประมาณปี 1834) และเสนอ "ทฤษฎีบทของแบ็บเบจ" ขึ้นมา:

นั่นหมายความว่าขณะนี้กระบวนการพัฒนาและการดำเนินงานด้านการวิเคราะห์ทั้งหมดสามารถดำเนินการได้ด้วยเครื่องจักรแล้ว

การวิเคราะห์ เครื่องจักรเชิงวิเคราะห์ของแบ็บเบจโดยแคนดี้อธิบายถึงการดำเนินการห้าประการดังต่อไปนี้ (ดูหน้า 52–53):

1. ฟังก์ชันทางคณิตศาสตร์ +, −, × โดยที่ − แสดงถึงการลบ "ที่ถูกต้อง": x − y = 0 ถ้าy ≥ x
2. ลำดับของการดำเนินการใดๆ ก็ถือเป็นการดำเนินการเช่นกัน
3. การทำซ้ำการดำเนินการ (การทำซ้ำการดำเนินการ P จำนวน n ครั้ง)
4. การวนซ้ำแบบมีเงื่อนไข (ทำซ้ำการดำเนินการ P จำนวน n ครั้ง โดยมีเงื่อนไขว่าการทดสอบ T ต้อง "สำเร็จ")
5. การโอนย้ายแบบมีเงื่อนไข (เช่น " goto " แบบมีเงื่อนไข)

Gandy ระบุว่า "ฟังก์ชันที่สามารถคำนวณได้โดย (1), (2) และ (4) นั้นเป็นฟังก์ชันที่สามารถคำนวณได้ด้วย Turing อย่างแม่นยำ " ^{[ 48 ]}เขาอ้างถึงข้อเสนออื่นๆ สำหรับ "เครื่องคำนวณสากล" รวมถึงข้อเสนอของPercy Ludgate (1909), Leonardo Torres Quevedo (1914), ^{[ 49 ] [ 50 ]} Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937) อย่างไรก็ตาม:

...จุดเน้นอยู่ที่การเขียนโปรแกรมลำดับการดำเนินการทางคณิตศาสตร์ที่ตายตัวและทำซ้ำได้ ความสำคัญพื้นฐานของการวนซ้ำแบบมีเงื่อนไขและการถ่ายโอนแบบมีเงื่อนไขสำหรับทฤษฎีทั่วไปของเครื่องคำนวณนั้นไม่ได้รับการยอมรับ...

สำหรับปัญหาของฮิลเบิร์ตที่นักคณิตศาสตร์ชื่อดังเดวิด ฮิลเบิร์ต ตั้งขึ้น ในปี ค.ศ. 1900 นั้น แง่มุมหนึ่งของปัญหาข้อที่ 10ได้ถูกกล่าวถึงมาเกือบ 30 ปีก่อนที่จะมีการกำหนดกรอบอย่างแม่นยำ โดยสูตรดั้งเดิมของฮิลเบิร์ตสำหรับปัญหาข้อที่ 10 มีดังนี้:

10. การพิจารณาความสามารถในการหาคำตอบของสมการไดโอแฟนไทน์กำหนดให้สมการไดโอแฟนไทน์ที่มีตัวแปรที่ไม่ทราบค่าจำนวนใดๆ และมีสัมประสิทธิ์เป็นจำนวนเต็มตรรกยะ: ต้องคิดค้นกระบวนการที่สามารถตรวจสอบได้ว่าสมการนั้นสามารถหาคำตอบได้ในจำนวนเต็มตรรกยะหรือไม่ โดยใช้การดำเนินการจำนวนจำกัด ปัญหาการตัดสินใจ (Entscheidungsproblem) [ปัญหาการตัดสินใจสำหรับตรรกะลำดับที่หนึ่ง ] จะได้รับการแก้ไขเมื่อเรารู้ขั้นตอนที่ช่วยให้สามารถตัดสินความถูกต้องหรือความสามารถในการทำให้เป็นจริงของนิพจน์ตรรกะใดๆ ได้ด้วยการดำเนินการจำนวนจำกัด ... ปัญหาการตัดสินใจ (Entscheidungsproblem)ถือเป็นปัญหาหลักของตรรกะทางคณิตศาสตร์

ในปี ค.ศ. 1922 แนวคิดเรื่อง" ปัญหาการตัดสินใจ " (Entscheidungsproblem) ได้พัฒนาขึ้นบ้างแล้ว และH. Behmannได้กล่าวว่า

...รูปแบบทั่วไปที่สุดของปัญหาการตัดสินใจมีดังนี้:

จำเป็นต้องมีสูตรสำเร็จที่ใช้ได้ทั่วไปและชัดเจน ซึ่งจะช่วยให้สามารถตัดสินความจริงหรือความเท็จของข้อความเชิงตรรกะที่กำหนดให้ได้ในจำนวนขั้นตอนที่จำกัด...

เบห์มันน์กล่าวว่า ... ปัญหาทั่วไปนั้นเทียบเท่ากับปัญหาในการตัดสินใจว่าข้อเสนอทางคณิตศาสตร์ข้อใดเป็นจริง

หากสามารถแก้ปัญหา Entscheidungsproblem ได้สำเร็จ ก็จะทำให้มี "ขั้นตอนในการแก้ปัญหาทางคณิตศาสตร์หลายๆ ข้อ (หรืออาจจะทั้งหมด)"

ในการประชุมนานาชาติของนักคณิตศาสตร์ในปี 1928 ฮิลเบิร์ต "ได้ตั้งคำถามอย่างเจาะจงมาก ประการแรก คณิตศาสตร์สมบูรณ์ หรือ ไม่ ... ประการที่สอง คณิตศาสตร์สอดคล้องกันหรือไม่ ... และประการที่สาม คณิตศาสตร์สามารถตัดสินได้หรือไม่" ^{[ 55 ] [ 56 ]}คำถามสองข้อแรกได้รับคำตอบในปี 1930 โดยเคิร์ต เกอเดลในการประชุมเดียวกันกับที่ฮิลเบิร์ตกล่าวสุนทรพจน์อำลา (ซึ่งทำให้ฮิลเบิร์ตไม่พอใจอย่างมาก) ส่วนคำถามข้อที่สาม—ปัญหาการตัดสินใจ —ต้องรอจนถึงกลางทศวรรษ 1930

ปัญหาคือคำตอบนั้นจำเป็นต้องมีคำจำกัดความที่แม่นยำของ "ข้อกำหนดทั่วไปที่แน่นอนที่ใช้ได้" ก่อน ซึ่งศาสตราจารย์Alonzo Church แห่งมหาวิทยาลัยพรินซ์ตัน จะเรียกในภายหลังว่า " ความสามารถในการคำนวณที่มีประสิทธิภาพ " และในปี 1928 ยังไม่มีคำจำกัดความดังกล่าว แต่ในช่วง 6-7 ปีต่อมาEmil Postได้พัฒนาคำจำกัดความของคนงานที่เคลื่อนที่จากห้องหนึ่งไปยังอีกห้องหนึ่งเพื่อเขียนและลบเครื่องหมายตามรายการคำสั่ง^{[ 57 ]}เช่นเดียวกับ Church และนักศึกษาสองคนของเขาStephen KleeneและJB Rosserโดยใช้แคลคูลัสแลมบ์ดาของ Church และทฤษฎีการเรียกซ้ำ ของ Gödel (1934) บทความของ Church (ตีพิมพ์เมื่อวันที่ 15 เมษายน 1936) แสดงให้เห็นว่าปัญหาEntscheidungsproblemนั้น "ไม่สามารถตัดสินได้" ^{[ 58 ]}และเอาชนะ Turing ไปได้เกือบหนึ่งปี (บทความของ Turing ส่งเมื่อวันที่ 28 พฤษภาคม 1936 ตีพิมพ์ในเดือนมกราคม 1937) ในระหว่างนั้น เอมิล โพสต์ได้ส่งบทความสั้นๆ ในช่วงฤดูใบไม้ร่วงปี 1936 ดังนั้นอย่างน้อยที่สุด ทิวริงจึงได้เปรียบโพสต์ ในขณะที่เชิร์ชทำหน้าที่ตรวจสอบบทความของทิวริง ทิวริงก็มีเวลาศึกษาบทความของเชิร์ชและเพิ่มเติมภาคผนวกซึ่งเขาได้ร่างบทพิสูจน์ว่าแคลคูลัสแลมบ์ดาของเชิร์ชและเครื่องจักรของเขาสามารถคำนวณฟังก์ชันเดียวกันได้

แต่สิ่งที่เชิร์ชทำนั้นค่อนข้างแตกต่างออกไป และในแง่หนึ่งก็อ่อนแอกว่า ... โครงสร้างของทัวริงนั้นตรงไปตรงมามากกว่า และให้เหตุผลจากหลักการพื้นฐาน ซึ่งช่วยอุดช่องว่างในการพิสูจน์ของเชิร์ชได้

โพสต์ได้เสนอเพียงนิยามของความสามารถในการคำนวณและวิพากษ์วิจารณ์ "นิยาม" ของเชิร์ช แต่ไม่ได้พิสูจน์อะไรเลย

ในฤดูใบไม้ผลิปี 1935 ทิวริงในฐานะนักศึกษาปริญญาโทหนุ่มที่คิงส์คอลเลจ เคมบริดจ์ได้รับความท้าทาย เขาได้รับแรงบันดาลใจจากการบรรยายของนักตรรกศาสตร์เอ็มเอชเอ นิวแมน "และได้เรียนรู้จากงานของเกอเดลและปัญหาการตัดสินใจ... นิวแมนใช้คำว่า 'เชิงกล'... ในบทความไว้อาลัยทิวริงในปี 1955 นิวแมนเขียนว่า:

เมื่อถูกถามว่า "กระบวนการ 'เชิงกล' คืออะไร" ทิวริงตอบอย่างมีเอกลักษณ์ว่า "สิ่งที่เครื่องจักรสามารถทำได้" และเขาก็เริ่มต้นภารกิจที่น่าสนใจอย่างยิ่งในการวิเคราะห์แนวคิดทั่วไปของเครื่องคำนวณ

แกนดี้กล่าวว่า:

ผมคาดเดา แต่ไม่แน่ใจนัก ว่าทัวริง ตั้งแต่เริ่มงานของเขา มีเป้าหมายที่จะพิสูจน์ว่าปัญหาการตัดสินใจ (Entscheidungsproblem) นั้นไม่สามารถตัดสินได้ เขาบอกผมว่า "แนวคิดหลัก" ของบทความนั้นเกิดขึ้นกับเขาขณะที่เขานอนพักผ่อนอยู่ในทุ่งหญ้าแกรนท์เชสเตอร์ในฤดูร้อนปี 1935 "แนวคิดหลัก" นั้นอาจจะเป็นการวิเคราะห์การคำนวณของเขา หรือการตระหนักรู้ว่ามีเครื่องจักรสากลอยู่ และด้วยเหตุนี้จึงสามารถ ใช้ ข้อโต้แย้งเชิงทแยงมุมเพื่อพิสูจน์ว่าปัญหานั้นไม่สามารถแก้ได้

แม้ว่าแคนดี้จะเชื่อว่าคำกล่าวของนิวแมนข้างต้นนั้น "ทำให้เข้าใจผิด" แต่ความคิดเห็นนี้ก็ไม่ได้เป็นที่ยอมรับของทุกคน ทิวริงมีความสนใจในเครื่องจักรมาตลอดชีวิต: "อลันเคยฝันอยากประดิษฐ์เครื่องพิมพ์ดีดตั้งแต่ยังเด็ก; [แม่ของเขา] คุณนายทิวริงมีเครื่องพิมพ์ดีด; และเขาน่าจะเริ่มต้นด้วยการถามตัวเองว่าการเรียกเครื่องพิมพ์ดีดว่า 'เชิงกล' นั้นหมายความว่าอย่างไร" (ฮอดจ์ส หน้า 96) ขณะศึกษาปริญญาเอกที่พรินซ์ตัน ทิวริงได้สร้างตัวคูณตรรกะบูลีน (ดูด้านล่าง) วิทยานิพนธ์ปริญญาเอกของเขาชื่อ " ระบบตรรกะบนพื้นฐานของลำดับ " มีคำจำกัดความของ "ฟังก์ชันที่คำนวณได้" ดังต่อไปนี้:

ดังที่กล่าวไว้ข้างต้นว่า 'ฟังก์ชันจะคำนวณได้อย่างมีประสิทธิภาพก็ต่อเมื่อสามารถหาค่าของฟังก์ชันนั้นได้ด้วยกระบวนการเชิงกลล้วนๆ' เราอาจตีความคำกล่าวนี้ตามตัวอักษร โดยเข้าใจว่ากระบวนการเชิงกลล้วนๆ คือกระบวนการที่สามารถดำเนินการโดยเครื่องจักรได้ เป็นไปได้ที่จะอธิบายโครงสร้างของเครื่องจักรเหล่านี้ในรูปแบบทางคณิตศาสตร์มาตรฐานบางอย่าง การพัฒนาแนวคิดเหล่านี้ทำให้เกิดนิยามของฟังก์ชันที่คำนวณได้ของผู้เขียน และการระบุความสามารถในการคำนวณได้กับความสามารถในการคำนวณได้อย่างมีประสิทธิภาพ การพิสูจน์ว่านิยามทั้งสามนี้ (นิยามที่ 3 คือแคลคูลัส λ) เทียบเท่ากันนั้นไม่ใช่เรื่องยาก แต่ค่อนข้างต้องใช้ความพยายาม

อลัน ทิวริง ประดิษฐ์ "เครื่องจักรอัตโนมัติ" (เครื่องจักรอัตโนมัติ) ในปี พ.ศ. 2479 ^{[ 7 ]}ทิวริงส่งบทความของเขาเมื่อวันที่ 31 พฤษภาคม พ.ศ. 2479 ให้กับสมาคมคณิตศาสตร์แห่งลอนดอนเพื่อตีพิมพ์ในวารสาร^{[ 62 ]}แต่บทความดังกล่าวได้รับการตีพิมพ์ในช่วงต้นปี พ.ศ. 2480 และมีฉบับพิมพ์ซ้ำในเดือนกุมภาพันธ์ พ.ศ. 2470 ^{[ 63 ]}อลอนโซ เชิร์ชที่ปรึกษาปริญญาเอกของทิวริง เป็นผู้บัญญัติศัพท์ "เครื่องจักรทิวริง" ในบทวิจารณ์ในภายหลัง^{[ 13 ]}ด้วยแบบจำลองนี้ ทิวริงสามารถตอบคำถามสองข้อในเชิงลบได้:

• มีเครื่องจักรใดบ้างที่สามารถตรวจสอบได้ว่าเครื่องจักรใดๆ บนเทปของมัน "ทำงานผิดปกติ" (เช่น ค้าง หรือไม่สามารถดำเนินการคำนวณต่อได้)?
• มีเครื่องจักรที่สามารถระบุได้หรือไม่ว่าเครื่องจักรใดๆ บนเทปของมันเคยพิมพ์สัญลักษณ์ที่กำหนดหรือไม่? ^{[ 14 ] [ 15 ]}

ดังนั้นด้วยการให้คำอธิบายทางคณิตศาสตร์ของอุปกรณ์ที่เรียบง่ายมากซึ่งสามารถคำนวณได้ตามอำเภอใจ เขาจึงสามารถพิสูจน์คุณสมบัติของการคำนวณโดยทั่วไปได้ และโดยเฉพาะอย่างยิ่งความไม่สามารถคำนวณได้ของ ปัญหา การตัดสินใจ (Entscheidungsproblem) ^{[ 16 ]}

เมื่อทิวริงกลับไปยังสหราชอาณาจักร ในที่สุดเขาก็มีส่วนรับผิดชอบในการถอดรหัสลับของเยอรมันที่สร้างขึ้นโดยเครื่องเข้ารหัสที่เรียกว่า "เอนิกมา" เขายังมีส่วนร่วมในการออกแบบ ACE ( Automatic Computing Engine ) ด้วย "[ข้อเสนอ ACE ของทิวริง] นั้นมีประสิทธิภาพในตัวเอง และรากฐานของมันไม่ได้มาจากEDVAC [โครงการริเริ่มของสหรัฐอเมริกา] แต่มาจากเครื่องจักรแบบสากลของเขาเอง" (ฮอดจ์ส หน้า 318) การถกเถียงยังคงดำเนินต่อไปเกี่ยวกับที่มาและธรรมชาติของสิ่งที่คลีน (1952) เรียกว่าวิทยานิพนธ์ของทิวริงแต่สิ่งที่ทิวริงพิสูจน์ได้ด้วยแบบจำลองเครื่องจักรคำนวณของเขานั้นปรากฏอยู่ในบทความของเขาเรื่อง " เกี่ยวกับจำนวนที่คำนวณได้ พร้อมการประยุกต์ใช้กับปัญหาการตัดสินใจ " (1937):

[ว่า] ปัญหาการตัดสินใจของฮิลเบิร์ต (Hilbert Entscheidungsproblem) ไม่มีคำตอบ ... ดังนั้น ข้าพเจ้าจึงเสนอให้แสดงว่าไม่มีกระบวนการทั่วไปใดที่จะใช้ในการพิจารณาว่าสูตร U ที่กำหนดในแคลคูลัสเชิงฟังก์ชัน K นั้นพิสูจน์ได้หรือไม่ กล่าวคือ ไม่มีเครื่องจักรใดที่เมื่อป้อนสูตร U ใด ๆ เหล่านี้เข้าไปแล้ว จะสามารถบอกได้ในที่สุดว่า U นั้นพิสูจน์ได้หรือไม่

ตัวอย่างของทิวริง (การพิสูจน์ข้อที่สองของเขา): หากเราถามถึงขั้นตอนทั่วไปที่จะบอกเราได้ว่า "เครื่องนี้เคยพิมพ์เลข 0 หรือไม่" คำถามนั้น "ไม่สามารถตัดสินได้"

ในปี 1937 ขณะที่กำลังทำวิทยานิพนธ์ปริญญาเอกอยู่ที่มหาวิทยาลัยพรินซ์ตัน ทิวริงได้สร้างตัวคูณดิจิทัล (ตรรกะบูลีน) ขึ้นมาเอง โดยสร้างรีเลย์ ไฟฟ้าเชิงกลขึ้นเอง (ฮอดจ์ส หน้า 138) "ภารกิจของอลันคือการนำการออกแบบเชิงตรรกะของเครื่องจักรทิวริงมาใส่ไว้ในเครือข่ายของสวิตช์ที่ทำงานด้วยรีเลย์..." (ฮอดจ์ส หน้า 138) แม้ว่าทิวริงอาจจะแค่สงสัยและทดลองในตอนแรก แต่ก็มีงานวิจัยที่จริงจังในทิศทางเดียวกันเกิดขึ้นในเยอรมนีโดยคอนราด ซูเซ (1938) และในสหรัฐอเมริกาโดยโฮเวิร์ด ไอเคนและจอร์จ สติบิตซ์ (1937) ผลงานของพวกเขาถูกนำไปใช้โดยทั้งกองทัพฝ่ายอักษะและฝ่ายสัมพันธมิตรในสงครามโลกครั้งที่สอง (ดู ฮอดจ์ส หน้า 298–299) ในช่วงต้นถึงกลางทศวรรษ 1950 เหา หวังและมาร์วิน มินสกีได้ลดเครื่องจักรทิวริงให้เป็นรูปแบบที่ง่ายกว่า (ซึ่งเป็นต้นแบบของเครื่องจักรโพสต์ทิวริงของมาร์ติน เดวิส ) ในขณะเดียวกัน นักวิจัยชาวยุโรปกำลังลดทอน คอมพิวเตอร์อิเล็กทรอนิกส์รุ่นใหม่ให้เหลือเพียงวัตถุเชิงทฤษฎีที่คล้ายคอมพิวเตอร์ ซึ่งเทียบเท่ากับสิ่งที่ปัจจุบันเรียกว่า "เครื่องจักรทัวริง" ในช่วงปลายทศวรรษ 1950 และต้นทศวรรษ 1960 การพัฒนาที่เกิดขึ้นพร้อมกันโดยบังเอิญของ Melzak และ Lambek (1961), Minsky (1961) และ Shepherdson และ Sturgis (1961) ได้ต่อยอดงานของชาวยุโรปและลดทอนเครื่องจักรทัวริงให้เหลือเพียงแบบจำลองนามธรรมที่เป็นมิตรต่อคอมพิวเตอร์มากขึ้น เรียกว่าเครื่องจักรนับ (counter machine ) Elgot และ Robinson (1964), Hartmanis (1971), Cook และ Reckhow (1973) ได้ต่อยอดงานนี้ไปอีกขั้นด้วย แบบจำลอง เครื่องจักรลงทะเบียน (register machine ) และเครื่องจักรเข้าถึงแบบสุ่ม (random-access machine)—แต่โดยพื้นฐานแล้วทั้งหมดก็คือเครื่องจักรทัวริงแบบหลายเทปที่มีชุดคำสั่งคล้ายเลขคณิต

ในปัจจุบัน เครื่องนับ เครื่องลงทะเบียน และเครื่องเข้าถึงแบบสุ่ม รวมถึงเครื่องทัวริงซึ่งเป็นต้นกำเนิดของเครื่องจักรเหล่านี้ ยังคงเป็นแบบจำลองที่นักทฤษฎีเลือกใช้ในการศึกษาคำถามต่างๆ ในทฤษฎีการคำนวณโดยเฉพาะอย่างยิ่งทฤษฎีความซับซ้อนของการคำนวณได้ใช้เครื่องทัวริงเป็นแบบจำลอง:

ขึ้นอยู่กับวัตถุที่ต้องการจัดการในการคำนวณ (เช่น ตัวเลขจำนวนเต็มที่ไม่ติดลบ หรือสตริงตัวอักษรและตัวเลข) มีสองแบบจำลองที่ได้รับความนิยมอย่างมากในทฤษฎีความซับซ้อนของเครื่องจักร:

เครื่องทัวริงแบบมัลติเทปออฟไลน์ ... ซึ่งเป็นตัวแทนของแบบจำลองมาตรฐานสำหรับการคำนวณเชิงสตริง และเครื่องเข้าถึงแบบสุ่ม (RAM)ตามที่ Cook และ Reckhow นำเสนอ... ซึ่งจำลองคอมพิวเตอร์แบบ Von Neumann ในอุดมคติ

เฉพาะในด้านการวิเคราะห์อัลกอริทึมเท่านั้นที่บทบาทนี้ถูกแทนที่โดยแบบจำลอง RAM

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับเครื่องจักรทัวริง