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

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

ล่าถอย. อันที่จริงไม่ต้องบอกว่าเครื่องทัวริงทำงานยังไง อย่างที่บอก หาง่ายมาก ดังนั้นเราจะถือว่าคุณรู้อยู่แล้วว่ามันทำงานอย่างไร

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

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

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

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

• 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 - ขั้นตอนที่) ระบุว่ากำลังดูเซลล์ไหนในขั้นตอนนี้ และรถอยู่ในสภาพใด? เฉพาะการกำหนดค่าที่จำกัดเท่านั้นที่สมเหตุสมผล กล่าวคือ เซลล์ที่เซลล์ทั้งหมดของเทปว่างเปล่า ยกเว้นจำนวนจำกัด ที่เป็นไปได้ การกำหนดค่าจะถือเป็นที่สิ้นสุดหากสถานะเครื่องอยู่ในขั้นสุดท้าย

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

เราจะบอกว่าคำที่ไม่ว่างเปล่า 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" วัตถุประสงค์ของกลไกนี้คือทำหน้าที่เป็นทั้งวิธีการเข้าและออกและเป็นหน่วยความจำในการทำงานสำหรับเก็บผลลัพธ์ของขั้นตอนการคำนวณระดับกลาง สิ่งที่อุปกรณ์ประกอบด้วย แต่ละเครื่องดังกล่าวประกอบด้วยสององค์ประกอบ: เทปไม่จำกัด เป็นอนันต์ในทั้งสองทิศทางและแบ่งออกเป็นเซลล์ ตัวเครื่องเป็นโปรแกรมควบคุม หัวสแกนสำหรับอ่านและเขียนข้อมูล สามารถอยู่ในสถานะใดสถานะหนึ่งในช่วงเวลาใดก็ได้

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

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

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

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

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

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

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

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

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

ตารางกระโดด.

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

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

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

เรามักจะแก้ปัญหาที่มีความซับซ้อนต่างกันไป เช่น ในชีวิตประจำวัน คณิตศาสตร์ ฯลฯ บางอย่างก็ง่ายที่จะแก้ บางอย่างต้องใช้ความคิดอย่างมาก และสำหรับบางคนเราก็หาทางออกไม่เจอ

ในกรณีทั่วไป วิธีการแก้ปัญหา (ถ้ามี) สามารถอธิบายได้โดยใช้การกระทำเบื้องต้นจำนวนจำกัด

ตัวอย่างเช่น การแก้สมการกำลังสอง:

1. แปลงสมการเป็นรูปแบบบัญญัติ \(a x^2 + b x + c = 0\)
2. ถ้า \(a=0\) แล้วนี่ สมการเชิงเส้นด้วยวิธีแก้ปัญหา \(x=\frac(-c)(b)\) แก้ไขปัญหา. มิฉะนั้น ไปที่ขั้นตอนที่ 3
3. คำนวณการเลือกปฏิบัติ \(D=b^2-4 a c\)
4. คำนวณสมการแก้สมการ \(x_(1,2) = \frac(-b\pm\sqrt(D))(2 a)\). แก้ไขปัญหา.

เราสามารถแนะนำแนวคิดเชิงสัญชาตญาณของอัลกอริทึมดังต่อไปนี้:

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

แน่นอนว่านี่ไม่ใช่คำจำกัดความที่เข้มงวด แต่อธิบายสาระสำคัญของแนวคิดของอัลกอริทึม

อัลกอริธึมถูกรวบรวมตามเฉพาะ นักแสดงและจึงต้องเป็นภาษาที่ผู้แสดงสามารถเข้าใจได้

ผู้ดำเนินการอัลกอริทึมอาจเป็นบุคคล หรืออาจเป็นคอมพิวเตอร์ หรือหุ่นยนต์อื่นๆ เช่น เครื่องทอผ้า

คุณสมบัติของอัลกอริทึมต่อไปนี้มีความโดดเด่น:

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

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

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

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

นอกจากนี้ ชุดของการกระทำที่เป็นไปได้ของผู้ดำเนินการก็ถูกจำกัดเช่นกัน เนื่องจากหากการกระทำใด ๆ ที่อนุญาตได้ ก็จะต้อง "ไม่ยอมรับ" ด้วยเช่นกัน

