คุณเคยสงสัยหรือไม่: อุปกรณ์ที่คุณกำลังอ่านบทความนี้คืออะไร? คอมพิวเตอร์คืออะไร?

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

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

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

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

ความสามารถในการคำนวณ

คอมพิวเตอร์คืออะไร? ปัญหาคืออะไร?

ในโรงเรียนเรามักจะได้รับการสอนแบบจำลองทางจิตของปัญหาและหน้าที่ที่เป็นดังนี้:

ฟังก์ชันคือขั้นตอนที่คุณใช้กับอินพุต x เพื่อค้นหาเอาต์พุต f (x)

ปรากฎว่าไฟล์ นิยามทางคณิตศาสตร์ แตกต่างกัน:

ฟังก์ชันคือชุดของคู่ที่เรียงลำดับซึ่งองค์ประกอบแรกของแต่ละคู่มาจากชุด X (เรียกว่าโดเมน) องค์ประกอบที่สองของแต่ละคู่มาจากชุด Y (เรียกว่าโคโดเมนหรือช่วง) และแต่ละองค์ประกอบของ โดเมนจับคู่กับองค์ประกอบเดียวของช่วง

นั่นค่อนข้างถูกปาก แต่นั่นหมายความว่าอย่างไร?

คำจำกัดความนี้บอกเราว่าคอมพิวเตอร์เป็นเครื่องจักรสำหรับการทำงานของคอมพิวเตอร์

ทำไม?

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

สัญญาเทียบกับเครื่องคิดเลขเงินเดือนถาวร

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

เนื่องจากไม่ใช่ทุกฟังก์ชันที่สามารถอธิบายเป็นอัลกอริทึมได้

กฎของเกม

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

เราจะเรียกอินพุตว่าตัวอักษรของเครื่อง นั่นคือชุดสตริงของอักขระจากเซต จำกัด บางชุด ตัวอย่างเช่นตัวอักษรของเครื่องอาจเป็นเลขฐานสอง (0 และ 1) หรืออาจเป็นชุดอักขระ ASCII ลำดับที่ จำกัด ของอักขระคือสตริงตัวอย่างเช่น“ 0110”

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

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

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

ตัวดำเนินการที่สำคัญตัวหนึ่งคือโอเปอเรเตอร์ Kleene star ที่ใช้กับนิพจน์ทั่วไปด้วย สิ่งนี้สามารถคิดได้ว่าเป็นการรวมพลังที่เป็นไปได้ทั้งหมดของภาษา เช่นถ้าภาษาของเรา ถึง คือชุดของสตริง {‘01’, ‘1’} จากนั้นเป็นหนึ่งในสมาชิกของ ถึง* คือสตริง '0101111'

นับได้

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

ยิ่งไปกว่านั้นหลักฐานของเราอ้างว่าชุดของโปรแกรมที่เป็นไปได้นั้นนับไม่ถ้วนในขณะที่ชุดของภาษาบนตัวอักษรนั้นไม่มีที่สิ้นสุดอย่างนับไม่ได้

ในตอนนี้คุณอาจกำลังคิดว่า“ Infinity เป็นความคิดที่แปลกประหลาดพอสมควร ตอนนี้ฉันต้องจัดการกับพวกมันสองคน!”

ก็ไม่ได้แย่ขนาดนั้น เซตที่นับไม่ถ้วนเป็นเซตที่สามารถแจกแจงได้ เป็นไปได้ที่จะกล่าวว่านี่คือองค์ประกอบแรกนี่คือองค์ประกอบที่สองและอื่น ๆ ในที่สุดก็กำหนดตัวเลขให้กับทุกองค์ประกอบของชุด ยกตัวอย่างชุดของเลขคู่ เราสามารถพูดได้ว่า 2 คืออันแรก 4 ตัวที่สอง 6 ตัวที่สามและอื่น ๆ ชุดดังกล่าวนับเป็นอนันต์หรือนับได้

แม้ว่าบางชุดเช่นตัวเลขจริงไม่สำคัญว่าคุณจะฉลาดแค่ไหน ไม่มีการแจงนับ ชุดเหล่านี้คือ ไม่มีที่สิ้นสุดนับไม่ถ้วน หรือนับไม่ได้

โปรแกรมมากมายนับไม่ถ้วน

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

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

ตัวอย่างหลักการออกแบบ

เพื่อย้ำ:

ชุดของสตริงทั้งหมดบนตัวอักษรใด ๆ (เช่นชุดโปรแกรมคอมพิวเตอร์ทั้งหมด) สามารถนับได้

หลายภาษานับไม่ถ้วน

จากข้อสรุปนี้แล้วส่วนย่อยของสตริงเหล่านี้ล่ะ? ถามอีกอย่างชุดภาษาทั้งหมดล่ะ ปรากฎว่าชุดนี้นับไม่ได้

ชุดของภาษาทั้งหมดบนตัวอักษรใด ๆ นั้นนับไม่ได้

อีกครั้งเราไม่ครอบคลุม หลักฐาน ที่นี่.

ผลที่ตามมา

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

ทำไม?

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

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

นี่คือประเด็นที่ลึกซึ้ง:

เนื่องจากชุดของโปรแกรมที่ถูกต้องทั้งหมดสามารถนับได้ แต่ชุดของฟังก์ชันไม่ได้จึงต้องมีฟังก์ชันบางอย่างที่เราไม่สามารถเขียนโปรแกรมได้

วิธีคำนวนราคาออปชั่นจากราคาหุ้น

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

ตอนนี้คำถามกลายเป็นว่า“ ปัญหาเหล่านี้มีลักษณะอย่างไร” ก่อนที่เราจะอธิบายปัญหาดังกล่าวต่อไปเราต้องสร้างโมเดลการคำนวณก่อนโดยทั่วไป

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

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

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

• สัญลักษณ์ปัจจุบันใต้หัวและ

• สถานะภายในของเครื่องซึ่งได้รับการอัปเดตเมื่อมีการเขียนสัญลักษณ์

แค่นั้นแหละ.

ความเป็นสากล

ในปี 1926 Alan Turing ไม่เพียง แต่พัฒนาเครื่องทัวริงเท่านั้น แต่ยังมีข้อมูลเชิงลึกที่สำคัญอื่น ๆ อีกมากมายเกี่ยวกับธรรมชาติของการคำนวณเมื่อเขาเขียนบทความที่มีชื่อเสียงของเขาเรื่อง“ On Computable Numbers” เขาตระหนักว่าโปรแกรมคอมพิวเตอร์นั้นถือได้ว่าเป็นข้อมูลเข้าสู่คอมพิวเตอร์ ด้วยมุมมองนี้เขามีความคิดที่สวยงามว่าเครื่องทัวริงสามารถจำลองหรือดำเนินการป้อนข้อมูลนั้นได้

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

วิทยานิพนธ์ของคริสตจักร - ทัวริง

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

ทุกสิ่งที่คำนวณได้นั้นสามารถคำนวณได้ด้วยเครื่องทัวริง

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

ความสามารถในการรับรู้และความสามารถในการตัดสินใจ

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

ภาษาจะจดจำได้หากมีเครื่องทัวริงที่จำได้

และ

ภาษาสามารถตัดสินใจได้หากมีเครื่องทัวริงที่ตัดสินใจได้

ในการเป็นผู้จดจำภาษาเครื่องทัวริงต้องยอมรับทุกสายอักขระในภาษาและต้องไม่ยอมรับสิ่งที่ไม่ใช่ภาษานั้น มันอาจปฏิเสธหรือวนซ้ำสตริงดังกล่าว ในการเป็นผู้ตัดสินใจเครื่องทัวริงต้องหยุดการป้อนข้อมูลเสมอไม่ว่าจะด้วยการยอมรับหรือปฏิเสธ

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

ไม่สามารถตัดสินใจได้

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

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

เราสามารถพิสูจน์สิ่งนี้ได้โดยใช้เครื่องทัวริง เครื่องทัวริงสามารถอธิบายได้ว่าเป็นสตริงดังนั้นจึงมีจำนวนที่นับได้ สมมติว่าม_{หนึ่ง}, ม₂และอื่น ๆ ประกอบเป็นชุดของเครื่องทัวริงทั้งหมด ให้เรากำหนดฟังก์ชันต่อไปนี้:

f (i, j) = 1 ถ้า M_ผมยอมรับญ>, 0 มิฉะนั้น

นี่คือไวยากรณ์สำหรับ 'การเข้ารหัสสตริงของ M' และฟังก์ชันนี้แสดงถึงปัญหาของการส่งออก 1 ถ้า M_ผมหยุดด้วยการยอมรับม_ญเป็นอินพุตและเอาต์พุต 0 มิฉะนั้น สังเกตว่า M_ผมต้องหยุด (เช่นเป็นผู้ตัดสินใจ) สิ่งนี้จำเป็นเนื่องจากเราต้องการอธิบายถึงฟังก์ชันที่ไม่สามารถตัดสินใจได้ (นั่นคือปัญหาที่ไม่สามารถแก้ไขได้)

ตอนนี้ให้เรากำหนดภาษาด้วย ล ที่ประกอบด้วยการเข้ารหัสสตริงของเครื่องทัวริงที่ไม่ยอมรับคำอธิบายของตนเอง:

L = M ไม่ยอมรับ

เช่นบางเครื่อง M_{หนึ่ง}อาจส่งออก 0 บนอินพุตหนึ่ง> ในขณะที่เครื่องอื่น M₂อาจส่งออก 1 บนอินพุต2>. เพื่อพิสูจน์ว่าภาษานี้ไม่สามารถระบุได้เราถามว่า M คืออะไร_ลเครื่องที่กำหนดภาษา L จะทำเมื่อได้รับคำอธิบายของตัวเองล> เป็นอินพุต มีความเป็นไปได้สองประการ:

ม_ลยอมรับล>

หรือ

ม_ลปฏิเสธล>

ถ้าม_ลยอมรับการเข้ารหัสของตัวเองนั่นหมายความว่าล> ไม่ได้อยู่ในภาษา L; อย่างไรก็ตามหากเป็นเช่นนั้น M_ลไม่ควรยอมรับการเข้ารหัสตั้งแต่แรก ในทางกลับกันถ้าม_ลไม่ยอมรับการเข้ารหัสของตัวเองแล้วล> อยู่ในภาษา L ดังนั้น M_ลควรยอมรับการเข้ารหัสสตริง

ในทั้งสองกรณีเรามีความขัดแย้งหรือในแง่ทางคณิตศาสตร์ความขัดแย้งที่พิสูจน์ได้ว่าภาษา L นั้นไม่สามารถตัดสินใจได้ ดังนั้นเราจึงได้อธิบายปัญหาที่แก้ไขไม่ได้แรกของเรา

การหยุดปัญหา

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

ภาษาของการเข้ารหัสของเครื่องทัวริงที่หยุดสตริงว่าง

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

วิธีใช้บูตสแตรปใน html

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

สรุป

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

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

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

ความซับซ้อน

ช้ากับเร็ว

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

ตัวอย่างเช่นสมมติว่าคุณมีหน้าที่รับผิดชอบในการพัฒนาอัลกอริทึมสำหรับบริการหาคู่ออนไลน์และมีคนตั้งคำถามว่า“ ทุกคนหาคู่เดทได้ไหม” คำตอบคือการจับคู่บุคคลที่เข้ากันได้เพื่อให้ทุกคนจับคู่กัน ปรากฎว่ามีอัลกอริทึมที่มีประสิทธิภาพในการแก้ปัญหานี้ ปัญหานี้อยู่ในชุด ป .

node.js ใช้ทำอะไร

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

คำจำกัดความที่เป็นทางการ

ป คือชุดของปัญหาที่แก้ไขได้ในเวลาพหุนาม นั่นคือจำนวนขั้นตอนการคำนวณถูกล้อมรอบด้วยฟังก์ชันพหุนามที่เกี่ยวข้องกับขนาดของปัญหา เราทราบดีว่าข้อความ“ ทุกคนสามารถออกเดทได้ไหม” คำถามหรือที่เรียกว่า ปัญหาการจับคู่สองฝ่าย , อยู่ใน ป .

