ปัญหาสไตล์เกอเดล ... มีเครื่องจักรคำนวณที่สามารถพิมพ์ข้อความ (expression) ได้หลากหลายข้อความ โดยแต่ละข้อความจะสร้างจากสัญลักษณ์เพียง 5 ตัว คือ ~ P N ( )
คำว่าข้อความหมายถึงลำดับของสัญลักษณ์อย่างน้อยหนึ่งตัวที่มีความยาวจำกัด และเป็นลำดับสร้างจากสัญลักษณ์ 5 ตัวดังกล่าวนั้น เราเรียกข้อความ X ว่าเป็นข้อความที่พิมพ์ได้ (printable) ถ้าเครื่องจักรนี้สามารถพิมพ์มันออกมาได้ นอกจากนี้ เครื่องจักรของเรายังถูกโปรแกรมให้ข้อความใด ๆ ก็ตามที่เครื่องจักรสามารถพิมพ์ออกมาได้ สุดท้ายแล้ว ข้อความนั้นจะต้องถูกพิมพ์ออกมา เรากำหนดให้นอร์ม (norm) ของข้อความ X คือข้อความ X(X) เช่น นอร์มของ P~ คือ P~(P~) เมื่อ X คือข้อความใด ๆ คำว่า ประโยค (sentence) คือข้อความที่อยู่ในรูปใดรูปหนึ่งจาก 4 รูปต่อไปนี้ หนึ่ง P(X) สอง PN(X) สาม ~P(X) และสี่ ~PN(X) ต่อมา เรากำหนดความหมายให้กับสัญลักษณ์ดังนี้ สัญลักษณ์ P แทน “เป็นข้อความที่พิมพ์ได้” สัญลักษณ์ N แทน “นอร์มของ” และสัญลักษณ์ ~ แทนการปฏิเสธ หรือ “ไม่” จากนั้น เรานิยามประโยค P(X) ว่าเป็นจริง (true) ก็ต่อเมื่อ X เป็นข้อความที่พิมพ์ได้ เรานิยาม PN(X) ว่าเป็นจริง ก็ต่อเมื่อ นอร์มของ X เป็นข้อความที่พิมพ์ได้ เรานิยาม ~P(X) ว่าเป็นจริง ก็ต่อเมื่อ X ไม่เป็นข้อความที่พิมพ์ได้ หรือพูดอีกอย่างว่า X เป็นข้อความที่พิมพ์ไม่ได้ และนิยาม ~PN(X) ว่าเป็นจริง ก็ต่อเมื่อ นอร์มของ X เป็นข้อความที่พิมพ์ไม่ได้ ถึงจุดนี้เราได้กำหนดนิยามอย่างชัดเจนแล้วว่าประโยคจะเป็นจริงเมื่อไร และจากนิยามทั้งหมด เราจะได้กรณีปัญหาการอ้างอิงตัวเอง (self-reference) ที่น่าสนใจข้อหนึ่ง เนื่องจากเครื่องจักรกำลังพิมพ์ประโยคอันหลากหลายเกี่ยวกับข้อความที่ตัวมันเองสามารถพิมพ์ได้หรือไม่สามารถพิมพ์ได้ออกมา นั่นคือ เครื่องจักรกำลังพูดถึงพฤติกรรมของตัวเอง กำหนดให้เครื่องจักรมีความแม่นยำสมบูรณ์แบบ กล่าวคือ ทุกประโยคที่เครื่องจักรเครื่องนี้พิมพ์ออกมาเป็นประโยคที่เป็นจริง เช่น ถ้ามันพิมพ์ P(X) ออกมา ก็แปลว่า X เป็นข้อความที่สามารถพิมพ์ได้ (ถ้า X ยังไม่เคยถูกพิมพ์ออกมาก่อนหน้า มันก็จะต้องถูกพิมพ์ออกมาแน่ ๆ ในอนาคต) หรือ ถ้า PN(X) เป็นข้อความที่สามารถพิมพ์ได้ แล้ว X(X) (นอร์มของ X) ก็ต้องเป็นข้อความที่สามารถพิมพ์ได้เช่นกัน คราวนี้ถ้าเรากำหนดให้ X เป็นข้อความที่สามารถพิมพ์ได้ คำถามที่ตามมาคือ P(X) จะเป็นข้อความที่พิมพ์ได้ด้วยรึเปล่า คำตอบคือไม่จำเป็น จริงอยู่ ถ้า X เป็นข้อความที่พิมพ์ได้ ประโยค P(X) ย่อมเป็นจริง แต่ไม่ได้มีการกำหนดว่าเครื่องจักรเครื่องนี้สามารถพิมพ์ทุกประโยคที่เป็นจริงได้ เพียงแค่กำหนดว่ามันพิมพ์ข้อความที่เป็นเท็จไม่ได้ ถ้าถามว่า เป็นไปได้หรือไม่ที่เครื่องจักรสามารถพิมพ์ประโยคที่เป็นจริงได้ทุกประโยค คำตอบคือ เป็นไปไม่ได้ และโจทย์สำหรับคุณผู้อ่านตอนนี้คือ ให้หาประโยคที่เป็นจริงที่เครื่องจักรไม่สามารถพิมพ์ได้ ปัญหาสไตล์เกอเดลอีกข้อหนึ่ง ... ปัญหาข้อนี้คล้ายกับข้อก่อนหน้า และจะเป็นปัญหาที่แนะนำให้คุณผู้อ่านรู้จักกับการกำหนดตัวเลขแบบเกอเดล (Gödel numbering) กำหนดให้เครื่องจักรสามารถพิมพ์ข้อความที่สร้างจากสัญลักษณ์ 5 ตัวต่อไปนี้ ~ P N 1 0 สำหรับข้อนี้ เราจะเขียนจำนวนนับในรูปของเลขฐานสอง (หรือลำดับของสัญลักษณ์ 0 กับ 1) เราจะกำหนดตัวเลขตัวหนึ่งให้กับแต่ละข้อความ และเรียกตัวเลขตัวนั้นว่าจำนวนเกอเดล (Gödel number) ของข้อความ โดยมีหลักเกณฑ์การกำหนดตัวเลขเกอเดลดังต่อไปนี้ ตัวเลขเกอเดลของข้อความที่มีสัญลักษณ์ตัวเดียว อันได้แก่ ~, P, N, 1, 0 คือ 10, 100, 1000, 10000, 100000 ตามลำดับ และตัวเลขเกอเดลของข้อความที่มีสัญลักษณ์มากกว่าหนึ่งตัวคือตัวเลขที่แทนที่สัญลักษณ์แต่ละตัวด้วยตัวเลขเกอเดลของมัน เช่น PNP มีตัวเลขเกอเดลคือ 1001000100 ในที่นี้ เราจะนิยามนอร์มของข้อความเสียใหม่ว่า นอร์มของข้อความใดคือข้อความนั้นที่ตามด้วยเลขเกอเดลของมัน เช่น นอร์มของ PNP คือ PNP1001000100 แล้วนิยามของประโยคก็เปลี่ยนไปเป็นข้อความที่อยู่ในรูปใดรูปหนึ่งจาก 4 รูปต่อไปนี้ PX, PNX, ~PX และ ~PNX เมื่อ X เป็นจำนวนใด ๆ ที่เขียนรูปของเลขฐานสอง เราจะพูดว่า PX เป็นจริงก็ต่อเมื่อ X เป็นจำนวนเกอเดลของข้อความที่สามารถพิมพ์ได้ และ PNX เป็นจริงก็ต่อเมื่อ X เป็นจำนวนเกอเดลของข้อความที่นอร์มของข้อความนั้นสามารถพิมพ์ได้ และ ~PX เป็นจริงก็ต่อเมื่อ PX ไม่เป็นจริง (กล่าวคือ X ไม่เป็นจำนวนเกอเดลของข้อความที่สามารถพิมพ์ได้) สุดท้าย ~PNX เป็นจริงก็ต่อเมื่อ PNX ไม่เป็นจริง เช่นเดียวกับปัญหาข้อก่อนหน้า เครื่องจักรจะไม่พิมพ์ประโยคที่เป็นเท็จ โจทย์ให้หาประโยคที่เป็นจริงที่เครื่องจักรไม่สามารถพิมพ์ได้ เฉลย ... สำหรับปัญหาข้อแรก ประโยคที่เป็นจริงที่เครื่องจักรไม่สามารถพิมพ์ได้คือ ~PN(~PN) เพราะจากนิยาม ประโยคนี้จะเป็นจริงก็ต่อเมื่อนอร์มของ ~PN ไม่สามารถพิมพ์ได้ และนอร์มของ ~PN ก็คือประโยค ~PN(~PN) ฉะนั้น ประโยคนี้จะเป็นจริงก็ต่อเมื่อประโยคนี้ไม่สามารถพิมพ์ได้ หมายความว่า ถ้าไม่ใช่กรณีที่ประโยคนี้เป็นจริงและไม่สามารถพิมพ์ได้ มันก็ต้องเป็นเท็จและสามารถพิมพ์ได้ แต่กรณีที่มันเป็นเท็จและสามารถพิมพ์ได้นั้นขัดกับข้อกำหนดที่ว่าเครื่องจักรไม่พิมพ์ข้อความที่ไม่จริง ฉะนั้น ประโยคดังกล่าวจึงเป็นประโยคที่เป็นจริงและไม่สามารถพิมพ์ได้ แทนที่จะพูดถึงเครื่องจักรกับการพิมพ์ข้อความ เราอาจใช้ตัวอย่างนี้พูดถึงระบบคณิตศาสตร์กับการพิสูจน์ประโยค โดยตีความ P เสียใหม่ จากสามารถพิมพ์ได้ด้วยเครื่องจักเป็นสามารถพิสูจน์ได้ (provable) ในระบบ แล้วกำหนดให้ระบบดังกล่าวมีความแม่นยำอย่างสมบูรณ์แบบ (หมายถึง เป็นไปไม่ได้ที่จะพิสูจน์ข้อความที่เป็นเท็จว่าเป็นจริงภายในระบบดังกล่าว) ฉะนั้น ประโยค ~PN(~PN) จึงเป็นประโยคที่เป็นจริงแต่ไม่สามารถพิสูจน์ได้ภายในระบบ ต่อมา ลองพิจารณาประโยค PN(~PN) ซึ่งเป็นประโยคที่เป็นเท็จ (เพราะนิเสธของมันเป็นจริง) ทำให้ประโยคนี้ก็พิสูจน์ว่าเป็นจริงไม่ได้ภายในระบบเช่นกัน ดังนั้นประโยค PN(~PN) จึงเป็นตัวอย่างของประโยคที่ไม่สามารถตัดสินได้ (undecidable) ในระบบ ประโยคที่ไม่สามารถตัดสินใจได้คือประโยคที่ทั้งตัวมันเองและนิเสธของมันต่างก็ไม่สามารถพิสูจน์ว่าเป็นจริงได้ภายในระบบ สำหรับปัญหาข้อที่สอง คำตอบคือ ~PN101001000