คำจำกัดความที่เข้มงวดของอัลกอริทึม

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

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

ในยุค 20-30 ของศตวรรษที่ XX นักคณิตศาสตร์หลายคนทำงานเกี่ยวกับปัญหาของคำจำกัดความที่เข้มงวดของอัลกอริทึม โดยเฉพาะ Alan Turing, Emil Leon Post, Andrey Andreevich Markov, Andrey Nikolaevich Kolmogorov, Alonzo Church และอื่น ๆ ในที่สุดงานของพวกเขาก็นำไปสู่การเกิดขึ้นและการพัฒนาของทฤษฎีอัลกอริธึม ทฤษฎีความสามารถในการคำนวณ และแนวทางต่างๆ ของแคลคูลัส และอีกอย่างคือการเขียนโปรแกรมโดยทั่วไป หนึ่งในผลงานของพวกเขาคือการเกิดขึ้นของคำจำกัดความที่เข้มงวดหลายประการของอัลกอริธึมซึ่งนำมาใช้ในรูปแบบต่างๆ แต่เท่าเทียมกัน

เราจะพูดถึงคำจำกัดความของทัวริงอย่างละเอียด และอ่านคำจำกัดความที่เทียบเท่ากันของโพสต์ โบสถ์ และมาร์กอฟ

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

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

อลันทัวริง (2455-2497)

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

ใช้เป็นอินพุตของเครื่องทัวริง คำ, เรียบเรียงด้วยบ้าง ตัวอักษร, นั่นคือ ชุด สัญลักษณ์.

ผลลัพธ์ของเครื่องทัวริงก็เป็นคำพูดเช่นกัน

คำที่ใช้อัลกอริทึมเรียกว่า ป้อนข้อมูล. คำพูดที่เกิดจากการทำงาน สุดสัปดาห์.

ชุดคำที่ใช้อัลกอริทึมเรียกว่า ขอบเขตของอัลกอริทึม.

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

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

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

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

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

แม้ว่าเครื่องจักรทัวริงจะเป็นแนวคิดที่เป็นนามธรรม แต่ก็ง่ายพอที่จะจินตนาการถึงเครื่องจักรดังกล่าว (แม้ว่าจะมีเทปจำกัด) และยังมีเครื่องจักรสาธิตเช่นนี้อีกด้วย:

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

ในทางกลับกัน คำสั่งอาจมีโครงสร้างดังต่อไปนี้:

\[ a_k \left\lbrace \begin(matrix) L \\ N \\ R \end(matrix)\right\rbrace q_m \]

อย่างแรกคือตัวอักษรของตัวอักษรซึ่งควรจะเขียนไปยังเซลล์ปัจจุบัน \(a_k\) จากนั้นการเคลื่อนที่ของหุ่นยนต์ไปทางซ้าย (L) ขวา (R) หรือไม่มีที่ไหนเลย (อยู่ในตำแหน่ง N) คือ ระบุไว้ ในตอนท้ายจะมีการระบุสถานะใหม่ซึ่งหุ่นยนต์ \(q_m\) ควรไป

เซลล์ตารางถูกกำหนดอย่างชัดเจนโดยอักขระปัจจุบัน \(a_i\) และสถานะปัจจุบันของหุ่นยนต์ \(q_j\)

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

ตัวอย่าง

เราจะเขียนอัลกอริธึมสำหรับเครื่องทัวริงที่จะเพิ่มคำที่ป้อนเข้าไป ซึ่งก็คือ เลขทศนิยม, 1.

จากนั้นอธิบายอัลกอริทึมสามารถกำหนดได้ดังนี้:

1. เลื่อนไปทางขวาหาจุดเริ่มต้นของคำป้อน
2. เลื่อนไปทางขวาหาจุดสิ้นสุดของคำป้อน
3. เพิ่มหนึ่งบิตปัจจุบันของคำที่ป้อน หากมีตัวเลขตั้งแต่ 0 ถึง 8 ให้ออก มิฉะนั้น ให้เขียน 0 เลื่อนไปทางซ้าย แล้วกลับไปที่ขั้นตอนที่ 3

