ต่อไปนี้เป็นตัวอย่างเพิ่มเติมเพื่อเสริมบทความเรื่องเครื่องจักรทัวริง

ตารางต่อไปนี้คือตัวอย่างแรกสุดของ ทิวริง (ทิวริง 1937):

"1. สามารถสร้างเครื่องจักรเพื่อคำนวณลำดับ 0 1 0 1 0 1..." (0 <blank> 1 <blank> 0...) ^{[ 1 ]}

ในส่วนที่เกี่ยวกับการกระทำที่เครื่องจักรทำจริง ๆ นั้น Turing (1936) ^{[ 2 ]}ระบุไว้ดังนี้:

"ตาราง [ตัวอย่าง] นี้ (และตารางที่ตามมาทั้งหมดในลักษณะเดียวกัน) จะต้องเข้าใจว่าสำหรับการกำหนดค่าที่อธิบายไว้ในสองคอลัมน์แรก การดำเนินการในคอลัมน์ที่สามจะดำเนินการตามลำดับ จากนั้นเครื่องจะเปลี่ยนไปใช้การกำหนดค่า m ในคอลัมน์สุดท้าย" ^{[ 2 ]}

เขาทำให้เรื่องนี้ชัดเจนมากเมื่อเขาลดตารางข้างต้นให้เหลือคำสั่งเดียวที่เรียกว่า "b" ^{[ 3 ]}แต่คำสั่งของเขามี 3 บรรทัด คำสั่ง "b" มีสัญลักษณ์ที่เป็นไปได้ 3 แบบ {ไม่มี, 0, 1} แต่ละความเป็นไปได้จะตามด้วยลำดับของการกระทำจนกว่าเราจะมาถึงคอลัมน์ขวาสุด ซึ่งการกำหนดค่า m สุดท้ายคือ "b":

ดังที่นักวิจารณ์หลายท่าน รวมถึงทิวริง (1937) เองได้สังเกตไว้ (เช่น โพสต์ (1936), โพสต์ (1947), คลีน (1952), หวัง (1954)) คำสั่งของทิวริงไม่ใช่หน่วยย่อย — สามารถลดความซับซ้อนของแบบจำลองลงได้อีกโดยไม่ลดกำลังการคำนวณ ดูเพิ่มเติมได้ที่เครื่องจักรโพสต์-ทิวริง

ตามที่ระบุในบทความเครื่องจักรทัวริงทัวริงเสนอให้แบ่งตารางของเขาออกเป็นอะตอมย่อยเพิ่มเติมโดยอนุญาตให้พิมพ์/ลบเพียงครั้งเดียวตามด้วยการเคลื่อนที่ของเทป L/R/N เพียงครั้งเดียว เขาให้ตัวอย่างตารางเล็ก ๆ แรกที่แปลงแล้วดังนี้: ^{[ 4 ]}

คำกล่าวของทัวริงยังคงบ่งบอกถึงการดำเนินการพื้นฐานห้าอย่าง ที่คำสั่งหนึ่งๆ (การกำหนดค่า m) เครื่องจักรจะดำเนินการดังนี้:

1. สังเกตสัญลักษณ์เทปที่อยู่ใต้หัว
2. โดยอิงตามสัญลักษณ์ที่สังเกตได้ จะนำไปยังลำดับคำสั่งที่เหมาะสมเพื่อใช้งาน
3. พิมพ์สัญลักษณ์ S _jหรือลบ หรือไม่ทำอะไรเลย
4. เลื่อนเทปไปทางซ้าย ขวา หรือไม่เลื่อนเลย
5. ไปสู่การกำหนดค่า m ขั้นสุดท้ายสำหรับสัญลักษณ์นั้น

เนื่องจากการกระทำของเครื่องจักรทัวริงไม่ใช่การกระทำแบบอะตอมิก การจำลองเครื่องจักรจึงต้องแยกชุด 5-tuple แต่ละชุดออกเป็นลำดับของการกระทำที่ง่ายกว่า หนึ่งในความเป็นไปได้ — ซึ่งใช้ในตัวอย่าง "พฤติกรรม" ของเครื่องจักรนี้ต่อไปนี้ — มีดังนี้:

(q _i ) ทดสอบสัญลักษณ์เทปใต้หัว: ถ้าสัญลักษณ์คือ S ₀ให้ไปที่ q _i .01 ถ้าสัญลักษณ์คือ S ₁ให้ไปที่ q _i .11 ถ้าสัญลักษณ์คือ S ₂ให้ไปที่ q _i .21 เป็นต้น

(q _i .01) พิมพ์สัญลักษณ์ S _j 0 หรือลบ หรือไม่ทำอะไรเลย จากนั้นไปที่ q _i .02

(q _i .02) เลื่อนเทปไปทางซ้ายหรือขวา หรือไม่เลื่อนเลย จากนั้นไปที่ qm0

(q _i .11) พิมพ์สัญลักษณ์ S _j 1 หรือลบ หรือไม่ทำอะไรเลย จากนั้นไปที่ q _i .12

