เครื่องทัวริง

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

'มันพิสูจน์ให้เห็นว่าวิธีการอัลกอริทึมไม่สามารถทดแทนสติปัญญาของมนุษย์ได้'

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

เครื่องทัวริงคืออะไร?

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

ทัวริงเครื่องกำลังตั้งท้องโดยอลันทัวริงในกระดาษน้ำเชื้อของเขา 'ON คำนวณตัวเลขกับใบสมัครเพื่อตีพิมพ์ในปี 1936 ความพยายามทัวริงเพื่อให้ตรงหักล้างไม่ได้ 'ปฏิบัติหลักฐาน' กับเดวิดฮิลแบร์ตEntscheidungsproblem Entscheidungsproblem เป็นวิธีการทางคณิตศาสตร์สำหรับความเป็นไปได้ที่เกิดขึ้นกับนักคณิตศาสตร์และนักตรรกวิทยาซึ่งเป็นความเป็นไปได้ของกรอบทางคณิตศาสตร์หนึ่งเดียวและทั้งหมดที่หลอมรวมกัน

ประวัติความเป็นมาของปัญหา Entscheidung

ในช่วงทศวรรษที่ 1690 Godfrey Wilhelm Leibniz นักคณิตศาสตร์ชาวเยอรมันหลังจากคิดค้นเครื่องคิดเลขเชิงกลแบบ 'Stepped Reckoner' ได้ขยายความคิดของเขาไปสู่การสร้างเครื่องจักรสากลที่สามารถตรวจสอบทุกคำสั่งทางคณิตศาสตร์ กล่าวคือเครื่องสามารถบอกได้ว่าคำสั่งที่สร้างขึ้นทางคณิตศาสตร์เป็นจริงหรือเท็จ นี่เป็นคำถามเชิงปรัชญามากกว่าคำถามเชิงตรรกะล้วนๆ อย่างไรก็ตามเรื่องนี้ต้องใช้วิธีการทางวิทยาศาสตร์ในการสำรวจและวิเคราะห์

ในปีพ. ศ. 2471 เดวิดฮิลเบิร์ตนักคณิตศาสตร์ชาวเยอรมันและผู้เสนอแนวทางลัทธิพิธีการได้เสนอคำถามสามข้อที่ International Congress of Mathematicians (ICM) เมือง Bologna:

1. คณิตศาสตร์สมบูรณ์หรือไม่?
2. คณิตศาสตร์สอดคล้องกันหรือไม่?
3. คณิตศาสตร์สามารถตัดสินใจได้หรือไม่?

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

'ไม่มีเครื่องจักรใดที่สร้างเครื่องจักรเครื่องที่สองและอินพุตที่ จำกัด ให้ตัดสินใจได้ว่าเครื่อง (เครื่องที่สอง) จะทำงานเสร็จหรือจะทำงานตลอดไป'

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

โครงสร้างของเครื่องพ่นไฟให้กับพฤติกรรม - เครื่องทำอะไร? เราตีความว่านี่เป็น 'อัลกอริทึม' ในการแก้ปัญหา ไม่มีอัลกอริทึมสากลที่สามารถตัดสินใจได้ว่าคำสั่งทางคณิตศาสตร์ที่กำหนดไว้จะมีหรือไม่

หมายเหตุ :

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

ให้เรานึกภาพอุปกรณ์ที่มีชุดสถานะที่เป็นไปได้ที่ จำกัด และไม่ต่อเนื่องกัน q 1 , q 2 , …. q n . สิ่งเหล่านี้จะเรียกว่าสถานะภายในของเครื่อง ทัวริงเองเรียกสิ่งเหล่านี้ว่าการกำหนดค่า m หรือการกำหนดค่าเครื่องจักร

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

ลักษณะการทำงานของเครื่องสามารถสรุปได้ดังนี้:

1. ลบหรือพิมพ์สัญลักษณ์ในช่องสี่เหลี่ยมที่สแกน

2. เลื่อนเทปไปทางซ้ายหรือขวา

3. เครื่องอาจเปลี่ยนสถานะ

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

ตัวอย่างเครื่องทัวริงแบบธรรมดา

เครื่องที่คำนวณ (พิมพ์บนเทปเปล่า) ลำดับง่ายๆของ 0s และ 1s: 01010101 …