เราเขียนอัลกอริทึมนี้ในรูปแบบของตาราง ตัวอักษรประกอบด้วยตัวเลขตั้งแต่ 0 ถึง 9 และ "อักขระว่าง" \(\Lambda\) นอกจากนี้เรายังต้องการ 4 สถานะของหุ่นยนต์ นับสถานะหยุด ซึ่งสอดคล้องกับขั้นตอนของคำอธิบายอัลกอริทึม

เรายอมรับว่าสถานะเริ่มต้น \(1\) คือการค้นหาจุดเริ่มต้นของคำที่ป้อน \(2\) คือการค้นหาจุดสิ้นสุดของคำที่ป้อน \(3\) คือการเพิ่ม 1

\(_(q_j)\แบ็กสแลช^(a_i)\)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛP1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛL3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

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

	1	9	9
1

ในสถานะ 1 หุ่นยนต์จะอยู่เหนือเซลล์ว่าง คำสั่งที่เกี่ยวข้องจากตาราง "ΛP1" กล่าวคือปล่อยเซลล์ว่างไว้ เลื่อนไปทางขวาและอยู่ในสถานะ 1:

	1	9	9
	1

ตอนนี้หุ่นยนต์สังเกตค่า "1" คำสั่งที่เกี่ยวข้องคือ "1H2" นั่นคือปล่อยให้ "1" อยู่ในเซลล์ ห้ามขยับ และไปที่สถานะ "2":

	1	9	9
	2

ในสถานะ "2" เครื่องจะสังเกตค่า "1" คำสั่งที่เกี่ยวข้องคือ "1P2" นั่นคือปล่อยให้ "1" เลื่อนไปทางขวาและอยู่ในสถานะ "2":

สถานการณ์ซ้ำ:

ตอนนี้ในสถานะ 3 และสังเกตสัญลักษณ์ "9" หุ่นยนต์ดำเนินการคำสั่ง "0L3":

	1	9	0
		3

สถานการณ์ซ้ำ:

สถานะ “0” – สถานะหยุด อัลกอริทึมเสร็จสมบูรณ์แล้ว

คำอธิบายอย่างเป็นทางการ

ในทางคณิตศาสตร์ เครื่องจักรทัวริงสามารถอธิบายได้ดังนี้:

เครื่องทัวริง (MT)

มันเป็นระบบของรูปแบบ \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), ที่ไหน

• \(A\) เป็นชุดสัญลักษณ์ของอักษร MT
• \(a_0 \in A\) – อักขระว่างของตัวอักษร
• \(Q\) – ชุดจำกัดของสถานะ MT
• \(q_1 \in Q\) – สถานะเริ่มต้นของ MT
• \(q_0 \in Q\) – สถานะสุดท้ายของ MT (สถานะหยุด)
• \(T = \(L, P, H\)\) คือชุดของกะของ MT
• \(\tau\) – โปรแกรม MT นั่นคือฟังก์ชันที่กำหนดแผนที่ \(\tau: A\times Q\backslash \(q_0\) \rightarrow A\times T \times Q\)

กุญแจสำคัญในทฤษฎีอัลกอริทึมคือ วิทยานิพนธ์ของทัวริง.

กล่าวอย่างหลวม ๆ วิทยานิพนธ์ของทัวริงระบุไว้ดังนี้:

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

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

คำจำกัดความของอัลกอริทึมสำรอง

นอกเหนือจากเครื่องจักรทัวริงแล้ว ยังมีคำจำกัดความอิสระอีกหลายคำที่เทียบเท่ากับคำจำกัดความของทัวริง

โดยเฉพาะอย่างยิ่ง คำจำกัดความผ่านเครื่อง Post ผ่านแคลคูลัสแลมบ์ดาของคริสตจักร ซึ่งเป็นอัลกอริธึม Markov ปกติ

ลองพิจารณาวิธีการเหล่านี้

เครื่องโพสต์

หนึ่งปีหลังจาก Turing นักคณิตศาสตร์ชาวอเมริกัน Emil Leon Post ได้เสนอคอมพิวเตอร์สากลที่เป็นนามธรรมอีกเครื่องหนึ่งซึ่งค่อนข้างทำให้ทัวริงง่ายขึ้น

เครื่อง Post ทำงานด้วยตัวอักษรสองหลัก และสถานะภายในของหุ่นยนต์จะถูกแทนที่ด้วย ไลน์โปรแกรม.

มิฉะนั้น เครื่อง Post จะคล้ายกับเครื่องทัวริง: มีหุ่นยนต์ และมีเทปอนันต์พร้อมเซลล์

เครื่อง Post สามารถรันคำสั่งต่อไปนี้:

1. เขียน 1 ไปที่บรรทัดที่ i ของโปรแกรม
2. เขียน 0 ไปที่บรรทัดที่ i ของโปรแกรม
3. เลื่อนไปทางซ้าย ไปที่บรรทัดที่ i- ของโปรแกรม
4. เลื่อนไปทางขวา ไปที่บรรทัดที่ i- ของโปรแกรม
5. สาขาตามเงื่อนไข: หากเซลล์ที่สังเกตพบเป็น 0 ให้ไปที่บรรทัดที่ i ของโปรแกรม มิฉะนั้น ให้ไปที่บรรทัดที่ j ของโปรแกรม
6. หยุด.

เครื่อง Post ยังมีคำสั่งที่ต้องห้ามหลายประการ:

1. เขียนไปที่เซลล์ 1 เมื่อมี 1 อยู่แล้ว
2. เขียนไปที่เซลล์ 0 เมื่อมี 0 อยู่แล้ว

เหตุการณ์ดังกล่าวทำให้เกิดความผิดพลาด

สัญกรณ์ต่อไปนี้สามารถใช้เขียนโปรแกรมสำหรับเครื่องโพสต์ได้:

1. ∨ ฉัน - เขียน 1 ไปที่บรรทัดที่ i ของโปรแกรม
2. × ผม – เขียน 0 ไปที่บรรทัดที่ i ของโปรแกรม
3. ← i - เลื่อนไปทางซ้าย ไปที่บรรทัด i-th ของโปรแกรม
4. → i - เลื่อนไปทางขวา, ไปที่บรรทัดที่ i- ของโปรแกรม
5. ? ผม; เจ- กระโดดแบบมีเงื่อนไข: หากมี 0 ในเซลล์ที่สังเกต ให้ไปที่บรรทัดที่ i ของโปรแกรม มิฉะนั้น ให้ไปที่บรรทัดที่ j ของโปรแกรม
6. ! - หยุด.

ตัวอย่างโปรแกรม:

1. → 2 2. ? หนึ่ง; 3 3. × 4 4. ← 5 5. !

โปรแกรมนี้จะลบป้ายกำกับแรก (1) ทางด้านขวาของตำแหน่งเริ่มต้นของหุ่นยนต์และหยุดหุ่นยนต์ในเซลล์ทางด้านซ้าย

โดยทั่วไปแล้วเครื่อง Post เป็นผู้เบิกทาง จำเป็นภาษาโปรแกรมเช่น C, Fortran เป็นต้น

เครื่อง Post เทียบเท่ากับเครื่องทัวริง กล่าวอีกนัยหนึ่ง สำหรับโปรแกรมเครื่องทัวริงใดๆ คุณสามารถเขียนโปรแกรม Post machine ที่เทียบเท่าได้ และในทางกลับกัน

ผลที่สำคัญประการหนึ่งของความเท่าเทียมกันนี้คือ ตัวอักษรใด ๆ สามารถลดลงเป็นรหัสไบนารี่.

คล้ายกับวิทยานิพนธ์ของทัวริง นอกจากนี้ยังมีวิทยานิพนธ์ของ Post ด้วย

วิทยานิพนธ์ของโพสต์ ทุกอัลกอริทึมสามารถแสดงเป็นเครื่องโพสต์ได้

อัลกอริธึม Markov ปกติ

อัลกอริธึม Markov ปกติออกแบบมาเพื่อใช้กับคำในตัวอักษรต่างๆ

คำจำกัดความของอัลกอริธึมปกติประกอบด้วยสองส่วน:

1. ตัวอักษรอัลกอริทึม
2. โครงการอัลกอริทึม

อัลกอริทึมนั้นถูกนำไปใช้กับ คำ, นั่นคือ ลำดับของตัวอักษร ตัวอักษร.