(q _i .12) เลื่อนเทปไปทางซ้ายหรือขวา หรือไม่เลื่อนเลย จากนั้นไปที่ qm1

(q _i .21) พิมพ์สัญลักษณ์ S _j 2 หรือลบ หรือไม่ทำอะไรเลย จากนั้นไปที่ q _i .22

(q _i .22) เลื่อนเทปไปทางซ้ายหรือขวา หรือไม่เลื่อนเลย จากนั้นไปที่ qm2

(ฯลฯ — ต้องคำนึงถึงสัญลักษณ์ทั้งหมด)

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

ในตัวอย่างต่อไปนี้เกี่ยวกับการทำงานของเครื่องจักร เราจะสังเกตเห็นลักษณะเฉพาะบางประการของแบบจำลองของทัวริง:

ธรรมเนียมการเขียนตัวเลขเฉพาะในช่องสลับกันนั้นมีประโยชน์มาก ฉันจะใช้ธรรมเนียมนี้เสมอ^{[ 2 ]}

ดังนั้นเมื่อพิมพ์ เขาจึงเว้นช่องสี่เหลี่ยมสลับกันไป ช่องสี่เหลี่ยมที่พิมพ์แล้วเรียกว่าช่อง F ส่วนช่องสี่เหลี่ยมว่างๆ ที่อยู่ระหว่างนั้นอาจใช้เป็น "เครื่องหมาย" และเรียกว่า "ช่อง E" ซึ่งหมายถึง "ลบได้ง่าย" ช่อง F เหล่านั้นก็คือ "ช่องรูปภาพ" ของเขา และจะมีเพียงสัญลักษณ์ 1 หรือ 0 เท่านั้น ซึ่งเขาเรียกว่า "ตัวเลข" (เช่นเดียวกับ "เลขฐานสอง")

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

ภาพนี้แสดง "ขั้นตอนการทำงาน" เดียวกัน โดยรวมขั้นตอนการพิมพ์เทปและการเคลื่อนย้ายต่างๆ ไว้ด้วย:

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

ตัวอย่างเช่น สมมติว่าเทปของเขาไม่ได้ว่างเปล่าตั้งแต่แรก จะเกิดอะไรขึ้น? เครื่องจักรทัวริงจะอ่านค่าที่แตกต่างจากค่าที่ตั้งใจไว้

นี่คือซับรูทีนที่สำคัญมากซึ่งใช้ในรูทีน "คูณ"

เครื่องจักรทัวริงตัวอย่างนี้จัดการกับสตริงของ 0 และ 1 โดยที่ 0 แทนด้วยสัญลักษณ์ว่าง หน้าที่ของมันคือการเพิ่มค่า 1 ซ้ำเป็นสองเท่าในทุกๆ ชุดของ 1 ที่พบในเทป โดยการเขียน 0 คั่นระหว่าง 1 เหล่านั้น ตัวอย่างเช่น เมื่อหัวอ่านอ่าน "111" มันจะเขียน 0 จากนั้นเขียน "111" ผลลัพธ์ที่ได้จะเป็น "1110111"

เพื่อให้บรรลุเป้าหมาย เครื่องจักรทัวริงนี้ต้องการสถานะการทำงานเพียง 5 สถานะ ซึ่งเรียกว่า {s ₁ , s ₂ , s ₃ , s ₄ , s ₅ } แต่ละสถานะจะทำการกระทำ 4 อย่าง:

1. อ่านสัญลักษณ์ใต้หัวข้อ
2. เขียนสัญลักษณ์เอาต์พุตที่รัฐกำหนด
3. เลื่อนเทปไปทางซ้ายหรือขวาตามที่รัฐกำหนด
4. เปลี่ยนไปใช้สถานะถัดไปซึ่งถูกกำหนดโดยสถานะปัจจุบัน

คำสั่งพิมพ์ : พิมพ์สัญลักษณ์ S หรือลบหรือไม่ทำอะไรเลย

การ "รัน" ลำดับการทำงานของเครื่องจักรผ่านการกำหนดค่าเครื่องจักร 16 รูปแบบ (หรือที่เรียกว่าสถานะทัวริง):

พฤติกรรมของเครื่องจักรนี้สามารถอธิบายได้ว่าเป็นลูป: มันเริ่มต้นที่ s ₁แทนที่เลข 1 ตัวแรกด้วยเลข 0 จากนั้นใช้ s ₂เคลื่อนไปทางขวา ข้ามเลข 1 และเลข 0 ตัวแรกที่พบ s ₃จะข้ามลำดับเลข 1 ถัดไป (ในตอนแรกไม่มี) และแทนที่เลข 0 ตัวแรกที่พบด้วยเลข 1 s ₄เคลื่อนกลับไปทางซ้าย ข้ามเลข 1 ไปเรื่อยๆ จนกว่าจะพบเลข 0 แล้วเปลี่ยนไปใช้ s ₅ s ₅จะเคลื่อนไปทางซ้าย ข้ามเลข 1 ไปเรื่อยๆ จนกว่าจะพบเลข 0 ที่เขียนไว้โดย s ₁ใน ตอนแรก

