คำจำกัดความของเครื่องทัวริง

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

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

โทร เครื่องทัวริง เป็นอุปกรณ์ทางทฤษฎีที่สามารถประมวลผลข้อมูลตามกฎที่กำหนด

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

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

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

instagram story viewer

กล่าวอีกนัยหนึ่งถ้าปัญหาสามารถแสดงผ่าน a อัลกอริทึม ในการเขียน มันสามารถประมวลผลได้ - อย่างน้อยก็ในระดับทฤษฎี - โดยเครื่องทัวริง

อลัน ทัวริงคิดว่ามันเป็นแบบฝึกหัดเพื่อแสดงให้เห็นว่ามีปัญหาทางคณิตศาสตร์ที่คอมพิวเตอร์ไม่สามารถแก้ไขได้

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

ชุดของกฎยังสามารถเข้าใจเป็นภาษาโปรแกรมได้เนื่องจากต้องมีไวยากรณ์ ตรรกะ และสม่ำเสมอ

เมื่อมองย้อนกลับไป นักคณิตศาสตร์คนอื่นๆ ได้สร้าง Turing Machine รุ่นที่ซับซ้อนยิ่งขึ้น

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

รูปถ่าย: Chrisdorney / Steve Simmons