• เครื่องจะต้องมีการกำหนดค่า m สี่แบบ 'b', 'c', 'e', ​​'f' และสามารถพิมพ์ '0' และ '1' ได้
• 'R' หมายถึง“ เครื่องเคลื่อนที่เพื่อให้สแกนสี่เหลี่ยมทางด้านขวาของเครื่องที่สแกนก่อนหน้านี้ทันที” ในทำนองเดียวกันสำหรับ "L"
• 'E' หมายถึง“ สัญลักษณ์ที่สแกนถูกลบ”
• 'P' ย่อมาจาก "ภาพพิมพ์" "P0" ย่อมาจาก "print 0" "P1" ย่อมาจาก "พิมพ์ 1"

ปัญญาประดิษฐ์และเครื่องจักรทัวริง

สิ่งที่เรารู้จักกันในชื่อ Turing Machines คือกระบวนการอัลกอริทึม ไม่มีกระบวนการ 'ตานางฟ้า' ที่สามารถเฝ้าดูกระบวนการที่สองได้ สิ่งนี้อาจอธิบายได้จากการเปรียบเทียบของชายตาบอดในทะเลทราย

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

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

ไฟในลำไส้

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

ปัญหาการตัดสินใจ

'เราสามารถข้ามปัญหาการตัดสินใจด้วยตัวเลือกแบบสุ่มได้หรือไม่?'

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

สัปดาห์ถัดไป: เทคโนโลยีการผูกขาด

สัปดาห์ก่อนหน้านี้: การปฏิวัติดิจิตอล - ไทม์ไลน์

สัปดาห์แรก: เครื่องจักรคิดได้หรือไม่?

ภาคผนวก

ลำดับที่คำนวณได้

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

เราใช้หลักการตั้งชื่อสำหรับเครื่องทัวริงที่คำนวณลำดับที่แตกต่างกัน ทัวริงเรียกคำอธิบายมาตรฐาน (SD) เหล่านี้หรือสะดวกกว่าสำหรับการรักษาเชิงตรรกะหมายเลขคำอธิบาย (DN)

คำอธิบายมาตรฐาน (ตามระบบการตั้งชื่อดั้งเดิมของทัวริง) สำหรับเครื่องทัวริงอาจเป็น DADDCRDAA, DAADDRDAAA, DAAADDCCRDAAAA, DAAAADDRDA เป็นต้น

หมายเลขคำอธิบายอาจเป็น 31332531173113353111731113322531111731111335317, 3133253117311335311173111332253111173111133531731323253117 เป็นต้น

ความไม่มั่นคงของปัญหาการตัดสินใจ

เราอาจมีรายชื่อเครื่องจักรทัวริงเป็น T1, T2, …, T3133253117311335311173111332253111173111133531731323253117, …, Tn n ยืนสำหรับหมายเลขคำอธิบายของ TM

นอกจากนี้เรายังอาจพิจารณา Turing Machine Tu ซึ่งมีหน้าที่คือยอมรับหมายเลขคำอธิบายของ Turing Machine Ti เครื่องอื่นและดำเนินการกับสัญลักษณ์ที่ตามมาของเทปที่ทำหน้าที่เป็น Ti TM 'สากล' นี้จะมีตัวเลขด้วยเช่นกัน

รายชื่อเครื่องจักรทัวริงทั้งหมดเริ่มจาก T1, T2, T3, …ไม่ทำงาน Turing Machines ส่วนใหญ่เป็น 'duds' ทัวริงโดยใช้ Diagonal Slash Argument ของ Cantor สามารถสรุปได้อย่างมีประสิทธิภาพว่าเครื่องที่ยอมรับหมายเลขคำอธิบายเป็นอินพุตและให้ 'จริง' หรือ 'เท็จ' เนื่องจากเครื่องเป็นคนโง่หรือไม่ตามลำดับนั้นเป็นไปไม่ได้ . Entscheidungsproblem ไม่มีทางแก้ !!! กล่าวคือไม่มี Turing Machine H ซึ่งสามารถระบุได้ว่า Turing Machine Ti จะหยุด (ประสบความสำเร็จ) หรือไม่นั่นคือมันทำงานไปเรื่อย ๆ หรือไม่

การอ้างอิง:

ความคิดใหม่ของจักรพรรดิโรเจอร์เพนโรสสำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด

เกี่ยวกับตัวเลขที่คำนวณได้พร้อมกับแอปพลิเคชันสำหรับปัญหา Entscheidungsproblem อลันทัวริง