มันจะแทนที่เลข 0 ด้วยเลข 1 เลื่อนไปทางขวาหนึ่งตำแหน่ง แล้วกลับเข้าไปที่เลข₁อีกครั้งเพื่อวนลูปอีกรอบ

กระบวนการนี้ดำเนินต่อไปจนกว่า s ₁จะพบ 0 (ซึ่งเป็น 0 ที่อยู่ตรงกลางระหว่างสตริง 1 สองสตริง) ณ เวลานั้นเครื่องจะหยุดทำงาน

คำอธิบายอีกแบบหนึ่งมองว่าปัญหาอยู่ที่ว่าจะติดตามจำนวน "1" ได้อย่างไร เราไม่สามารถใช้สถานะหนึ่งสถานะสำหรับแต่ละจำนวนที่เป็นไปได้ (เช่น สถานะสำหรับ 0, 1, 2, 3, 4, 5, 6 เป็นต้น) เพราะถ้าเป็นเช่นนั้น เราจะต้องมีสถานะอนันต์เพื่อแทนจำนวนธรรมชาติทั้งหมด และเครื่องสถานะมีจำนวนจำกัดเราจึงต้องติดตามสิ่งนี้โดยใช้เทปในรูปแบบใดรูปแบบหนึ่ง

หลักการทำงานพื้นฐานคือ การคัดลอกเลข "1" แต่ละตัวไปยังอีกด้านหนึ่ง โดยการเคลื่อนที่ไปมา – มันฉลาดพอที่จะจำได้ว่ามันอยู่ส่วนไหนของการเดินทางแล้ว โดยละเอียดแล้ว มันจะส่งต่อเลข "1" แต่ละตัวไปยังอีกด้านหนึ่ง โดยการจดจำเลข "0" ที่อยู่ตรงกลาง และจดจำเลข "0" ที่อีกด้านหนึ่งเพื่อรู้ว่ามันถึงจุดสิ้นสุดแล้ว มันจะกลับมาโดยใช้วิธีเดียวกัน โดยตรวจจับเลข "0" ตรงกลาง และจากนั้นก็ตรวจจับเลข "0" ที่ด้านเดิม เลข "0" ที่ด้านเดิมนี้เป็นกุญแจสำคัญในการไขปริศนาว่ามันติดตามจำนวนเลข "1" ได้อย่างไร

เทคนิคก็คือ ก่อนที่จะทดเลข "1" มันจะทำเครื่องหมายว่าเลขนั้น "ถูกใช้ไปแล้ว" โดยการแทนที่ด้วย "0" เมื่อมันกลับมา มันจะเติม "0" กลับเข้าไปด้วย "1" จากนั้นก็ไปยังเลขถัดไปทำเครื่องหมายด้วย "0" และทำซ้ำวงจร โดยทดเลข "1" นั้นไปเรื่อยๆ ใน แต่ละรอบที่ทวนไปมา เครื่องหมาย "0" จะเคลื่อนเข้าใกล้จุดศูนย์กลางมากขึ้นหนึ่งขั้นนี่คือวิธีที่มันติดตามว่ามันได้ทวนเลข "1" ไปกี่ตัวแล้ว

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

การ "ดำเนินการ" แบบเต็มรูปแบบที่แสดงผลลัพธ์ของการ "เคลื่อนไหว" ระหว่างขั้นตอนต่างๆ

ตารางคำสั่ง Turing ต่อไปนี้ได้มาจาก Peterson: ^{[ 5 ]} "busy beaver สามสถานะจะเขียนเลข 1 จำนวน 6 ตัวก่อนที่จะหยุด" Peterson ขยับหัวอ่าน ในแบบจำลองต่อไปนี้เทปจะเคลื่อนที่ 0 คืออักขระว่าง: เทปเริ่มต้นด้วยเซลล์ทั้งหมดเป็น 0

ภาพวาด "สถานะ" ของ Busy Beaver 3 สถานะแสดงลำดับเหตุการณ์ภายในที่จำเป็นต่อการดำเนินการ "สถานะ" จริงๆ ดังที่กล่าวไว้ข้างต้น Turing (1937) ทำให้ชัดเจนอย่างยิ่งว่านี่คือการตีความที่ถูกต้องของ 5-tuple ที่อธิบายคำสั่ง^{[ 1 ]}สำหรับข้อมูลเพิ่มเติมเกี่ยวกับการแยกย่อย 5-tuple ของ Turing โปรดดูที่เครื่องจักรหลัง Turing :

ตารางต่อไปนี้แสดงผลการทำงานแบบ "ย่อ" — เฉพาะสถานะของทัวริงเท่านั้น:

ลำดับการทำงานทั้งหมดของ Busy Beaver แบบ 3 สถานะ ผลลัพธ์ของสถานะ Turing (สิ่งที่ Turing เรียกว่า "m-configurations" หรือ "machine-configurations") แสดงเป็นสีเทาในคอลัมน์ A และอยู่ใต้คำสั่งของเครื่อง (คอลัมน์ AF-AU) ด้วย: