เครื่องทัวริงคือชุดของวัตถุดังต่อไปนี้

• 1) ตัวอักษรภายนอก A=(a 0 , a 1 , …, a n );
• 2) ตัวอักษรภายใน Q=(q 1 , q 2 ,…, q m ) - ชุดของสถานะ;
• 3) ชุดอักขระควบคุม (P, L, S)
• 4) เทปไม่มีที่สิ้นสุดในทั้งสองทิศทางซึ่งแบ่งออกเป็นเซลล์ซึ่งแต่ละอันสามารถมีอักขระ A ได้เพียงตัวเดียวในเวลาที่ไม่ต่อเนื่อง
• 5) อุปกรณ์ควบคุมที่สามารถอยู่ในสถานะใดสถานะหนึ่งได้

สัญลักษณ์ของเซลล์ว่างคือตัวอักษรของตัวอักษรภายนอก 0 .

ในบรรดาสถานะต่างๆ ค่าเริ่มต้น q 1 นั้นแตกต่างกัน โดยที่เครื่องเริ่มทำงาน และสุดท้าย (หรือสถานะการหยุด) q 0 เมื่อเครื่องหยุดทำงาน

อุปกรณ์ควบคุมสามารถเลื่อนไปทางซ้ายและขวาบนเทป อ่านและเขียนตัวอักษร A ลงในเซลล์เทป อุปกรณ์ควบคุมทำงานตามคำสั่งที่มีรูปแบบดังนี้

q i a j > a p X q k

การบันทึกหมายถึงสิ่งต่อไปนี้: หากอุปกรณ์ควบคุมอยู่ในสถานะ q i และตัวอักษร a j ถูกเขียนในเซลล์ที่ถูกตรวจสอบ (1) a p จะถูกเขียนไปยังเซลล์แทนที่จะเป็น j (2) เครื่องจะดำเนินการตรวจสอบต่อไป เซลล์ขวาจากเซลล์ที่เพิ่งดู ถ้า X=P หรือเพื่อดูเซลล์ซ้ายถัดไป ถ้า X=L หรือดูเซลล์เทปเดียวกันต่อไป ถ้า X=C (3) อุปกรณ์ควบคุมเข้าสู่ รัฐคิวเค

เนื่องจากการทำงานของเครื่อง ตามเงื่อนไข ถูกกำหนดโดยสมบูรณ์โดยสถานะ q ในช่วงเวลาที่กำหนด และโดยเนื้อหา a ของเซลล์ที่กำลังดูในขณะนั้น มีกฎหนึ่งข้อสำหรับแต่ละการกำหนดค่าที่เป็นไปได้ q i a j ไม่มีกฎเกณฑ์เฉพาะสำหรับสถานะสุดท้ายที่เครื่องหยุดทำงาน ดังนั้น โปรแกรมเครื่องทัวริงที่มีตัวอักษรภายนอก A=(a0, a1, …, an) และตัวอักษรภายใน Q=(q1, q2,…, qm) มีคำสั่งไม่เกิน m (n+ 1)

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

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

เราจะบอกว่าคำที่ไม่ว่างเปล่า b ในตัวอักษร A (а 0 ) = (a 1 , ..., a n ) ถูกรับรู้โดยเครื่องในตำแหน่งมาตรฐานหากเขียนในเซลล์ที่ต่อเนื่องกันของเทปทั้งหมด เซลล์อื่นว่างเปล่า และเครื่องจะสแกนเซลล์ด้านซ้ายสุดหรือขวาสุดจากเซลล์ที่เขียนคำว่า b ตำแหน่งมาตรฐานเรียกว่าเริ่มต้น (สุดท้าย) หากเครื่องที่รับรู้คำในตำแหน่งมาตรฐานอยู่ในสถานะเริ่มต้น q 1 (ตามลำดับ ในสถานะหยุด q 0)

หากการประมวลผลของคำ b นำเครื่องทัวริงไปสู่สถานะสุดท้าย กล่าวได้ว่าใช้กับ b มิฉะนั้นจะไม่ใช้กับ b (เครื่องทำงานไม่มีกำหนด)

พิจารณาตัวอย่าง:

รับเครื่องทัวริงที่มีตัวอักษรภายนอก A \u003d (0, 1) (ที่นี่ 0 คือสัญลักษณ์ของเซลล์ว่าง) ตัวอักษรของสถานะภายใน Q \u003d (q 0, q 1, q 2 ) และมีดังต่อไปนี้ แผนภาพการทำงาน (โปรแกรม):

q 1 0 > 1 ลิตร q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 C q 1;

โปรแกรมนี้สามารถเขียนโดยใช้ตาราง

ในขั้นตอนแรก คำสั่งจะทำงาน: q 1 0 > 1 Л q 2 (อุปกรณ์ควบคุมอยู่ในสถานะ q1 และตัวอักษร 0 ถูกเขียนในเซลล์ที่ถูกตรวจสอบ 1 จะถูกเขียนในเซลล์แทนที่จะเป็น 0, ส่วนหัว เลื่อนไปทางซ้าย อุปกรณ์ควบคุมจะเปลี่ยนเป็นสถานะ q2) ในผลลัพธ์ การกำหนดค่าต่อไปนี้จะถูกสร้างขึ้นบนเครื่อง:

สุดท้าย หลังจากรันคำสั่ง q 2 0 > 0 P q 0 การกำหนดค่าจะถูกสร้างขึ้น

การกำหนดค่านี้ถือเป็นที่สิ้นสุดเนื่องจากเครื่องอยู่ในสถานะหยุดทำงาน q 0

ดังนั้นคำดั้งเดิม 110 จึงถูกประมวลผลโดยเครื่องเป็นคำ 101

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

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

เครื่องทัวริงไม่มีอะไรมากไปกว่ากฎบางอย่าง (อัลกอริทึม) สำหรับการแปลงคำของตัวอักษร A Q, i.e. การกำหนดค่า ดังนั้น ในการกำหนดเครื่องทัวริง คุณต้องระบุตัวอักษรภายนอกและภายใน โปรแกรม และระบุว่าสัญลักษณ์ใดแสดงถึงเซลล์ว่างและสถานะสุดท้าย

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

มันคืออะไรและใครเป็นคนสร้างมันขึ้นมา

Alan Turing พยายามอธิบายรูปแบบดั้งเดิมที่สุดของอุปกรณ์กลไกที่มีความสามารถพื้นฐานเหมือนกับคอมพิวเตอร์ ทัวริงอธิบายเครื่องนี้เป็นครั้งแรกในปี 1936 ใน "On Computable Numbers with an Application to the Decidability Problem" ซึ่งปรากฏใน Proceedings of the London Mathematical Society

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

อุปกรณ์ทำมาจากอะไร?

แต่ละเครื่องดังกล่าวประกอบด้วยสององค์ประกอบ:

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

แต่ละเครื่องจะเชื่อมโยงชุดข้อมูลที่มีขอบเขตจำกัดสองชุด: ตัวอักษรของสัญลักษณ์อินพุต A = (a0, a1, ..., am) และตัวอักษรของรัฐ Q = (q0, q1, ..., qp) สถานะ q0 เรียกว่า passive เชื่อกันว่าอุปกรณ์จะสิ้นสุดการทำงานเมื่อถูกกระแทก สถานะ q1 เรียกว่าสถานะเริ่มต้น - เครื่องเริ่มการคำนวณโดยอยู่ที่จุดเริ่มต้น คำป้อนจะถูกวางไว้บนเทปหนึ่งตัวอักษรในแถวในแต่ละตำแหน่ง ทั้งสองด้านเป็นเพียงเซลล์ว่าง

กลไกทำงานอย่างไร

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

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

คุณสมบัติการเคลื่อนไหว

เครื่องทัวริงเช่นเดียวกับระบบคอมพิวเตอร์อื่น ๆ มีคุณสมบัติโดยธรรมชาติและคล้ายกับคุณสมบัติของอัลกอริธึม:

1. ความไม่รอบคอบ เครื่องดิจิตอลจะไปยังขั้นตอนถัดไป n+1 หลังจากเสร็จสิ้นขั้นตอนก่อนหน้าเท่านั้น แต่ละขั้นตอนที่เสร็จสมบูรณ์จะกำหนดว่า n+1 จะเป็นอย่างไร
2. ความชัดเจน อุปกรณ์ดำเนินการเพียงครั้งเดียวสำหรับเซลล์เดียวกัน มันป้อนอักขระจากตัวอักษรและทำให้หนึ่งการเคลื่อนไหว: ซ้ายหรือขวา
3. ความมุ่งมั่น แต่ละตำแหน่งในกลไกจะสอดคล้องกับรูปแบบเฉพาะของรูปแบบที่กำหนด และในแต่ละขั้นตอน การกระทำและลำดับของการดำเนินการจะไม่คลุมเครือ
4. ประสิทธิภาพ. ผลลัพธ์ที่แน่นอนสำหรับแต่ละขั้นตอนจะถูกกำหนดโดยเครื่องทัวริง โปรแกรมดำเนินการอัลกอริทึมและในจำนวนขั้นตอนที่ จำกัด จะผ่านไปยังสถานะ q0
5. ตัวละครจำนวนมาก อุปกรณ์แต่ละตัวถูกกำหนดไว้เหนือคำที่อนุญาตซึ่งรวมอยู่ในตัวอักษร

ฟังก์ชั่นเครื่องทัวริง

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

ซอฟต์แวร์อุปกรณ์

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

ส่วนประกอบสำหรับการคำนวณ

ในการสร้างเครื่องทัวริงเพื่อแก้ปัญหาเฉพาะ จำเป็นต้องกำหนดพารามิเตอร์ต่อไปนี้

ตัวอักษรภายนอก นี่คือชุดสัญลักษณ์จำนวนจำกัด ซึ่งแสดงโดยเครื่องหมาย A องค์ประกอบที่เป็นส่วนประกอบเรียกว่าตัวอักษร หนึ่งในนั้น - a0 - ต้องว่างเปล่า ตัวอย่างเช่น ตัวอักษรของอุปกรณ์ทัวริงที่ทำงานกับเลขฐานสองมีลักษณะดังนี้: A = (0, 1, a0)

ห่วงโซ่ต่อเนื่องของตัวอักษร-สัญลักษณ์ที่บันทึกไว้ในเทปเรียกว่าคำ

หุ่นยนต์เป็นอุปกรณ์ที่ทำงานโดยปราศจากการแทรกแซงของมนุษย์ ในเครื่องจักรทัวริง มีสถานะต่าง ๆ สำหรับการแก้ปัญหา และภายใต้เงื่อนไขบางประการ มันจะย้ายจากตำแหน่งหนึ่งไปยังอีกตำแหน่งหนึ่ง ชุดของสถานะการขนส่งดังกล่าวเป็นตัวอักษรภายใน เขามี การกำหนดตัวอักษรของแบบฟอร์ม Q=(q1, q2...) หนึ่งในตำแหน่งเหล่านี้ - q1 - ต้องเป็นตำแหน่งเริ่มต้น นั่นคือตำแหน่งที่เริ่มโปรแกรม องค์ประกอบที่จำเป็นอีกประการหนึ่งคือสถานะ q0 ซึ่งเป็นสถานะสุดท้าย นั่นคือสถานะที่ยุติโปรแกรมและย้ายอุปกรณ์ไปยังตำแหน่งหยุด

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

อัลกอริทึมสำหรับหุ่นยนต์

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

1. การเขียนอักขระของตัวอักษรภายนอกไปยังตำแหน่ง รวมถึงอักขระว่าง แทนที่องค์ประกอบที่อยู่ในนั้น รวมถึงอักขระว่างด้วย
2. ย้ายเซลล์ขั้นตอนหนึ่งไปทางซ้ายหรือขวา
3. เปลี่ยนสถานะภายในของคุณ

