บทพิสูจน์ของ Turingเป็นบทพิสูจน์ที่Alan Turingนำเสนอเมื่อวันที่ 12 พฤศจิกายน พ.ศ. 2479 และตีพิมพ์ครั้งแรกในปี พ.ศ. 2480 ^{[ 1 ]}ในชื่อ " เกี่ยวกับจำนวนที่คำนวณได้ พร้อมการประยุกต์ใช้กับปัญหาการตัดสินใจ " นับเป็นบทพิสูจน์ที่สอง (หลังจากทฤษฎีบทของ Church ) ของการปฏิเสธปัญหาการตัดสินใจของHilbertกล่าวคือข้อสันนิษฐานที่ว่าคำถามใช่-ไม่ใช่ทางคณิตศาสตร์บางข้อไม่สามารถตอบได้ด้วยการคำนวณ กล่าว ใน เชิงเทคนิคมากขึ้น คือ ปัญหาการตัดสินใจ บางอย่าง " ไม่สามารถตัดสินได้ " ในแง่ที่ว่าไม่มีอัลกอริทึม ใด ที่ให้คำตอบ "ใช่" หรือ "ไม่ใช่" ที่ถูกต้องอย่างแน่นอนสำหรับแต่ละกรณีของปัญหา ในคำพูดของ Turing เอง: "สิ่งที่ฉันจะพิสูจน์นั้นแตกต่างจากผลลัพธ์ที่เป็นที่รู้จักกันดีของGödel ... ตอนนี้ฉันจะแสดงให้เห็นว่าไม่มีวิธีการทั่วไปใดที่บอกได้ว่าสูตรU ที่กำหนด นั้นสามารถพิสูจน์ได้ในK [ Principia Mathematica ] หรือไม่" ^{[ 2 ]}

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

ในการพิสูจน์ว่าปัญหา Entscheidungsproblem ไม่มีคำตอบนั้น ทิวริงได้เริ่มต้นจากการพิสูจน์สองขั้นตอนซึ่งนำไปสู่ข้อพิสูจน์สุดท้ายของเขา ทฤษฎีบทแรกของเขามีความเกี่ยวข้องกับปัญหาการหยุดทำงาน มากที่สุด ส่วนทฤษฎีบทที่สองมีความเกี่ยวข้องกับทฤษฎีบทของไรซ์มากกว่า

หลักฐานแรก : ไม่มี "เครื่องคำนวณ" ใดที่สามารถตัดสินได้ว่า "เครื่องคำนวณ" ใดๆ (ซึ่งแทนด้วยจำนวนเต็ม 1, 2, 3, ...) นั้น "ปราศจากวงกลม" (กล่าวคือ พิมพ์ตัวเลขในรูปแบบไบนารีไปเรื่อยๆ อย่างไม่มีที่สิ้นสุด): "...เราไม่มีกระบวนการทั่วไปในการทำเช่นนี้ในจำนวนขั้นตอนที่จำกัด" (หน้า 132, ibid .) หลักฐานของทัวริง แม้ว่าจะดูเหมือนใช้ "กระบวนการแนวทแยง" แต่ในความเป็นจริงแสดงให้เห็นว่าเครื่องของเขา (เรียกว่า H) ไม่สามารถคำนวณตัวเลขของตัวเองได้เลย ไม่ต้องพูดถึงตัวเลขแนวทแยงทั้งหมด ( ข้อโต้แย้งแนวทแยงของแคนเตอร์ ): "ความผิดพลาดในข้อโต้แย้งอยู่ที่สมมติฐานที่ว่า B [ตัวเลขแนวทแยง] สามารถคำนวณได้" ^{[ 3 ]}หลักฐานนี้ไม่จำเป็นต้องใช้คณิตศาสตร์มากนัก

บทพิสูจน์ที่สอง : บทพิสูจน์นี้อาจเป็นที่คุ้นเคยสำหรับผู้อ่านในชื่อทฤษฎีบทของไรซ์ : "เราสามารถแสดงเพิ่มเติมได้ว่าไม่มีเครื่องจักร E ใดที่เมื่อได้รับ SD ["โปรแกรม"] ของเครื่องจักร M ใดๆ จะสามารถระบุได้ว่า M เคยพิมพ์สัญลักษณ์ที่กำหนด (เช่น 0) หรือไม่ " ^{[ a ]}

บทพิสูจน์ที่สาม : "สำหรับเครื่องคำนวณ M แต่ละเครื่อง เราสร้างสูตร Un(M) และเราแสดงให้เห็นว่า หากมีวิธีการทั่วไปในการพิจารณาว่า Un(M) สามารถพิสูจน์ได้หรือไม่ ก็จะมีวิธีการทั่วไปในการพิจารณาว่า M เคยพิมพ์ 0 หรือไม่" ^{[ 2 ]}

การพิสูจน์ข้อที่สามต้องใช้ตรรกศาสตร์เชิงรูปธรรมเพื่อพิสูจน์บทพิสูจน์ย่อยข้อแรก ตามด้วยการพิสูจน์บทพิสูจน์ย่อยข้อที่สองด้วยถ้อยคำสั้นๆ:

บทตั้งที่ 1: ถ้า S1 [สัญลักษณ์ "0"] ปรากฏบนเทปในรูปแบบสมบูรณ์ของ M แล้ว Un(M) สามารถพิสูจน์ได้^{[ 4 ]} บทตั้งที่ 2: [บทกลับ] ถ้า Un(M) สามารถพิสูจน์ได้ แล้ว S1 [สัญลักษณ์ "0"] ปรากฏบนเทปในรูปแบบสมบูรณ์ของ M ^{[ 5 ]}

ในที่สุด Turing ก็พิสูจน์โดยวิธีหักล้าง ด้วยคำและสัญลักษณ์เพียง 64 คำ ว่า "ปัญหาการตัดสินใจของ Hilbert ไม่มีทางออก" ^{[ 2 ]}

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

คำชี้แจงสำคัญบางประการ:

เครื่องจักร H ของทัวริงกำลังพยายามพิมพ์ตัวเลข 0 และ 1 เรียงกันในแนวทแยงมุม ตัวเลขแนวทแยงนี้เกิดขึ้นเมื่อ H "จำลอง" เครื่องจักรที่ "ประสบความสำเร็จ" แต่ละเครื่องที่กำลังประเมิน และพิมพ์ "ตัวเลข" ตัวที่ R (1 หรือ 0) ของเครื่องจักรที่ "ประสบความสำเร็จ" ตัวที่ R นั้น

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

ทิวริงเริ่มต้นการพิสูจน์ด้วยการยืนยันถึงการมีอยู่ของเครื่อง "การตัดสินใจ/การกำหนด" D เมื่อป้อน SD ใดๆ (สตริงของสัญลักษณ์ A, C, D, L, R, N, เครื่องหมายเซมิโคลอน ";") เครื่องนี้จะกำหนดว่า SD (สตริงสัญลักษณ์) นี้แสดงถึง "เครื่องคำนวณ" ที่เป็น "แบบวงกลม" — และดังนั้นจึง "ไม่น่าพอใจ u" — หรือ "ปราศจากวงกลม" — และดังนั้นจึง "น่าพอใจ s"

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

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