โครงร่างของอัลกอริธึมปกติคือชุดของสิ่งที่เรียกว่า สูตรทดแทนซึ่งแต่ละอย่างสามารถ เรียบง่ายหรือ สุดท้าย. สูตรการแทนที่อย่างง่ายคือนิพจน์ของรูปแบบ \(L\to D\) โดยที่ \(L\) และ \(D\) เป็นคำสองคำโดยพลการที่ประกอบด้วยตัวอักษรของอัลกอริทึม (เรียกว่า ส่วนซ้ายและขวาตามลำดับ ของสูตรการทดแทน) ในทำนองเดียวกัน สูตรการแทนที่ขั้นสุดท้ายคือนิพจน์ของรูปแบบ \(L\to\cdot D\) โดยที่ \(L\) และ \(D\) เป็นคำสองคำที่ประกอบขึ้นจากตัวอักษรของอัลกอริทึม

สันนิษฐานว่าอักขระเสริม \(\to\) และ \(\to\cdot\) ไม่ได้อยู่ในตัวอักษรของอัลกอริทึม

กระบวนการของการใช้อัลกอริทึมปกติกับคำใด ๆ \(V\) คือลำดับของการกระทำดังต่อไปนี้:

1. ให้ \(V"\) เป็นคำที่ได้รับในขั้นตอนก่อนหน้าของอัลกอริทึม (หรือคำดั้งเดิมหากขั้นตอนปัจจุบันเป็นขั้นตอนแรก)
2. หากไม่มีสูตรทดแทนใด ๆ ส่วนด้านซ้ายจะรวมอยู่ใน \(V"\) แสดงว่าการทำงานของอัลกอริทึมเสร็จสมบูรณ์และคำว่า \(V"\) ถือเป็นผลลัพธ์ของ งานนี้.
3. มิฉะนั้น ในบรรดาสูตรการทดแทน ส่วนด้านซ้ายซึ่งรวมอยู่ใน \(V"\) ส่วนแรกจะถูกเลือก
4. จากการแสดงคำที่เป็นไปได้ทั้งหมด \(V"\) ในรูปแบบ \(RLS\) (โดยที่ \(R\) เป็นคำนำหน้าและ \(L\) เป็นคำต่อท้าย) มีการเลือกคำหนึ่งเพื่อให้ \(R \) สั้นที่สุด , หลังจากที่ดำเนินการแทน \(V"=RDS\)
5. หากสูตรการทดแทนมีจำกัด อัลกอริทึมจะสิ้นสุดด้วยผลลัพธ์ \(V"\) มิฉะนั้น ให้ไปที่ขั้นตอนที่ 1 (ขั้นตอนถัดไป)

อัลกอริธึมปกติใดๆ เทียบเท่ากับเครื่องทัวริงบางเครื่อง และในทางกลับกัน เครื่องทัวริงใดๆ ก็เทียบเท่ากับอัลกอริธึมปกติบางเครื่อง

อะนาล็อกของวิทยานิพนธ์ของทัวริงสำหรับอัลกอริธึมปกติมักเรียกว่า หลักการทำให้เป็นมาตรฐาน.

ตัวอย่าง

อัลกอริธึมนี้แปลงเลขฐานสองเป็นเลข "เดี่ยว" (ซึ่งบันทึกของจำนวนเต็มที่ไม่เป็นลบ N คือสตริงของไม้ N) ตัวอย่างเช่น เลขฐานสอง 101 ถูกแปลงเป็น 5 แท่ง: |||||

ตัวอักษร: ( 0, 1, | ) กฎ:

1. 1 → 0|
2. |0 → 0||
3. 0 → (สตริงว่าง)

บรรทัดที่มา: 101 การดำเนินการ:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

ฟังก์ชันแบบเรียกซ้ำ

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

• ฟังก์ชันเรียกซ้ำดั้งเดิม
• ฟังก์ชันเรียกซ้ำทั่วไป
• ฟังก์ชันเรียกซ้ำบางส่วน

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

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

ฟังก์ชันเรียกซ้ำดั้งเดิม

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

คุณสมบัติพื้นฐาน ได้แก่ :

• ฟังก์ชัน null \(O()=0\) เป็นฟังก์ชันที่ไม่มีอาร์กิวเมนต์ที่ส่งคืน \(0\) เสมอ
• ฟังก์ชันต่อเนื่อง \(S(x)=x+1\) เป็นฟังก์ชันที่กำหนดจำนวนธรรมชาติใด ๆ \(x\) หมายเลขถัดไป\(x+1\)
• ฟังก์ชั่น \(I_n^m(x_1,\ldots,x_n) = x_m\), โดยที่ \(0

ในการสร้างส่วนที่เหลือของฟังก์ชันคลาส ใช้ตัวดำเนินการต่อไปนี้:

• การทดแทน สำหรับฟังก์ชัน \(f\) ของตัวแปร \(m\) และ \(m\) ฟังก์ชัน \(g_1,\ldots,g_m\) ของ \(n\) ตัวแปรแต่ละตัว ผลลัพธ์ของการแทนที่ \(g_k\) เข้า \( f\) เป็นฟังก์ชัน \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)จากตัวแปร \(n\)
• การเรียกซ้ำดั้งเดิม ให้ \(f(x_1,\ldots,x_n)\) เป็นฟังก์ชันของตัวแปร \(n\) และ \(g(x_1,\ldots,x_(n+2))\) เป็นฟังก์ชันของ \( n+ 2\) ตัวแปร จากนั้นผลลัพธ์ของการใช้ตัวดำเนินการเรียกซ้ำดั้งเดิมกับฟังก์ชัน \(f\) และ \(g\) คือฟังก์ชัน \(h\) ของตัวแปร \(n+1\) ของรูปแบบ: \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

ฟังก์ชันเรียกซ้ำบางส่วน

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

ตัวดำเนินการย่อขนาดอาร์กิวเมนต์

ให้ \(f\) เป็นฟังก์ชันของ \(n\) ตัวแปร \(x_i \in \mathbb(N)\) จากนั้นผลลัพธ์ของการใช้ตัวดำเนินการย่อขนาดอาร์กิวเมนต์กับฟังก์ชัน \(f\) คือฟังก์ชัน \(h\) ของอาร์กิวเมนต์ \(n-1\) ซึ่งกำหนดเป็น:

\[ h(x_1,\ldots,x_(n-1)) = \นาที y, \]ที่ไหน \ นั่นคือ \(h\) ส่งคืนค่าต่ำสุดของอาร์กิวเมนต์สุดท้ายของฟังก์ชัน \(f\) ซึ่งค่าของ \(f\) เป็นศูนย์

แม้ว่าฟังก์ชันแบบเรียกซ้ำแบบพื้นฐานจะคำนวณได้เสมอ ฟังก์ชันแบบเรียกซ้ำบางส่วนอาจไม่ได้กำหนดไว้สำหรับค่าอาร์กิวเมนต์บางค่า

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

ฟังก์ชันเรียกซ้ำทั่วไป

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

ทฤษฎีการคำนวณและปัญหาการหยุดชะงัก

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

ทฤษฎีการคำนวณเกี่ยวข้องกับการศึกษาปัญหาดังกล่าว

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

ปัญหาการหยุดชะงัก จากคำอธิบายของอัลกอริธึม A และอินพุต \(x\) จำเป็นต้องค้นหาว่าอัลกอริธึม \(A\) หยุดอินพุต \(x\) หรือไม่

ปัญหาการหยุดชะงักนั้นไม่สามารถตัดสินใจได้โดยใช้อัลกอริธึม มาพิสูจน์กัน

\(\เดลต้า\)

ให้มีอัลกอริธึมสากลที่แก้ปัญหาการหยุดชะงัก ให้เราพิจารณาคลาสของอัลกอริธึมที่ประมวลผลข้อความที่อธิบายอัลกอริธึม

เนื่องจากการมีอยู่ของอัลกอริธึมสากลสำหรับการแก้ปัญหาการหยุดชะงัก มีอัลกอริธึมที่กำหนดว่าอัลกอริธึมจากคลาสดังกล่าวจะหยุดด้วยข้อความของตัวเองหรือไม่ ระบุอัลกอริทึมดังกล่าว \(B\)

มาสร้างอัลกอริทึมกันเถอะ \(C\) อินพุตซึ่งเป็นข้อความของอัลกอริทึม \(A\) ซึ่งประมวลผลข้อความของตัวเอง:

1. เรียกใช้อัลกอริทึม \(B\) บน \(A\)
2. หากอัลกอริทึม \(B\) กำหนดว่า \(A\) จะหยุดที่ข้อความ ไปที่ขั้นตอนที่ 1 มิฉะนั้น ไปที่ขั้นตอนที่ 3
3. สิ้นสุดอัลกอริทึม \(C\)

ในการพยายามใช้อัลกอริธึม \(C\) กับอัลกอริธึม \(C\) เราพบข้อขัดแย้งที่ชัดเจน: ถ้า \(C\) หยุดที่ข้อความของตัวเอง มันก็จะหยุดไม่ได้ และในทางกลับกัน ดังนั้นจึงไม่มีอัลกอริธึม \(B\) \(\ไม่ใช่ \เดลต้า\)

สูตรทั่วไปของปัญหาการหยุดชะงักคือปัญหาของการกำหนดอนุพันธ์

ปัญหาการรับรู้อนุพันธ์

ให้กำหนดตัวอักษร บางคำ (สูตร) ​​ของตัวอักษรนี้ และระบบการแปลงอย่างเป็นทางการเหนือคำของตัวอักษรนี้ (เช่น สร้างแคลคูลัสเชิงตรรกะ)

มีอยู่สำหรับคำสองคำใด \(R\) และ \(S\) ห่วงโซ่นิรนัยที่นำจาก \(R\) ถึง \(S\) ภายในแคลคูลัสเชิงตรรกะที่กำหนดหรือไม่

ในปี 1936 โบสถ์อลอนโซได้พิสูจน์ทฤษฎีบทของคริสตจักร

ทฤษฎีบทของคริสตจักร ปัญหาของการจำแนกการอนุมานได้นั้นไม่สามารถแก้ไขได้โดยอัลกอริธึม

คริสตจักรใช้สูตรของแคลคูลัสแลมบ์ดาเพื่อพิสูจน์ ในปีพ.ศ. 2480 ทัวริงได้พิสูจน์ทฤษฎีบทเดียวกันโดยอิสระจากเขาโดยใช้รูปแบบเครื่องทัวริง

เนื่องจากคำจำกัดความทั้งหมดของอัลกอริธึมมีความเท่าเทียมกัน จึงมีระบบแนวคิดที่ไม่เกี่ยวข้องกับคำจำกัดความเฉพาะของอัลกอริธึมและดำเนินการตามแนวคิด ฟังก์ชันคำนวณ.

ฟังก์ชันที่คำนวณได้คือฟังก์ชันที่สามารถประเมินได้โดยอัลกอริทึม

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

ตัวอย่างของฟังก์ชันที่คำนวณไม่ได้

ใช้ฟังก์ชัน \(h(n)\) ที่กำหนดไว้สำหรับ \(\forall n \in \mathbb(N)\) ดังนี้:

\[ h(n) = \begin(cases) 1, & \text(if )\pi\text( มีลำดับของ )n\text( 9th) \\ 0, & \text(otherwise ) \end( กรณี) \]

เราสามารถรับค่า \(1\) สำหรับฟังก์ชันนี้ได้ อย่างไรก็ตาม เพื่อให้ได้ค่า \(0\) เราจำเป็นต้องตรวจสอบการขยายทศนิยมอนันต์ของตัวเลข \(\pi\) ซึ่งเห็นได้ชัดว่าเป็นไปไม่ได้อย่างจำกัด เวลา. ฟังก์ชันนี้จึงไม่สามารถคำนวณได้

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

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

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

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

เครื่องทัวริงได้รับการออกแบบเพื่อกำหนดอย่างเป็นทางการว่าสามารถคำนวณอะไรได้บ้างตามขีดจำกัดความสามารถในการคำนวณ หากเครื่องทัวริงสามารถทำงานได้ แสดงว่างานนั้นสามารถคำนวณได้ทัวริง ทัวริงมุ่งเน้นไปที่การออกแบบเครื่องจักรที่สามารถกำหนดสิ่งที่สามารถคำนวณได้เป็นหลัก ทัวริงสรุปว่าตราบใดที่มีเครื่องทัวริงที่สามารถคำนวณค่าประมาณของตัวเลขได้ ค่านั้นก็สามารถนับได้ นอกจากนี้ เครื่องทัวริงสามารถตีความตัวดำเนินการเชิงตรรกะ เช่น AND, OR, XOR, NOT และ "If-then-Else" เพื่อตรวจสอบว่า