ดังนั้นเมื่อเขียนโปรแกรมสำหรับอักขระหรือตำแหน่งแต่ละคู่ จำเป็นต้องอธิบายพารามิเตอร์สามตัวให้ถูกต้อง: a i - องค์ประกอบจากตัวอักษร A ที่เลือก ทิศทางของการเลื่อนแคร่ตลับหมึก ("←" ไปทางซ้าย "→" ไปที่ ขวา "จุด" - ไม่มีการเคลื่อนไหว) และ q k - สถานะใหม่ของอุปกรณ์ ตัวอย่างเช่นคำสั่ง 1 "←" q 2 มีความหมาย "แทนที่อักขระด้วย 1 ย้ายหัวรถไปทางซ้ายหนึ่งเซลล์ขั้นและข้ามไปยังสถานะ q 2 ".

เครื่องทัวริง: ตัวอย่าง

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

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

ที่นี่ q 1 คือสถานะของการเปลี่ยนตัวเลข q 0 คือจุดหยุด หากใน q 1 automaton แก้ไของค์ประกอบจากแถว 0..8 มันจะแทนที่ด้วยหนึ่งใน 1..9 ตามลำดับ จากนั้นเปลี่ยนเป็นสถานะ q 0 นั่นคืออุปกรณ์หยุดทำงาน หากแคร่หมายเลข 9 ถูกแทนที่ด้วย 0 จากนั้นเลื่อนไปทางซ้ายโดยหยุดในสถานะ q 1 . การเคลื่อนไหวนี้ดำเนินต่อไปจนกว่าอุปกรณ์จะแก้ไขตัวเลขที่น้อยกว่า 9 หากอักขระทั้งหมดมีค่าเท่ากับ 9 จะถูกแทนที่ด้วยศูนย์ 0 จะถูกเขียนแทนองค์ประกอบสูงสุด แคร่ตลับหมึกจะเลื่อนไปทางซ้ายและเขียน 1 ถึง เซลล์ว่าง ขั้นตอนต่อไปคือการเปลี่ยนเป็นสถานะ q 0 - หยุด