ตัวอย่างเช่น คือชุดของปัญหาที่ตรวจสอบได้ในเวลาพหุนาม ซึ่งรวมถึงทุกปัญหาใน P แน่นอน; อย่างไรก็ตามเราไม่รู้ว่าการกักกันนี้เข้มงวดหรือไม่ เราทราบดีถึงปัญหาที่สามารถตรวจสอบได้อย่างมีประสิทธิภาพ แต่ไม่สามารถแก้ไขได้อย่างมีประสิทธิภาพ แต่เราไม่รู้ว่าปัญหานั้นว่ายากจริงหรือไม่ ปัญหากลุ่มเป็นปัญหาดังกล่าว เราทราบดีว่าสามารถตรวจสอบวิธีแก้ปัญหาได้อย่างมีประสิทธิภาพ แต่เราไม่ทราบแน่ชัดว่าจะแก้ปัญหาได้อย่างมีประสิทธิภาพหรือไม่

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

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

รายละเอียดปลีกย่อยที่สามารถเคลื่อนที่ได้

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

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

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

เราสามารถเป็นคนละเอียดอ่อนได้ แทนที่จะถามเส้นทางที่สั้นที่สุด (P) เราสามารถขอเส้นทางที่ยาวที่สุดโดยไม่มีรอบได้ ปรากฎว่าปัญหาเส้นทางที่ยาวที่สุดนั้นเป็น NP-complete

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

สรุป

ในการตรวจสอบความซับซ้อนนี้เราได้กำหนดระดับของปัญหา P และ NP P แสดงถึงปัญหาที่คอมพิวเตอร์สามารถแก้ไขได้อย่างมีประสิทธิภาพในขณะที่ NP แสดงถึงปัญหาที่ตรวจสอบได้อย่างมีประสิทธิภาพ

ยังไม่มีใครพิสูจน์ได้ว่า P ไม่เท่ากับ NP ปัญหาทั้งสองชั้นนี้เทียบเท่ากันหรือไม่หรือที่เรียกว่าปัญหา P เทียบกับ NP และเป็นปัญหาเปิดที่สำคัญที่สุดในวิทยาการคอมพิวเตอร์เชิงทฤษฎีในปัจจุบันหากไม่ได้อยู่ในคณิตศาสตร์ทั้งหมด ในความเป็นจริงในปี 2000 สถาบัน Clay Math ได้ตั้งชื่อปัญหา P vs. NP เป็นหนึ่งในคำถามเปิดที่สำคัญที่สุดเจ็ดข้อในวิชาคณิตศาสตร์และได้เสนอเงินรางวัลมูลค่าหนึ่งล้านดอลลาร์เพื่อเป็นหลักฐานที่กำหนดวิธีแก้ปัญหานี้

สรุป

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

• มีบางสิ่งที่ไม่สามารถคำนวณได้เช่นปัญหาการหยุดชะงัก

• มีบางสิ่งที่ไม่สามารถคำนวณได้อย่างมีประสิทธิภาพเช่นปัญหาใน NPC

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

ทำความเข้าใจพื้นฐาน

มีปัญหาด้านการคำนวณที่ไม่มีทางแก้ไขหรือไม่?

เนื่องจากชุดของโปรแกรมที่ถูกต้องทั้งหมดสามารถนับได้ แต่ชุดของฟังก์ชันไม่ได้จึงต้องมีฟังก์ชันบางอย่างที่เราไม่สามารถเขียนโปรแกรมได้

วิทยานิพนธ์ของศาสนจักร - ทัวริงคืออะไร?

วิทยานิพนธ์ของศาสนจักร - ทัวริงกล่าวว่าทุกสิ่งที่คำนวณได้นั้นสามารถคำนวณได้ด้วยเครื่องทัวริง

ปัญหา P กับ NP คืออะไร?

เป็นปัญหาในการยืนยันว่าปัญหาการคำนวณทุกปัญหาที่สามารถตรวจสอบวิธีแก้ปัญหาในเวลาพหุนามสามารถแก้ไขได้ในเวลาพหุนามหรือไม่