จากนั้น ทิวริงได้อธิบาย (อย่างคร่าวๆ) อัลกอริทึม (วิธีการ) ที่เครื่องจักรที่เขาเรียกว่า H จะต้องปฏิบัติตาม เครื่องจักร H ประกอบด้วยเครื่องจักรตัดสินใจ D อยู่ภายใน (ดังนั้น D จึงเป็น "รูทีนย่อย" ของ H) อัลกอริทึมของเครื่องจักร H ถูกแสดงไว้ในตารางคำสั่งของ H หรืออาจจะอยู่ในคำอธิบายมาตรฐานของ H บนเทปและรวมเข้ากับเครื่องจักรเอนกประสงค์ U ทิวริงไม่ได้ระบุรายละเอียดนี้

ในระหว่างการอธิบายเครื่องจักรเอนกประสงค์ U นั้น ทิวริงได้แสดงให้เห็นว่า SD ของเครื่องจักร (สตริงของตัวอักษรที่คล้ายกับ "โปรแกรม") สามารถแปลงเป็นจำนวนเต็ม (ฐาน 8) และในทางกลับกันได้ จำนวนใดๆ N (ในฐาน 8) สามารถแปลงเป็น SD ได้โดยใช้การแทนที่ดังต่อไปนี้: 1 ด้วย A, 2 ด้วย C, 3 ด้วย D, 4 ด้วย L, 5 ด้วย R, 6 ด้วย N, 7 ด้วยเครื่องหมายเซมิโคลอน ";"

ปรากฏว่าหมายเลขเฉพาะ (DN) ของเครื่องจักร H คือหมายเลข "K" เราสามารถอนุมานได้ว่า K เป็นตัวเลขที่ยาวมาก อาจมีหลายหมื่นหลัก แต่สิ่งนี้ไม่สำคัญต่อสิ่งที่จะกล่าวต่อไป

เครื่องจักร H มีหน้าที่แปลง ตัวเลข N ใดๆให้เป็นสตริงสัญลักษณ์ SD ที่เทียบเท่ากัน เพื่อให้เครื่องจักรย่อย D ทดสอบ (ในภาษาการเขียนโปรแกรม: H ส่ง "SD" ใดๆ ไปยัง D และ D จะส่งคืนค่า "น่าพอใจ" หรือ "ไม่น่าพอใจ") เครื่องจักร H ยังมีหน้าที่เก็บบันทึก R ("บันทึก"?) ของตัวเลขที่ประสบความสำเร็จ (เราสมมติว่าจำนวน SD ที่ "ประสบความสำเร็จ" คือ R นั้นน้อยกว่าจำนวน SD ที่ทดสอบ คือ N มาก) สุดท้าย H จะพิมพ์ตัวเลขแนวทแยง "beta-primed" B' ลงบนส่วนหนึ่งของเทป H สร้าง B' นี้โดยการ "จำลอง" (ในความหมายของคอมพิวเตอร์) "การเคลื่อนไหว" ของแต่ละเครื่องจักร/ตัวเลขที่ "น่าพอใจ" ในที่สุดเครื่องจักร/ตัวเลขที่กำลังทดสอบนี้จะมาถึง "ตัวเลข" ที่ R (1 หรือ 0) และ H จะพิมพ์ออกมา จากนั้น H จะรับผิดชอบในการ "ทำความสะอาดความยุ่งเหยิง" ที่เกิดจากการจำลอง โดยเพิ่มค่า N และดำเนินการทดสอบต่อไปเรื่อยๆอย่างไม่มีที่สิ้นสุด

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

ตัวอย่างเช่น สมมติว่าเครื่อง H ได้ทดสอบตัวเลข 13472 ตัว และได้ตัวเลขที่ถูกต้อง 5 ตัว นั่นคือ H ได้แปลงตัวเลข 1 ถึง 13472 เป็น SD (สตริงสัญลักษณ์) และส่งต่อไปยัง D เพื่อทดสอบ ผลที่ตามมาคือ H ได้นับตัวเลขที่ถูกต้อง 5 ตัว และประมวลผลตัวแรกไปที่ "หลัก" ที่ 1 ตัวที่สองไปที่หลักที่ 2 ตัวที่สามไปที่หลักที่ 3 ตัวที่สี่ไปที่หลักที่ 4 และตัวที่ห้าไปที่หลักที่ 5 ตอนนี้จำนวนนับอยู่ที่ N = 13472, R = 5 และ B' = ".10011" (ตัวอย่างเช่น) H ทำความสะอาดข้อมูลบนเทป และดำเนินการต่อไป:

เครื่อง Hเพิ่มค่าNเป็น 13473 และแปลง "13473" เป็นสตริงสัญลักษณ์ ADRLD หากเครื่องย่อย D พิจารณาว่า ADRLD ไม่เป็นที่น่าพอใจ เครื่อง H จะคงค่าบันทึก R ไว้ที่ 5 เครื่อง H จะเพิ่มค่า N เป็น 13474 และดำเนินการต่อไป ในทางกลับกัน หาก D พิจารณาว่า ADRLD เป็นที่น่าพอใจ เครื่อง H จะเพิ่มค่า R เป็น 6 เครื่อง H จะแปลง N (อีกครั้ง) เป็น ADLRD [นี่เป็นเพียงตัวอย่าง ADLRD อาจไม่มีประโยชน์] และ "เรียกใช้" โดยใช้เครื่องอเนกประสงค์ U จนกว่าเครื่องที่กำลังทดสอบ (U ที่ "เรียกใช้" ADRLD) จะพิมพ์ "ตัวเลข" ตัวที่ 6 คือ 1 หรือ 0 เครื่อง H จะพิมพ์ตัวเลขตัวที่ 6 นี้ (เช่น "0") ในพื้นที่ "เอาต์พุต" ของเทป (เช่น B' = ".100110")

H ทำความสะอาดสิ่งสกปรก แล้วเพิ่มค่าNเป็น 13474

กระบวนการทั้งหมดจะคลี่คลายเมื่อ H มาถึงหมายเลขของตัวเอง K เราจะดำเนินการต่อด้วยตัวอย่างของเรา สมมติว่าค่าการนับ/บันทึกที่สำเร็จ R อยู่ที่ 12 ในที่สุด H ก็มาถึงหมายเลขของตัวเองลบ 1 นั่นคือ N = K-1 = 4335...321 4และหมายเลขนี้ไม่สำเร็จ จากนั้น H จะเพิ่มค่า N เพื่อให้ได้ K = 4335...321 5นั่นคือหมายเลขของตัวเอง H แปลงค่านี้เป็น “LDDR...DCAR” และส่งไปยังเครื่องตัดสินใจ D เครื่องตัดสินใจ D ต้องส่งคืน “น่าพอใจ” (นั่นคือ H ต้องทำการทดสอบต่อไปเรื่อยๆอย่างไม่มีที่สิ้นสุดเพราะมัน “ปราศจากวงกลม”) ดังนั้น H จึงเพิ่มค่าการนับ R จาก 12 เป็น 13 จากนั้นแปลงหมายเลขที่กำลังทดสอบ K กลับเป็นค่าเบี่ยงเบนมาตรฐาน (SD) และใช้ U เพื่อจำลอง แต่หมายความว่า H จะจำลองการเคลื่อนไหวของตัวเอง สิ่งแรกที่การจำลองจะทำคืออะไร? การจำลอง K-aka-H นี้จะสร้าง N ใหม่ หรือ "รีเซ็ต" N "เก่า" ให้เป็น 1 K-aka-H นี้จะสร้าง R ใหม่ หรือ "รีเซ็ต" R "เก่า" ให้เป็น 0 H เก่าจะ "รัน" K-aka-H ใหม่ไปเรื่อยๆ จนกว่าจะถึงตัวเลขที่ 12

แต่เครื่อง K-aka-H ไม่สามารถคำนวณไปถึงตัวเลขที่ 13 ได้ ในที่สุด K-aka-H ก็คำนวณได้ 4335...321 5อีกครั้ง และK-aka-Hต้องทำการทดสอบซ้ำ เครื่อง K-aka-Hจะไม่มีวันคำนวณไปถึงตัวเลขที่ 13 ได้ เครื่อง H อาจจะพิมพ์สำเนาของตัวเองไปเรื่อยๆ อย่างไม่มีที่สิ้นสุดบนเทปเปล่า แต่สิ่งนี้ขัดแย้งกับสมมติฐานที่ว่า H เป็นเครื่องคำนวณที่น่าพอใจและไม่เป็นวงกลม ซึ่งจะพิมพ์เลข 1 และ 0 บนแนวทแยงมุมไปเรื่อยๆ อย่างไม่มีที่สิ้นสุด (เราจะเห็นผลลัพธ์เดียวกันนี้หากตั้งค่า N เป็น 1 และ R เป็น 0)

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

เนื้อหาสั้นกว่าหนึ่งหน้า และการเปลี่ยนจากข้อสมมติฐานไปสู่ข้อสรุปนั้นคลุมเครือ

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

เมื่อทราบว่ามีเครื่องจักร E อยู่แล้ว ทิวริงจึงดำเนินการดังต่อไปนี้:

1. ถ้าเครื่อง E มีอยู่จริง ก็จะมีเครื่อง G อยู่จริง ซึ่งสามารถระบุได้ว่า M พิมพ์ 0 บ่อยเป็นอนันต์หรือไม่ และ
2. ถ้า E มีอยู่จริง ก็จะมีกระบวนการอื่นอยู่ด้วย [เราอาจเรียกกระบวนการ/เครื่องจักรนั้นว่า G' เพื่อเป็นข้อมูลอ้างอิง] ที่ตรวจสอบว่า M พิมพ์ 1 ซ้ำๆ อย่างไม่มีที่สิ้นสุดหรือไม่ ดังนั้น
3. เมื่อเรารวม G กับ G' เราจะได้กระบวนการที่ตรวจสอบว่า M พิมพ์ตัวเลขจำนวนอนันต์หรือไม่ และ
4. ถ้ากระบวนการ "G กับ G'" ตรวจสอบว่า M พิมพ์รูปทรงจำนวนอนันต์ แสดงว่า "G กับ G'" ได้ตรวจสอบแล้วว่า M ไม่มีวงกลม แต่
5. กระบวนการ "G กับ G'" ที่ตรวจสอบว่า M เป็นวงกลมที่ปราศจากวงกลมหรือไม่ ตามการพิสูจน์ข้อ 1 นั้น ไม่สามารถมีอยู่ได้ ดังนั้น
6. เครื่องจักร E ไม่มีอยู่จริง

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

นี่คือตัวอย่าง: สมมติว่าเราเห็นลานจอดรถที่เต็มไปด้วยรถยนต์หลายร้อยคัน เราตัดสินใจเดินไปรอบๆ ลานจอดรถทั้งหมดเพื่อมองหา “รถยนต์ที่มีล้อแบน (ล้อเสีย)” หลังจากนั้นประมาณหนึ่งชั่วโมง เราพบ “รถยนต์ที่มีล้อเสีย” สองคัน ตอนนี้เราสามารถพูดได้อย่างแน่นอนว่า “รถยนต์บางคันมีล้อเสีย” หรือเราอาจพูดว่า “ไม่เป็นความจริงที่ว่า ‘รถยนต์ทุกคันมีล้อที่ดี’” หรือ “เป็นความจริงที่ว่า ‘รถยนต์บางคันไม่มีล้อที่ดี’” ลองไปที่ลานจอดรถอีกแห่งหนึ่ง ที่นี่เราพบว่า “รถยนต์ทุกคันมีล้อที่ดี” เราอาจพูดได้ว่า “ไม่มีรถยนต์แม้แต่คันเดียวที่มีล้อเสีย” ดังนั้นเราจะเห็นว่า ถ้าเราสามารถพูดอะไรเกี่ยวกับรถยนต์แต่ละคันแยกกันได้ เราก็สามารถพูดอะไรเกี่ยวกับรถยนต์ทั้งหมดโดยรวมได้เช่นกัน

นี่คือสิ่งที่ทัวริงทำ: จากเครื่องจักร Mเขาจะสร้างชุดเครื่องจักร { M 1, M 2, M 3, M 4, ..., Mn } และสำหรับแต่ละเครื่องจักร เขาจะเขียนประโยคว่า “ Xพิมพ์เลข 0 อย่างน้อยหนึ่งตัว” และอนุญาตให้มี “ ค่าความจริง ” เพียงสองค่าเท่านั้น คือ จริง = ว่างเปล่า หรือ เท็จ = :0: ทีละเครื่อง เขาจะตรวจสอบค่าความจริงของประโยคสำหรับแต่ละเครื่องจักร และสร้างสตริงของช่องว่างหรือ :0: หรือการผสมผสานกันของสิ่งเหล่านี้ เราอาจได้บางอย่างเช่นนี้: “ M 1 พิมพ์ 0” = จริง และ “ M 2 พิมพ์ 0” = จริง และ “ M 3 พิมพ์ 0” = จริง และ “ M 4 พิมพ์ 0” = เท็จ, ... และ “ Mnพิมพ์ 0” = เท็จ เขาได้สตริงนี้มา

BBB:0::0::0: ... :0: ... ไม่มีที่สิ้นสุด

ถ้ามีเครื่องจักรจำนวนอนันต์Mnในทางกลับกัน ถ้าเครื่องจักรทุกเครื่องผลิตค่า "จริง" ออกมา นิพจน์บนเทปจะเป็น

BBBBB....BBBB ... ไม่มีที่สิ้นสุด

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

สิ่งที่ทิวริงต้องทำต่อไปก็คือ สร้างกระบวนการเพื่อสร้างลำดับของ Mn จาก M เพียงตัวเดียว

สมมติว่าMพิมพ์รูปแบบนี้:

M => ...AB01AB0010AB…

ทิวริงสร้างเครื่องจักรอีกเครื่องหนึ่งชื่อ F ซึ่งรับ M และประมวลผลลำดับของ Mn ที่แปลง 0 ตัวแรก n ตัวให้เป็น “0-bar” ( 0 ):

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

ตอนนี้ทิวริงได้รวมเครื่องจักร E และ F เข้าด้วยกันเป็นเครื่องจักรประกอบ G โดย G เริ่มต้นด้วยเครื่องจักร M ดั้งเดิม จากนั้นใช้ F เพื่อสร้างเครื่องจักรที่ตามมาทั้งหมด M1, M2, ..., Mn จากนั้น G จะใช้ E เพื่อทดสอบเครื่องจักรแต่ละเครื่องโดยเริ่มจาก M หาก E ตรวจพบว่าเครื่องจักรไม่เคยพิมพ์เลขศูนย์ G จะพิมพ์ :0: สำหรับเครื่องจักรนั้น หาก E ตรวจพบว่าเครื่องจักรพิมพ์เลข 0 (เราสันนิษฐานเอาเอง ทิวริงไม่ได้กล่าวไว้) G จะพิมพ์ :: หรือข้ามรายการนี้ไป ปล่อยให้ช่องว่างว่างเปล่า เราจะเห็นว่ามีหลายสิ่งที่สามารถเกิดขึ้นได้

G จะไม่พิมพ์เลข 0 เลย หาก Mn ทุกตัวพิมพ์เลข 0 หรือ G จะพิมพ์เลข 0 ไปเรื่อยๆ อย่างไม่มีที่สิ้นสุด หาก M ทุกตัวไม่พิมพ์เลข 0 หรือ G จะพิมพ์เลข 0 สักพักแล้วหยุด

ทีนี้ เมื่อเรานำ E ไปใช้กับ G เอง จะเกิดอะไรขึ้น?

ถ้า E(G) พิสูจน์ได้ว่า G ไม่เคยพิมพ์เลข 0 เลย แสดงว่าเรารู้ว่า Mn ทั้งหมดพิมพ์เลข 0 และนั่นหมายความว่า เนื่องจาก Mn ทั้งหมดมาจาก M ดังนั้น M เองจึงพิมพ์เลข 0 ไปเรื่อยๆ อย่างไม่มีที่สิ้นสุดหรือ ถ้า E(G) พิสูจน์ได้ว่า G พิมพ์เลข 0 แสดงว่าเรารู้ว่า Mn ไม่ได้พิมพ์เลข 0 ทั้งหมด ดังนั้น M จึงไม่พิมพ์เลข 0 ไปเรื่อยๆอย่าง ไม่มีที่สิ้นสุด

เนื่องจากเราสามารถใช้กระบวนการเดียวกันในการตรวจสอบว่า M พิมพ์ 1 เป็นอนันต์ครั้งหรือไม่ เมื่อเรารวมกระบวนการเหล่านี้เข้าด้วยกัน เราสามารถระบุได้ว่า M พิมพ์ 1 และ 0 เป็นอนันต์ หรือไม่ ดังนั้นเราจึงมีวิธีการตรวจสอบว่า M เป็นวงกลมที่ปราศจากวงกลมหรือไม่ ตามการพิสูจน์ข้อที่ 1 สิ่งนี้เป็นไปไม่ได้ ดังนั้นข้อความแรกที่ว่า E มีอยู่จึงผิด: E ไม่มีอยู่จริง

ที่นี่ Turing พิสูจน์ว่า " ปัญหาการตัดสินใจของ Hilbert ไม่มีคำตอบ" ^{[ 2 ]}ที่นี่เขา

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

ทั้งบทพิสูจน์ย่อยที่ 1 และ 2 จำเป็นต่อการสร้าง "ถ้าและเฉพาะเมื่อ" (กล่าวคือความสมมูลเชิงตรรกะ ) ที่จำเป็นสำหรับการพิสูจน์:

เซต E สามารถตัดสินได้ด้วยการคำนวณก็ต่อเมื่อทั้ง E และส่วนเติมเต็มของ E สามารถนับได้ด้วยการคำนวณ (Franzén, หน้า 67)

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

จากนั้นทิวริงพิสูจน์บทพิสูจน์ย่อยสองข้อ โดยข้อแรกต้องใช้ความพยายามอย่างมาก (ข้อที่สองเป็นบทพิสูจน์ผกผันของข้อแรก) จากนั้นเขาใช้การพิสูจน์โดยการหักล้าง (reductio ad absurdum ) เพื่อพิสูจน์ผลลัพธ์สุดท้ายของเขา:

1. มีสูตรUn (M) อยู่ สูตรนี้เป็นจริง และ
2. หาก สามารถแก้ ปัญหา Entscheidungsproblemได้แล้ว ก็จะมีกระบวนการเชิงกลสำหรับการพิจารณาว่าUn (M) สามารถพิสูจน์ได้ (อนุมานได้) หรือไม่ และ
3. โดยบทพิสูจน์เสริมข้อที่ 1 และ 2: Un (M) สามารถพิสูจน์ได้ก็ต่อเมื่อ0ปรากฏใน "การกำหนดค่าที่สมบูรณ์" บางอย่างของ M และ
4. ถ้า0ปรากฏใน "การกำหนดค่าที่สมบูรณ์" บางอย่างของ M แล้วจะมีกระบวนการเชิงกลที่สามารถกำหนดได้ว่า M ใดๆ จะพิมพ์0 ออกมาหรือ ไม่ และ
5. จากข้อพิสูจน์ที่ 2 ไม่มีกระบวนการเชิงกลใดที่จะสามารถระบุได้ว่าค่า M ใดๆ จะพิมพ์ค่า0 ออกมาหรือไม่ ดังนั้น
6. Un (M) ไม่สามารถพิสูจน์ได้ (มันเป็นจริง แต่พิสูจน์ ไม่ได้ ) ซึ่งหมายความว่าปัญหาการตัดสินใจไม่สามารถแก้ไขได้

[หากผู้อ่านตั้งใจจะศึกษาบทพิสูจน์โดยละเอียด ควรแก้ไขสำเนาหน้าบทพิสูจน์ที่สามด้วยการแก้ไขที่ทัวริงได้ให้ไว้ ผู้อ่านควรมีความรู้พื้นฐานที่มั่นคงใน (i) ตรรกศาสตร์ และ (ii) บทความของเคิร์ท เกอเดลเรื่อง " เกี่ยวกับข้อเสนอที่ไม่สามารถตัดสินได้อย่างเป็นทางการของ Principia Mathematica และระบบที่เกี่ยวข้อง " ^{[ b ]}สำหรับความช่วยเหลือเกี่ยวกับบทความของเกอเดล อาจศึกษาได้จาก เช่นErnest NagelและJames R. Newman , Gödel's Proof , New York University Press, 1958]

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

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

เบาะแสแรก: "ให้เราใส่คำอธิบายของ M ลงในรูปแบบมาตรฐานแรกของ §6" ส่วนที่ 6 อธิบายถึง "การเข้ารหัส" ที่เฉพาะเจาะจงมากของเครื่องจักร M บนเทปของ "เครื่องจักรสากล" U ซึ่งจำเป็นต้องให้ผู้อ่านรู้จักลักษณะเฉพาะบางประการของเครื่องจักรสากล U ของทัวริงและรูปแบบการเข้ารหัส

(i) เครื่องจักรสากลคือชุดคำสั่ง "สากล" ที่อยู่ใน "ตารางคำสั่ง" แยกต่างหากจากสิ่งนี้ บนเทปของ U จะมี "เครื่องคำนวณ" M อยู่ในรูปแบบ "รหัส M" ตารางคำสั่งสากลสามารถพิมพ์สัญลักษณ์A, C, D, 0, 1, u, v, w, x, y, z, : ลงบนเทป ได้ เครื่องจักรต่างๆ M สามารถพิมพ์สัญลักษณ์เหล่านี้ได้โดยอ้อมเท่านั้น โดยการสั่งให้ U พิมพ์

(ii) "รหัสเครื่อง" ของ M ประกอบด้วยตัวอักษรเพียงไม่กี่ตัวและเครื่องหมายเซมิโคลอน เช่นD, C, A, R, L, N, ;ตัวเลข (สัญลักษณ์) 1และ0 จะไม่ ปรากฏอยู่ใน "รหัส" ของ M เลย หาก M ต้องการให้ U พิมพ์สัญลักษณ์จากชุดค่าว่าง, 0, 1มันจะใช้รหัสใดรหัสหนึ่งต่อไปนี้เพื่อบอกให้ U พิมพ์สัญลักษณ์เหล่านั้น เพื่อให้เกิดความสับสนมากขึ้น ทัวริงเรียกสัญลักษณ์เหล่านี้ว่า S0, S1 และ S2 เช่น

ช่องว่าง = S0 = D

0 = S1 = DC

1 = S2 = DCC

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

(iv) ถ้า "เครื่องคำนวณ" คือ U+"รหัส M" แล้ว "รหัส M" จะปรากฏก่อนบนเทป เทปมีปลายด้านซ้าย และ "รหัส M" จะเริ่มต้นที่นั่นและดำเนินไปทางขวาในช่องสลับกัน เมื่อรหัส M สิ้นสุดลง (และต้องเป็นเช่นนั้น เนื่องจากสมมติฐานที่ว่ารหัส M เหล่านี้เป็นอัลกอริทึมแบบจำกัด) "ตัวเลข" จะเริ่มต้นด้วย1และ0ในช่องสลับกัน และดำเนินไปทางขวาเรื่อยๆ อย่างไม่มีที่สิ้นสุด ทัวริงใช้ช่องสลับ (ที่ว่างเปล่า) (เรียกว่าช่อง "E" หรือ "ลบได้") เพื่อช่วยให้ U+"รหัส M" ติดตามตำแหน่งของการคำนวณ ทั้งในรหัส M และใน "ตัวเลข" ที่เครื่องกำลังพิมพ์

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

(vi) ทิวริงได้ลดจำนวนคำสั่งที่เป็นไปได้มากมายใน "รหัส M" (อีกครั้ง: รหัสของ M ที่จะปรากฏบนเทป) ให้เหลือเพียงชุดมาตรฐานขนาดเล็กชุดหนึ่ง ซึ่งมีอยู่สามชุดคล้ายกับนี้: {qi Sj Sk R ql} เช่นถ้าเครื่องกำลังประมวลผลคำสั่ง #qi และสัญลักษณ์ Sj อยู่บนช่องสี่เหลี่ยมที่กำลังสแกน ให้พิมพ์สัญลักษณ์ Sk แล้วไปทางขวา จากนั้นไปที่คำสั่ง qlคำสั่งอื่นๆ ก็คล้ายกัน โดยเข้ารหัสสำหรับ "ซ้าย" L และ "ไม่เคลื่อนไหว" N ชุดคำสั่งนี้จะถูกเข้ารหัสด้วยสตริงของสัญลักษณ์ qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA....A แต่ละคำสั่งจะคั่นด้วยเครื่องหมายเซมิโคลอน ตัวอย่างเช่น {q5, S1 S0 L q3} หมายถึง: คำสั่ง #5: ถ้าสัญลักษณ์ที่สแกนเป็น0ให้พิมพ์ว่างไปทางซ้าย จากนั้นไปที่คำสั่ง #3 มันถูกเข้ารหัสดังนี้

; DAAAAADCDLDAAA

เบาะแสที่สอง: ทิวริงกำลังใช้แนวคิดที่นำเสนอในบทความของเกอเดล นั่นคือ "การทำให้เป็นแบบเกอเดล" (อย่างน้อยบางส่วนของ) สูตรสำหรับUn (M) เบาะแสนี้ปรากฏเฉพาะในเชิงอรรถในหน้า 138 ( เดวิส (1965)หน้า 138): "ลำดับของจำนวนเฉพาะ r ตัวถูกแทนด้วย^ (r)" ( ibid .) [ในที่นี้ r ภายในวงเล็บ "ถูกยกกำลัง"] "ลำดับของจำนวนเฉพาะ" นี้ปรากฏในสูตรที่เรียกว่า F^(n)

เบาะแสที่สาม: นี่เป็นการยืนยันเบาะแสที่สอง ความพยายามครั้งแรกของทัวริงในการพิสูจน์ใช้สำนวนว่า:

(Eu)N(u) & (x)(... ฯลฯ ...) ^{[ 6 ]}

ก่อนหน้านี้ในบทความ Turing เคยใช้สำนวนนี้มาก่อน (หน้า 138) และกำหนด N(u) ให้หมายถึง "u เป็นจำนวนเต็มที่ไม่เป็นลบ" ( ibid .) (กล่าวคือ จำนวน Gödel) แต่ด้วยการแก้ไขของ Bernays ทำให้ Turing ละทิ้งแนวทางนี้ (กล่าวคือ การใช้ N(u)) และสถานที่เดียวที่ "จำนวน Gödel" ปรากฏอย่างชัดเจนคือที่ที่เขาใช้ F^(n)

แล้วสิ่งนี้หมายความว่าอย่างไรสำหรับการพิสูจน์? เบาะแสแรกหมายความว่าการตรวจสอบ M-code บนเทปอย่างง่ายจะไม่สามารถเปิดเผยได้ว่าสัญลักษณ์0เคยถูกพิมพ์โดย U+"M-code" หรือไม่ เครื่องทดสอบอาจมองหาการปรากฏของDCในสตริงของสัญลักษณ์ที่แสดงถึงคำสั่ง แต่คำสั่งนี้จะถูก "ดำเนินการ" หรือไม่? ต้องมีบางสิ่งที่จะ "รันโค้ด" เพื่อหาคำตอบ สิ่งนั้นอาจเป็นเครื่องจักร หรืออาจเป็นบรรทัดในการพิสูจน์อย่างเป็นทางการ เช่น บทพิสูจน์ย่อยข้อที่ 1

เบาะแสข้อที่สองและสามบ่งชี้ว่า เนื่องจากพื้นฐานของการพิสูจน์มาจากบทความของเกอเดล การพิสูจน์จึงทำได้ยาก

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

ทั้งบทพิสูจน์ย่อยที่ 1 และ 2 จำเป็นต่อการสร้าง "ถ้าและเฉพาะเมื่อ" (กล่าวคือ ความสมมูลเชิงตรรกะ) ที่จำเป็นสำหรับการพิสูจน์:

เซต E สามารถตัดสินได้ด้วยการคำนวณก็ต่อเมื่อทั้ง E และส่วนเติมเต็มของ E สามารถนับได้ด้วยการคำนวณ (Franzén, หน้า 67)

อ้างอิงจากฟรานเซน:

กล่าวได้ว่าประโยค A สามารถตัดสินได้ในระบบที่เป็นทางการ S ถ้า A หรือประโยคปฏิเสธของ A สามารถพิสูจน์ได้ใน S (Franzén, หน้า 65)

ฟรานเซนได้ให้คำจำกัดความของคำว่า "พิสูจน์ได้" ไว้แล้วในหนังสือของเขา:

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

ดังนั้น "ประโยค" จึงเป็นสตริงของสัญลักษณ์ และ "ทฤษฎีบท" จึงเป็นสตริงของสตริงของสัญลักษณ์

ทิวริงต้องเผชิญกับภารกิจต่อไปนี้:

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

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

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

ตัวอย่างของเราอ้างอิงจาก แบบจำลองเครื่องจักรทัวริงแบบ ดัดแปลง หลังยุคทัวริง (Post–Turing machine) แบบจำลองนี้จะพิมพ์เฉพาะสัญลักษณ์ 0 และ 1 เท่านั้น เทปว่างจะถือว่าเป็นสัญลักษณ์ b ทั้งหมด แบบจำลองที่ดัดแปลงของเราต้องการเพิ่มคำสั่งอีกสองคำสั่งลงในคำสั่งหลังยุคทัวริง 7 คำสั่ง ตัวย่อที่เราจะใช้มีดังนี้:

R, ขวา: มองไปทางขวาและเลื่อนเทปไปทางซ้าย หรือเลื่อนหัวเทปไปทางขวา L, ซ้าย: มองไปทางซ้ายและเลื่อนเทปไปทางขวา หรือเลื่อนหัวเทปไปทางซ้าย E, ลบช่องที่สแกนแล้ว (เช่น ทำให้ช่องว่างเปล่า) P0,: พิมพ์ 0 ในช่องที่สแกนแล้ว P1,: พิมพ์ 1 ในช่องที่สแกนแล้ว Jb_n, JUMP-IF-blank-to-instruction_#n, J0_n, JUMP-IF-0-to-instruction_#n, J1_n, JUMP-IF-1-to-instruction_#n, HALT.

ในกรณีของ R, L, E, P0 และ P1 หลังจากทำงานเสร็จแล้ว เครื่องจะดำเนินการต่อไปยังคำสั่งถัดไปตามลำดับตัวเลข เช่นเดียวกับการกระโดดหากการทดสอบล้มเหลว

แต่เพื่อความกระชับ ตัวอย่างของเราจะใช้เพียงสามช่องสี่เหลี่ยม และช่องเหล่านี้จะเริ่มต้นด้วยช่องว่างสามช่อง โดยมีช่องที่สแกนอยู่ทางซ้าย เช่น bbb ด้วยสัญลักษณ์สองตัวคือ 1, 0 และช่องว่าง เราสามารถสร้างรูปแบบที่แตกต่างกันได้ 27 แบบ:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

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

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

b(b)0 หมายความว่า "เทปเป็นช่องว่างทางซ้ายของช่องว่างด้านซ้าย แต่ช่องว่างด้านซ้าย 'กำลังเล่น' ช่องที่สแกนเป็นช่องว่าง '0' ช่องว่างไปทางขวา" 1(0)1 หมายความว่า "เทปเป็นช่องว่างทางซ้าย จากนั้น 1 ช่องที่สแกนเป็น '0'"

มาลองเขียนโปรแกรมง่ายๆ กัน:

เริ่มต้น: P1, R, P1, R, P1, H

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

เริ่มการตั้งค่า: (b) P1, การตั้งค่า #1: (1) R, การตั้งค่า #2: 1(b) P1, การตั้งค่า #3: 1(1) R, การตั้งค่า #4: 11(b) P1, การตั้งค่า #5: 11(1) H

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

เริ่มต้น: P1, R, P1, R, P1, P0, L, J1_7, H (b)bb P1, (1)bb R, 1(b)b P1, 1(1)b R, 11(b) P1, 11(1) P0, 11(0) L, 1(1)0 J1_7 1(1)0 L (1)10 J0_7 (1)10 L (b)110 J0_7 (b)110 H

ในตอนท้ายนี้ เราพบว่าช่องว่างทางด้านซ้ายได้ "เข้ามามีบทบาท" ดังนั้นเราจึงปล่อยมันไว้เป็นส่วนหนึ่งของการจัดวางโดยรวม

เมื่อเราทำงานของเราอย่างถูกต้องแล้ว เราก็เพิ่มเงื่อนไขเริ่มต้นและดูว่า "ทฤษฎีบทจะไปในทิศทางใด" การจัดเรียงที่ได้ผลลัพธ์คือเลข 110 ซึ่งเป็นข้อพิสูจน์

• งานแรกของทิวริงคือการเขียนนิพจน์ทั่วไปโดยใช้สัญลักษณ์ทางตรรกะเพื่อแสดงสิ่งที่ Un(M) ของเขาจะทำได้อย่างแม่นยำ
• ภารกิจที่สองของทิวริงคือการ "แปลง" สายอักขระสัญลักษณ์ที่ยาวเหยียดนี้ให้เป็นแบบเกอเดล โดยใช้วิธีการของเกอเดลในการกำหนดจำนวนเฉพาะให้กับสัญลักษณ์และยกกำลังจำนวนเฉพาะเหล่านั้นด้วยกำลังของจำนวนเฉพาะ ตามวิธีการของเกอเดล

การพิสูจน์ของ Turing มีความซับซ้อนเนื่องจากมีคำจำกัดความจำนวนมาก และสับสนกับสิ่งที่Martin Davisเรียกว่า "รายละเอียดทางเทคนิคเล็กน้อย" และ "...รายละเอียดทางเทคนิคที่ไม่ถูกต้องตามที่กำหนด" ^{[ c ]} Turing เองได้ตีพิมพ์ "การแก้ไข" ในปี 1938: "ผู้เขียนขอขอบคุณP. Bernaysที่ชี้ให้เห็นข้อผิดพลาดเหล่านี้" ^{[ 7 ]}

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

การแก้ไขของ Bernays สามารถพบได้ในDavis (1965)หน้า 152–154; ต้นฉบับสามารถพบได้ในชื่อ "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction," Proceedings of the London Mathematical Society (2), 43 (1938), 544-546

บทความของทิวริงฉบับออนไลน์มีการแก้ไขเหล่านี้อยู่ในภาคผนวก อย่างไรก็ตาม การแก้ไขเกี่ยวกับเครื่องจักรสากล (Universal Machine) ต้องค้นหาจากบทวิเคราะห์ที่จัดทำโดยเอมิล โพสต์

ในตอนแรก นักคณิตศาสตร์เพียงคนเดียวที่ให้ความสนใจอย่างใกล้ชิดกับรายละเอียดของการพิสูจน์คือ Post (ดู Hodges หน้า 125) — ส่วนใหญ่เป็นเพราะเขาได้ค้นพบการลดทอน "อัลกอริทึม" ในลักษณะเดียวกันไปสู่การกระทำแบบเครื่องจักรดั้งเดิมในเวลาเดียวกัน ดังนั้นเขาจึงให้ความสนใจในการพิสูจน์นี้เป็นการส่วนตัว ที่น่าแปลก (อาจเป็นเพราะสงครามโลกครั้งที่สองเข้ามาเกี่ยวข้อง) คือ Post ใช้เวลาประมาณสิบปีในการวิเคราะห์มันในภาคผนวกของบทความของเขาเรื่องRecursive Unsolvability of a Problem of Thueในปี 1947 ^{[ d ]}

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

หากการวิจารณ์ของเราถูกต้อง เครื่องจักรจะถูกเรียกว่าปราศจากวงกลมได้ก็ต่อเมื่อเป็นเครื่องคำนวณของทัวริงที่พิมพ์เลข 0 และ 1 ออกมาเป็นจำนวนอนันต์ และทฤษฎีบทสองข้อของทัวริงที่กล่าวถึงนั้นก็คือ ไม่มีเครื่องทัวริงใดที่เมื่อป้อนจำนวนเต็มบวก n ใดๆ จะสามารถระบุได้ว่า n เป็น DN ของเครื่องคำนวณของทัวริงที่ปราศจากวงกลมหรือไม่ [ประการที่สอง] ไม่มีเครื่องทัวริงแบบอนุมานใดที่เมื่อป้อนจำนวนเต็มบวก n ใดๆ จะสามารถระบุได้ว่า n เป็น DN ของเครื่องคำนวณของทัวริงที่พิมพ์สัญลักษณ์ใดๆ (เช่น 0) ออกมาหรือไม่^{[ f ]}

ใครก็ตามที่เคยพยายามอ่านหนังสือพิมพ์ฉบับนั้นจะเข้าใจข้อร้องเรียนของฮอดจ์ส:

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

1. จำนวนที่คำนวณได้ — จำนวนที่ค่าทศนิยมสามารถคำนวณได้ด้วยเครื่องจักร (เช่น ด้วยวิธีการจำกัด เช่น อัลกอริทึม)

2. M — เครื่องจักรที่มีตารางคำสั่งจำกัดและหัวสแกน/พิมพ์ M เคลื่อนเทปอนันต์ที่แบ่งออกเป็นช่องสี่เหลี่ยมแต่ละช่อง “สามารถบรรจุสัญลักษณ์ได้” คำสั่งของเครื่องจักรมีเพียงดังต่อไปนี้: เลื่อนไปทางซ้ายหนึ่งช่อง เลื่อนไปทางขวาหนึ่งช่อง พิมพ์สัญลักษณ์ p บนช่องที่สแกน ลบช่องที่สแกน ถ้าสัญลักษณ์คือ p ให้ทำคำสั่ง aaa ถ้าสัญลักษณ์ที่สแกนไม่ใช่ p ให้ทำคำสั่ง aaa ถ้าสัญลักษณ์ที่สแกนไม่ใช่ none ให้ทำคำสั่ง aaa ถ้าสัญลักษณ์ที่สแกนเป็น any ให้ทำคำสั่ง aaa [โดยที่ “aaa” คือตัวระบุคำสั่ง]

3. เครื่องคำนวณ — เครื่อง M ที่พิมพ์สัญลักษณ์สองประเภท สัญลักษณ์ประเภทแรกเรียกว่า "ตัวเลข" ซึ่งเป็นสัญลักษณ์ไบนารี 1 และ 0 เท่านั้น สัญลักษณ์ประเภทที่สองคือสัญลักษณ์อื่นๆ ทุกชนิด

ตัวเลข 4 ตัว — สัญลักษณ์1และ0หรือที่เรียกว่า “สัญลักษณ์ประเภทแรก”

5. การกำหนดค่า m — ตัวระบุคำสั่ง ซึ่งอาจเป็นสัญลักษณ์ในตารางคำสั่ง หรือสตริงของสัญลักษณ์ที่แสดงหมายเลขคำสั่งบนเทปของเครื่องอเนกประสงค์ (เช่น "DAAAAA = #5")

6 สัญลักษณ์ประเภทที่สอง — สัญลักษณ์ใดๆ ก็ตามที่ไม่ใช่1และ0

7. วงกลม — เครื่องคำนวณที่ไม่ประสบความสำเร็จ มันไม่สามารถพิมพ์ตัวเลข0หรือ1ซึ่งแทนเลขฐานสองของจำนวนที่มันคำนวณได้ ซ้ำไปซ้ำมาอย่างไม่มีที่สิ้นสุด

8. เครื่องคำนวณ แบบไร้วงกลม — เครื่องคำนวณที่ประสบความสำเร็จ มันพิมพ์ตัวเลข0หรือ1 ซ้ำไปเรื่อยๆ อย่างไม่มีที่สิ้นสุด ซึ่งตัวเลขเหล่านี้แทนค่าเลขฐานสองของจำนวนที่มันคำนวณได้

ลำดับที่ 9 — เช่นเดียวกับ “ลำดับที่คำนวณโดยเครื่อง”: สัญลักษณ์ชนิดแรก หรือที่เรียกว่าตัวเลข หรือสัญลักษณ์ 0 และ 1

ลำดับที่คำนวณได้ 10 ลำดับ — สามารถคำนวณได้โดยเครื่องจักรที่ไม่ต้องใช้รอบวงกลม

11 SD – คำอธิบายมาตรฐาน: ลำดับของสัญลักษณ์ A, C, D, L, R, N, “;” บนเทปของเครื่องทัวริง

12 DN — หมายเลขคำอธิบาย : SD ที่แปลงเป็นตัวเลข: 1=A, 2=C, 3=D, 4=L, 5=R, 6=N, 7=;

13 M(n) — เครื่องจักรที่มี DN เป็นหมายเลข “n”

14 น่าพอใจ — SD หรือ DN ที่แสดงถึงเครื่องจักรที่ไม่มีวงกลม

15. U — เครื่องจักรที่ติดตั้งตารางคำสั่ง "สากล" หาก U ได้รับ "เทปที่มีคำสั่ง SD ของเครื่องคำนวณ M เขียนไว้ที่ตอนต้น U จะคำนวณลำดับเดียวกันกับ M"

16 β' —“beta-primed”: จำนวนที่เรียกว่า “จำนวนแนวทแยง” ซึ่งประกอบด้วยตัวเลขลำดับที่ n (เช่น 0 หรือ 1) ของลำดับที่คำนวณได้ลำดับที่ n [หรือ: จำนวนที่คำนวณได้ของ H ดูด้านล่าง]

17 u — SD ที่ไม่น่าพอใจ เช่น เป็นวงกลม

18 วินาที — น่าพอใจ กล่าวคือ SD ที่ไม่มีวงกลม

19 D — เครื่องจักรที่บรรจุอยู่ใน H (ดูด้านล่าง) เมื่อได้รับ SD ของเครื่องคำนวณ M ใดๆ D จะทดสอบ SD ของ M และหากเป็นวงกลมจะทำเครื่องหมายด้วย “u” และหากไม่มีวงกลมจะทำเครื่องหมายด้วย “s”

20 H — เครื่องคำนวณ H คำนวณ B' รักษาค่า R และ N H ประกอบด้วย D และ U และเครื่องจักร (หรือกระบวนการ) ที่ไม่ระบุรายละเอียดซึ่งรักษาค่า N และ R และให้ค่า SD ที่เทียบเท่ากับ N แก่ D E ยังคำนวณรูปทรงของ B' และประกอบรูปทรงของ B' ด้วย

21 R — บันทึกหรือนับจำนวน SD ที่ประสบความสำเร็จ (ปราศจากวงกลม) ที่ทดสอบโดย D

22 N — ตัวเลขที่ขึ้นต้นด้วย 1 ซึ่งจะถูกแปลงเป็น SD โดยเครื่องจักร E โดยเครื่องจักร E จะเก็บรักษาค่า N ไว้

23 K — ตัวเลข DN ของ H

จำเป็นสำหรับหลักฐาน #3

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

24 การกำหนดค่าที่สมบูรณ์ — หมายเลข (ตัวเลข1หรือ0 ) ของช่องสี่เหลี่ยมที่สแกน ลำดับที่สมบูรณ์ของสัญลักษณ์ทั้งหมดบนเทป และการกำหนดค่า m (ตัวระบุคำสั่ง ซึ่งอาจเป็นสัญลักษณ์หรือสตริงของสัญลักษณ์ที่แทนตัวเลข เช่น "คำสั่ง DAAAA = #5")

25 RSi(x, y) — "ในโครงสร้างสมบูรณ์ x ของ M สัญลักษณ์บนช่อง y คือ Si; "โครงสร้างสมบูรณ์" คือคำจำกัดความที่ 5

26 I(x, y) — "ในการกำหนดค่าสมบูรณ์ x ของ M สี่เหลี่ยม y จะถูกสแกน"

27 Kqm(x) — "ในการกำหนดค่าสมบูรณ์ x ของ M การกำหนดค่าเครื่องจักร (หมายเลขคำสั่ง) คือ qm"

28 F(x,y) — "y คือ ตัวสืบทอด โดยตรงของ x" (ตามการใช้ "f" ของ Gödel ในฐานะฟังก์ชันตัวสืบทอด)

29 G(x,y) — "x มาก่อน y" ไม่จำเป็นต้องอยู่ติดกันเสมอไป

30 Inst{qi, Sj Sk L ql}เป็นตัวย่อ เช่นเดียวกับInst{qi, Sj Sk R ql}และInst{qi, Sj Sk N ql}ดูรายละเอียดด้านล่าง

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

ตัวอย่างเช่น การดำเนินการในบรรทัดแรกคือ PSk = พิมพ์สัญลักษณ์ Sk จากชุดA, C, D, 0, 1, u, v, w, x, y, z, :จากนั้นเลื่อนเทปไปทางซ้าย

นอกจากนี้เขายังย่อคำเหล่านี้เพิ่มเติมดังนี้: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

ในบทพิสูจน์ที่ 3 เขาเรียกสิ่งแรกนี้ว่า “Inst{qi Sj Sk L ql}” และเขาแสดงวิธีการเขียนเครื่องจักร SD ทั้งหมดในรูปของการเชื่อมโยงเชิงตรรกะ (ตรรกะ OR): สตริงนี้เรียกว่า “Des(M)” เช่นเดียวกับ “คำอธิบายของ M” กล่าวคือ ถ้าเครื่องจักรพิมพ์ 0 จากนั้นพิมพ์ 1 และ 0 สลับกันในช่องสี่เหลี่ยมไปทางขวาเรื่อยๆ อย่างไม่มีที่สิ้นสุด ก็อาจจะมีตาราง (ตัวอย่างที่คล้ายกันปรากฏในหน้า 119):

q1, ว่างเปล่า, P0, R, q2 q2, ว่างเปล่า, P-ว่างเปล่า, R, q3 q3, ว่างเปล่า, P1, R, q4 q4, ว่างเปล่า, P-ว่างเปล่า, R, q1

(โค้ดนี้ถูกลดรูปให้เป็นรูปแบบมาตรฐานโดยใช้คำสั่ง “p-blank” ดังนั้นจึงแตกต่างจากตัวอย่างของ Turing เล็กน้อย) หากนำไปใส่ในรูปแบบ “Inst( )” คำสั่งจะเป็นดังต่อไปนี้ (โปรดจำไว้ว่า: S0 ว่างเปล่า, S1 = 0, S2 = 1):

Inst {q1 S0 S1 R q2} Inst {q2 S0 S0 R q3} Inst {q3 S0 S2 R q4} Inst {q4 S0 S0 R q1}

การลดรูปไปสู่คำอธิบายมาตรฐาน (SD) จะเป็นดังนี้:

; แด๊ดดีอาร์เอเอ ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA ;

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