ตัวอย่าง 2กำหนดชุดสัญลักษณ์ที่แสดงถึงวงเล็บเปิดและปิด จำเป็นต้องสร้างอุปกรณ์ทัวริงที่จะลบวงเล็บร่วมกันนั่นคือองค์ประกอบที่จัดเรียงเป็นแถว - "()" ตัวอย่างเช่น ข้อมูลเริ่มต้น: “) (() (()” คำตอบควรเป็น: “) . . . ((” วิธีแก้ไข: กลไก อยู่ใน q 1 วิเคราะห์องค์ประกอบซ้ายสุดในสตริง

สถานะ q 1: หากพบสัญลักษณ์ “(” ให้เลื่อนไปทางขวาและไปที่ตำแหน่ง q 2 หากกำหนด “a 0 ” ให้หยุด

สถานะ q 2: วงเล็บ "(" ถูกวิเคราะห์สำหรับการมีอยู่ของการจับคู่ ในกรณีของการจับคู่ ")" ควรได้รับ หากองค์ประกอบเป็นคู่ ให้ขึ้นแคร่ไปทางซ้ายแล้วไปที่ q 3

สถานะ q 3: ก่อนอื่นให้ลบอักขระ “(” แล้วตามด้วย “)” และไปที่ q 1

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

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

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

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

เครื่องทัวริง: คำนิยาม

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

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

ดังนั้น ในการกำหนดเครื่องทัวริง ต้องระบุวัตถุต่อไปนี้:

ตารางกระโดดถูกจัดเรียงดังนี้: สำหรับแต่ละคู่จะมีการระบุสามเท่า ในที่นี้กะคือหนึ่งในตัวเลข -1 (ซ้าย), 0 (ในตำแหน่ง) และ 1 (ขวา) ดังนั้น ตารางการเปลี่ยนแปลงจึงเป็นฟังก์ชันของประเภท S x A -> S x A x (-1,0,1) ที่กำหนดไว้ในคู่ที่สถานะยังไม่สิ้นสุด

มันยังคงอธิบายพฤติกรรมของเครื่องทัวริง ทุกขณะย่อมมีบ้าง การกำหนดค่าซึ่งประกอบด้วยเนื้อหาของเทป (พูดอย่างเป็นทางการ เนื้อหาของเทปคือการแมปตามอำเภอใจ Z -> A ) ตำแหน่งปัจจุบันของส่วนหัว (จำนวนเต็มบางส่วน ) และสถานะปัจจุบันของเครื่อง (องค์ประกอบ S ) การเปลี่ยนแปลงของการกำหนดค่าเป็นแบบถัดไปเกิดขึ้นตามกฎธรรมชาติ: เราดูในตารางว่าต้องทำอะไรสำหรับสถานะที่กำหนดและสำหรับสัญลักษณ์ที่กำหนด นั่นคือ เราค้นหาสถานะใหม่ของเครื่องจักร เปลี่ยน สัญลักษณ์ตามที่ระบุแล้วเลื่อนหัวไปทางซ้าย ขวา หรือปล่อยไว้กับที่ ในกรณีนี้ หากสถานะใหม่เป็นหนึ่งในสถานะสุดท้าย การทำงานของเครื่องจะสิ้นสุดลง ยังคงต้องตกลงกันว่าเราส่งข้อมูลไปยังอินพุตของเครื่องอย่างไรและสิ่งใดที่ถือว่าเป็นผลงาน เราจะถือว่าตัวอักษรของเครื่อง นอกเหนือจากช่องว่างแล้ว ยังมีอักขระ 0 และ 1 (และอาจรวมถึงอักขระอื่นๆ ด้วย) อินพุตและเอาต์พุตของเครื่องจะเป็นลำดับที่จำกัดของศูนย์และหนึ่ง (คำไบนารี) คำที่ป้อนจะถูกเขียนบนเทปเปล่า วางหัวเครื่องไว้ในเซลล์แรก เครื่องจะเริ่มต้นและเริ่มทำงาน หากเครื่องหยุดทำงาน ผลลัพธ์จะเป็นคำไบนารีที่สามารถอ่านได้จากตำแหน่งส่วนหัวและเลื่อนไปทางขวา (จนกว่าอักขระอื่นที่ไม่ใช่ 0 และ 1 จะปรากฏขึ้น)

ดังนั้นเครื่องทัวริงใด ๆ จะกำหนดฟังก์ชันบางส่วนในคำไบนารี เป็นเรื่องปกติที่จะเรียกฟังก์ชันดังกล่าวทั้งหมด คำนวณได้ด้วยเครื่องจักรทัวริง.

เครื่องจักรทัวริง: การสนทนา

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

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

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

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

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

77 . แสดงว่าฟังก์ชันย้อนกลับซึ่งพลิกคำย้อนกลับสามารถคำนวณได้บนเครื่องทัวริง

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

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

เครื่องจำลองการศึกษานักแสดงสากล

มันคืออะไร?

เครื่องจำลองทัวริงคือรูปแบบการฝึกอบรมของตัวดำเนินการสากล (คอมพิวเตอร์นามธรรม) ที่เสนอในปี 1936 โดย A. Turing เพื่อชี้แจงแนวคิดของอัลกอริทึม ตามวิทยานิพนธ์ของทัวริง อัลกอริธึมใดๆ สามารถเขียนเป็นโปรแกรมสำหรับเครื่องทัวริงได้ ได้รับการพิสูจน์แล้วว่าเครื่องทัวริงมีความสามารถเทียบเท่าเครื่อง Post และอัลกอริธึม Markov ปกติ

เครื่องทัวริงประกอบด้วยแคร่ (หัวอ่านและเขียน) และเทปที่ไม่มีที่สิ้นสุดแบ่งออกเป็นเซลล์ แต่ละเซลล์ของเทปสามารถมีอักขระจากตัวอักษรบางตัว A=(a 0 ,a 1 ,…,a N ) ตัวอักษรใด ๆ มีสัญลักษณ์ช่องว่างซึ่งแสดงเป็น 0 หรือ Λ เมื่อป้อนคำสั่ง ช่องว่างจะถูกแทนที่ด้วยขีดล่าง "_"

เครื่องทัวริงเป็นหุ่นยนต์ที่ควบคุมโดยโต๊ะ แถวในตารางสอดคล้องกับสัญลักษณ์ของตัวอักษร A ที่เลือก และคอลัมน์จะสอดคล้องกับสถานะของหุ่นยนต์ Q=(q 0 ,q 1 ,…,q M ) เมื่อเริ่มต้นการทำงาน เครื่องทัวริงอยู่ในสถานะ q 1 . สถานะ q 0 เป็นสถานะสุดท้าย: เมื่อเข้าไปแล้ว หุ่นยนต์จะหยุดการทำงาน

ในแต่ละเซลล์ของตารางที่สอดคล้องกับสัญลักษณ์บางตัว i และบางสถานะ q j มีคำสั่งที่ประกอบด้วยสามส่วน:

1. อักขระจากตัวอักษร A ;
2. ย้ายทิศทาง: > (ขวา),
3. สภาพเครื่องใหม่

ข่าว

1. ฟาลิน่า ไอ.เอ็น.หัวข้อ "Turing Machine" ในหลักสูตรวิทยาการคอมพิวเตอร์ของโรงเรียน (inf.1september.ru)
2. เมเยอร์ อาร์.วี.เครื่องโพสต์และทัวริง (komp-model.narod.ru)
3. Pilshchikov V.N. , Abramov V.G. , Vylitok A.A. , Hot I.V.เครื่องทัวริงและอัลกอริธึม Markov การแก้ปัญหา, มอสโก: มหาวิทยาลัยแห่งรัฐมอสโก, 2549.
4. เบ็คแมน ไอ.เอ็น.วิทยาศาสตร์คอมพิวเตอร์. การบรรยาย 7. อัลกอริทึม (profbeckman.narod.ru)
5. Solovyov A.คณิตศาสตร์แบบไม่ต่อเนื่องโดยไม่มีสูตร (lib.rus.ec)
6. Ershov S.S.องค์ประกอบของทฤษฎีอัลกอริทึม, Chelyabinsk, Publishing Center of SUSU, 2009
7. Varpakhovsky F.L.องค์ประกอบของทฤษฎีอัลกอริทึม, M: การตรัสรู้, 1970.
8. Vereshchagin N.K. , Shen A.ฟังก์ชันที่คำนวณได้, M: MTsNMO, 1999

จะทำอย่างไรกับมัน?

ที่ด้านบนของโปรแกรมจะมีช่องแก้ไขซึ่งคุณสามารถป้อนเงื่อนไขของปัญหาในรูปแบบอิสระได้

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

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

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

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

เมื่อป้อนคำสั่งในเซลล์ตาราง คุณต้องป้อน . ก่อน ตัวละครใหม่จากนั้นทิศทางของการเปลี่ยนแปลงและหมายเลขสถานะ หากละอักขระ อักขระนั้นจะไม่เปลี่ยนแปลงตามค่าเริ่มต้น หากละเว้นหมายเลขสถานะ สถานะของหุ่นยนต์จะไม่เปลี่ยนแปลงตามค่าเริ่มต้น

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

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

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

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

ความต้องการทางด้านเทคนิค

โปรแกรมทำงานภายใต้ระบบปฏิบัติการของสาย Windowsบนคอมพิวเตอร์สมัยใหม่

ใบอนุญาต

โปรแกรมฟรีสำหรับการใช้งานที่ไม่ใช่เชิงพาณิชย์ ไม่ได้แจกจ่ายซอร์สโค้ดของโปรแกรม

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

เมื่อวางโปรแกรมลงบนเว็บไซต์อื่น จำเป็นต้องมีลิงก์ไปยังแหล่งที่มา

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

การดาวน์โหลดเอกสารหมายความว่าคุณยอมรับเงื่อนไขของข้อตกลงสิทธิ์การใช้งานนี้

ดาวน์โหลด

หลังจากคลายไฟล์เก็บถาวร โปรแกรมจะอยู่ในสภาพใช้งานได้และไม่ต้องติดตั้งเพิ่มเติมใดๆ

1. คำอธิบายของเครื่องทัวริง 3

1.1 คุณสมบัติของเครื่องทัวริงเป็นอัลกอริธึม 5

2. ความซับซ้อนของอัลกอริทึม 7

2.1 ความซับซ้อนของปัญหา.. 9

3. เครื่องทัวริงและปัญหาที่แก้ไม่ได้ด้วยอัลกอริธึม.. 12

บทสรุป. 16

อ้างอิง.. 18

บทนำ

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

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

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

1. คำอธิบายของเครื่องทัวริง

ยุคก่อนประวัติศาสตร์ของการสร้างงานนี้เกี่ยวข้องกับการกำหนดปัญหาทางคณิตศาสตร์ที่ยังไม่ได้แก้ไขโดย David Hilbert ที่การประชุม International Congress of Mathematicians ในกรุงปารีสในปี 1900 หนึ่งในนั้นคือปัญหาในการพิสูจน์ความสอดคล้องของระบบสัจพจน์ของเลขคณิตธรรมดา ซึ่งต่อมาฮิลเบิร์ตระบุว่าเป็น "ปัญหาการตัดสินใจ" - การค้นหา วิธีทั่วไปเพื่อกำหนดความเป็นไปได้ของคำสั่งที่กำหนดในภาษาของตรรกะที่เป็นทางการ

บทความของทัวริงให้คำตอบสำหรับปัญหานี้ ปัญหาที่สองของฮิลเบิร์ตกลับกลายเป็นว่าแก้ไม่ได้ แต่ความสำคัญของกระดาษของทัวริงไปไกลกว่าปัญหาที่เขียนขึ้น

นี่คือคำอธิบายของงานนี้โดย John Hopcroft: “การทำงานกับปัญหาของ Hilbert ทัวริงต้องให้คำจำกัดความที่ชัดเจนของแนวคิดของวิธีการนั้น ๆ เริ่มต้นจากแนวคิดที่ใช้งานง่ายของวิธีการเป็นอัลกอริทึมชนิดหนึ่งเช่น กระบวนการที่สามารถทำได้ด้วยกลไกโดยปราศจากการแทรกแซงเชิงสร้างสรรค์ เขาแสดงให้เห็นว่าแนวคิดนี้สามารถรวมเป็นหนึ่งในรูปแบบของแบบจำลองโดยละเอียดของกระบวนการคำนวณได้อย่างไร แบบจำลองที่ได้ของการคำนวณซึ่งแต่ละอัลกอริทึมถูกแบ่งออกเป็นลำดับง่ายๆ ขั้นตอนเบื้องต้นเป็นโครงสร้างที่สมเหตุสมผลซึ่งต่อมาเรียกว่าเครื่องทัวริง "

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

ตามหลักแล้ว เครื่องทัวริงสามารถอธิบายได้ดังนี้ ให้:

ชุดสถานะที่แน่นอน - Q ซึ่งเครื่องทัวริงสามารถเป็นได้

ชุดสัญลักษณ์เทป จำกัด - Г;

ฟังก์ชัน δ (ฟังก์ชันหรือโปรแกรมการเปลี่ยนภาพ) ซึ่งกำหนดโดยการจับคู่จากผลิตภัณฑ์คาร์ทีเซียน Q x Г (เครื่องอยู่ในสถานะ qi และสำรวจสัญลักษณ์ gi) เป็นสามเท่าของผลิตภัณฑ์คาร์ทีเซียน Q x Г x (L , R) (เครื่องเข้าสู่สถานะ Qi แทนที่อักขระ gi ด้วยอักขระ gj และเคลื่อนที่ไปทางซ้ายหรือขวาหนึ่งอักขระในเทป) – Q x G -> Q x G x (L,R)

หนึ่งอักขระจาก G-->e (ว่าง);

เซตย่อย Σ є Г - -> ถูกกำหนดให้เป็นเซตย่อยของสัญลักษณ์อินพุตของเทป และ e є (Г - Σ);

หนึ่งในสถานะ - q0 є Q คือสถานะเริ่มต้นของเครื่อง

ปัญหาที่ต้องแก้ไขนั้นถูกกำหนดโดยการเขียนสัญลักษณ์จำนวนจำกัดจากชุด Σ є Г - Si є Σ ลงบนเทป:

eS1S2S3S4... ... ...Sne

หลังจากนั้นเครื่องจะถูกส่งไปยังสถานะเริ่มต้นและส่วนหัวจะถูกตั้งค่าไว้ที่สัญลักษณ์ไม่ว่างด้านซ้ายสุด (q0,w) – หลังจากนั้นตามฟังก์ชันการเปลี่ยนแปลงที่ระบุ (qi,Si) - -> (qj, Sk, L หรือ R) เครื่องจะเริ่มเปลี่ยนอักขระที่ต้องการดู เลื่อนส่วนหัวไปทางขวาหรือซ้าย และเปลี่ยนไปเป็นสถานะอื่นๆ ที่กำหนดโดยฟังก์ชันการเปลี่ยน

เครื่องจะหยุดทำงานหากไม่มีการกำหนดฟังก์ชันการเปลี่ยนแปลงสำหรับคู่เงิน (qi,Si)

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

1.1 คุณสมบัติของเครื่องทัวริงเป็นอัลกอริธึม

ในตัวอย่างของเครื่องทัวริง คุณสมบัติของอัลกอริธึมได้รับการติดตามอย่างดี ขอให้นักเรียนแสดงว่าเครื่องทัวริงมีคุณสมบัติทั้งหมดของอัลกอริธึม

ความไม่รอบคอบ เครื่องทัวริงสามารถไปที่ขั้นตอนที่ (k + 1) - หลังจากดำเนินการแต่ละขั้นตอนแล้วเท่านั้น เนื่องจากเป็นแต่ละขั้นตอนที่กำหนดว่าขั้นตอนที่ (k + 1) - จะเป็นอย่างไร

ความชัดเจน ในแต่ละขั้นตอน สัญลักษณ์จากตัวอักษรจะถูกเขียนลงในเซลล์ หุ่นยนต์จะทำการเคลื่อนไหวหนึ่งครั้ง (L, P, N) และเครื่องทัวริงจะเข้าสู่สถานะใดสถานะหนึ่งที่อธิบายไว้

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

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

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

2. ความซับซ้อนของอัลกอริทึม

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

โดยปกติ ความซับซ้อนในการคำนวณของอัลกอริธึมจะแสดงโดยใช้สัญกรณ์ "บิ๊กโอ" กล่าวคือ อธิบายโดยลำดับความสำคัญของความซับซ้อนในการคำนวณ นี่เป็นเพียงระยะเวลาของการขยายความซับซ้อนที่เติบโตเร็วที่สุดด้วย n คำที่ต่ำกว่าทั้งหมดจะถูกละเว้น ตัวอย่างเช่น หากความซับซ้อนของเวลาของอัลกอริทึมที่กำหนดคือ 4n2+7n+12 ความซับซ้อนในการคำนวณจะอยู่ในลำดับของ n2 เขียนเป็น O(n2)

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

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

โดยปกติ อัลกอริทึมจะถูกจัดประเภทตามเวลาหรือความซับซ้อนของพื้นที่ อัลกอริทึมเรียกว่าค่าคงที่หากความซับซ้อนไม่ขึ้นอยู่กับ n: 0(1) อัลกอริธึมเป็นแบบเส้นตรงถ้าความซับซ้อนของเวลาเป็น O(n) อัลกอริทึมสามารถเป็นกำลังสอง ลูกบาศก์ ฯลฯ อัลกอริธึมทั้งหมดนี้เป็นพหุนาม ความซับซ้อนคือ O(m) โดยที่ m เป็นค่าคงที่ อัลกอริธึมที่มีความซับซ้อนเวลาพหุนามเรียกว่าอัลกอริธึมเวลาพหุนาม

อัลกอริทึมที่มีความซับซ้อนเท่ากับ O(tf(n)) โดยที่ t เป็นค่าคงที่ที่มากกว่า 1 และ f(n) คือฟังก์ชันพหุนามบางตัวของ n เรียกว่าเลขชี้กำลัง เซตย่อยของอัลกอริธึมเลขชี้กำลังที่ความซับซ้อนคือ O(cf(n)) โดยที่ c เป็นค่าคงที่และ f(n) โตเร็วกว่าค่าคงที่แต่ช้ากว่าฟังก์ชันเชิงเส้น เรียกว่า superpolynomial

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