คุณสมบัติของเครื่องทัวริงเป็นอัลกอริทึม ความคิดคือสิ่งสำคัญ: อลัน ทัวริงเป็น "เครื่องคิดเลขสากล" รุ่นเครื่องทัวริง

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

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

พิจารณาการทำงานของเครื่องทัวริง

เครื่องทัวริงเป็นเทปไม่มีที่สิ้นสุดที่แบ่งออกเป็นเซลล์และแคร่ (อุปกรณ์อ่านและพิมพ์) ที่เคลื่อนที่ไปตามเทป

ดังนั้น ทัวริงแมชชีนจึงได้รับการอธิบายอย่างเป็นทางการด้วยชุดตัวอักษรสองตัว:

A=(a1, a2, a3, …, an) - ตัวอักษรภายนอก ใช้ในการบันทึกข้อมูลต้นฉบับ

Q=(q1, q2, q3,…, qm) - ตัวอักษรภายใน อธิบายชุดสถานะของอุปกรณ์การพิมพ์การอ่าน

แต่ละเซลล์ของเทปสามารถมีอักขระจากตัวอักษรภายนอก A = (a0,a1,…,an) (ในกรณีของเรา A=(0, 1))

การดำเนินการที่อนุญาตของเครื่องทัวริงคือ:

1) เขียนสัญลักษณ์ของตัวอักษรภายนอกใด ๆ ลงในเซลล์ของเทป (สัญลักษณ์ที่มีอยู่ก่อนหน้านี้จะถูกเขียนทับ)

2) ย้ายไปยังเซลล์ที่อยู่ติดกัน

3) เปลี่ยนสถานะเป็นหนึ่งในสถานะที่ระบุด้วยสัญลักษณ์ตัวอักษรภายใน Q

เครื่องทัวริงเป็นหุ่นยนต์ที่ควบคุมโดยโต๊ะ

แถวในตารางสอดคล้องกับสัญลักษณ์ของตัวอักษร A ที่เลือก และคอลัมน์สอดคล้องกับสถานะของเครื่อง Q = (q0,q1,…,qm) เมื่อเริ่มต้นการทำงาน เครื่องทัวริงอยู่ในสถานะ q1 สถานะ q0 เป็นสถานะสุดท้าย เมื่ออยู่ในนั้น เครื่องจะหยุดการทำงาน

ในแต่ละเซลล์ของตารางที่สอดคล้องกับสัญลักษณ์ ai และสถานะ qj บางอัน จะมีคำสั่งที่ประกอบด้วยสามส่วน
· ตัวอักษรจากตัวอักษร A
· ทิศทางการเคลื่อนไหว: ">" (ขวา), "<» (влево) или «.» (на месте)
· สถานะใหม่ของตัวเครื่อง

ในตารางด้านบน ตัวอักษรคือ A =(0, 1, _) (ประกอบด้วยอักขระ 3 ตัว) และตัวอักษรภายในคือ Q=(q1, q2, q3, q4, q0), q0 คือสถานะที่ทำให้ขึ้นบรรทัดใหม่ หยุด.

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

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

ตอนนี้เรามากำหนดสถานะการขนส่งกันดีกว่า ฉันเรียกพวกเขาว่า "รถม้าปรารถนาที่จะทำอะไรบางอย่าง"

q1) แคร่ควรไปทางขวา: ถ้าเห็น 0 มันจะเปลี่ยนเป็น 1 และยังคงอยู่ในสถานะ q1 หากเห็น 1 มันจะเปลี่ยนเป็น 0 และยังคงอยู่ในสถานะ q1 ถ้าเห็น _ มัน ย้อนกลับไป 1 เซลล์ “ต้องการอย่างอื่น” เช่น เข้าสู่สถานะ q2 มาเขียนเหตุผลของเราลงในตารางของนักแสดงกันดีกว่า สำหรับไวยากรณ์ โปรดดูวิธีใช้โปรแกรม)

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

คุณสามารถรับชมการทำงานของโปรแกรมได้ในวิดีโอ:

ปัญหาที่ 2 ให้ไว้: ลำดับจำกัดของ 0 และ 1 (001101011101) จำเป็นต้องเขียนออกมาหลังจากลำดับนี้ผ่านเซลล์ว่างและในลำดับนี้ให้แทนที่ด้วย 0 ตัวอย่างเช่น

จาก 001101011101 เราได้รับ 000000000000 1111111

อย่างที่คุณเห็นมีเจ็ดอันถูกเขียนขึ้นหลังจากลำดับนี้และมีศูนย์อยู่ในตำแหน่งของพวกเขา

มาเริ่มการสนทนากันดีกว่า เรามาพิจารณาว่าความต้องการการขนส่งระบุใดและจำนวนเท่าใด

q1) เห็น 1 - แก้ไขให้เป็นศูนย์และไปที่สถานะอื่น q2 (มีการแนะนำสถานะใหม่เพื่อให้แคร่ไม่เปลี่ยนสถานะทั้งหมดเป็นศูนย์ในการผ่านครั้งเดียว)

q2) ไม่ต้องเปลี่ยนแปลงอะไรเลย ให้ย้ายไปที่จุดสิ้นสุดของลำดับ

q3) ทันทีที่แคร่เห็นเซลล์ว่าง มันจะก้าวไปทางขวาแล้ววาดเลข 1 ถ้าเห็นเลข 1 มันจะเคลื่อนที่ต่อไปเพื่อลงนามสัญลักษณ์ที่ส่วนท้าย ทันทีที่ฉันวาดหน่วยได้ เราก็ไปที่สถานะ q4

q4) เราอ่านหน่วยที่เป็นลายลักษณ์อักษรโดยไม่มีการเปลี่ยนแปลงอะไรเลย ทันทีที่เราไปถึงเซลล์ว่างที่แยกลำดับออกจากเซลล์ เราจะย้ายไปยังสถานะใหม่ q5

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

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

เราได้รับโปรแกรมดังต่อไปนี้:

คุณสามารถรับชมการทำงานของ Turing Machine ได้ในวิดีโอด้านล่าง

เชื่อกันว่าใครได้ยืมแนวคิดนี้มาจาก Emil Post ในปี 1936 แม้จะมีคำจำกัดความอย่างเป็นทางการที่ค่อนข้างซับซ้อน แต่แนวคิดนี้ก็เรียบง่ายในหลักการ เพื่อทำความเข้าใจ เรามาลองดูหน้าต่างๆ ของ Wikipedia กันดีกว่า

ก่อนอื่น เราไปที่หน้าเว็บ ซึ่งจริงๆ แล้วเรียกว่า: "เครื่องจักรทัวริง"

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

เครื่องทัวริง (MT)- นามธรรมทางคณิตศาสตร์ที่แสดงถึงเครื่องคอมพิวเตอร์ทั่วไป มันถูกเสนอโดย Alan Turing ในปี 2010 เพื่อกำหนดแนวคิดของอัลกอริทึมอย่างเป็นทางการ

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

เครื่องจักรทัวริงมีอนันต์ในทั้งสองทิศทาง ริบบิ้น, แบ่งออกเป็นเซลล์ และ อุปกรณ์ควบคุมด้วยจำนวนรัฐอันจำกัด

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

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

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

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

1. ในการผลิตโปรตีนในเซลล์โดยใช้เอนไซม์ที่ซับซ้อน - RNA polymerase - ข้อมูลจะถูกอ่านจาก DNA ซึ่งเป็นเทปข้อมูลของเครื่องจักรทัวริง อย่างไรก็ตาม ที่นี่เซลล์ของเทปไม่ได้ถูกเขียนใหม่ มิฉะนั้นกระบวนการจะคล้ายกันมาก: RNA polymerase ตั้งอยู่บน DNA และเคลื่อนที่ไปในทิศทางเดียวในขณะที่มันสังเคราะห์เส้นใยของ RNA ซึ่งเป็นกรดนิวคลีอิกที่คล้ายกับ DNA เมื่อแยกอาร์เอ็นเอออกจากเอนไซม์แล้ว อาร์เอ็นเอที่เสร็จแล้วจะส่งข้อมูลไปยังออร์แกเนลล์ของเซลล์ซึ่งเป็นแหล่งผลิตโปรตีน

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

การเปรียบเทียบนี้ไม่ใช่เรื่องใหม่ และใน Wikipedia ก็อธิบายไว้ในบทความ "คอมพิวเตอร์โมเลกุล" ด้วย:

คอมพิวเตอร์โมเลกุล

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

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

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

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

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

เครื่องของรัฐ

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

ด้วยคำจำกัดความแต่ละข้อ เราได้ก้าวเข้าสู่ขอบเขตของคณิตศาสตร์บริสุทธิ์มากขึ้นเรื่อยๆ ภาษามีความเข้มงวดมากขึ้น มีคำจำกัดความที่เป็นทางการปรากฏขึ้น ซึ่งประกอบด้วยสัญลักษณ์ทางคณิตศาสตร์ หากเราก้าวต่อไป เราจะมาถึงทฤษฎีอัลกอริธึมและทฤษฎีความสามารถในการคำนวณ คุณสามารถเดินทางผ่านหน้าต่างๆ ของ Wikipedia ได้เป็นเวลานาน แต่จะดีกว่าถ้าตุนน้ำและอาหารไว้เผื่อในกรณีที่คุณเดินเข้าไปในทะเลทรายแห่งสัจพจน์และคำจำกัดความ หรืออย่างน้อยก็ลิงก์ที่เชื่อถือได้ไปยังหนังสือเรียนคณิตศาสตร์ เช่น http:/ /www.mccme.ru/free-books/ หรือบทความจากนิตยสาร Potential ;)

ฉันหวังว่าคำอธิบายนี้จะทำให้คุณชัดเจนขึ้นเล็กน้อยว่าเครื่องจักรทัวริงคืออะไร

ย้อนกลับไปสู่ประวัติศาสตร์ของคำนี้กัน

ดังที่เราได้กล่าวไปแล้ว อลัน ทัวริงได้เล่าให้โลกฟังเกี่ยวกับเครื่องจักรของเขาในปี 1937 ในสิ่งที่เรียกว่าวิทยานิพนธ์เชิร์ช-ทัวริง บทความ “Alan Turing” จะบอกเราเกี่ยวกับ Alan Turing แฮกเกอร์และผู้บุกเบิกด้านวิทยาการคอมพิวเตอร์คนแรก ตามที่เขียนไว้บนแผ่นจารึกในโรงแรมที่เขาเกิด เราจะไม่ให้เนื้อหาทั้งหมดของบทความที่นี่ แต่ตัวมันเองไม่ได้มีรายละเอียดมากนัก

อลัน ทัวริง

ทัวริง, อลัน แมทธีสัน(23 มิถุนายน พ.ศ. 2455 - 7 มิถุนายน พ.ศ. 2497) - นักคณิตศาสตร์ นักตรรกวิทยา นักวิทยาการเข้ารหัสลับชาวอังกฤษ ผู้ประดิษฐ์เครื่องทัวริง

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

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

การทดสอบทัวริง

การทดสอบทัวริง- การทดสอบที่เสนอโดย Alan Turing ในปี 1950 ในบทความ “เครื่องจักรคอมพิวเตอร์และความฉลาด” เพื่อทดสอบว่าคอมพิวเตอร์มีความฉลาดในความหมายของมนุษย์หรือไม่

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

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

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

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

ทัวริงทำนายว่าในที่สุดคอมพิวเตอร์จะผ่านการทดสอบของเขา เขาเชื่อว่าภายในปี 2000 คอมพิวเตอร์ที่มีหน่วยความจำ 1 พันล้านบิต (ประมาณ 119 MB) จะสามารถหลอกผู้ตัดสินได้ 30% ในการทดสอบ 5 นาที คำทำนายนี้ไม่เป็นจริง (จริงอยู่ที่การแข่งขัน Loebner ครั้งแรก โปรแกรมคอมพิวเตอร์ "PC Therapist" บน IBM PC 386 สามารถทำให้กรรมการ 5 ใน 10 คนเข้าใจผิดได้ แต่ผลลัพธ์ไม่ได้รับการรับรอง และในปี 1994 การแข่งขันก็ยากขึ้น) ทัวริง ยังคาดการณ์ด้วยว่าการผสมผสาน "เครื่องคิด" จะไม่ถือเป็นความขัดแย้ง และการฝึกอบรมคอมพิวเตอร์จะมีบทบาทสำคัญในการสร้างคอมพิวเตอร์ที่ทรงพลัง (ซึ่งนักวิจัยสมัยใหม่ส่วนใหญ่เห็นด้วย)

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

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

โปรแกรม A.L.I.C.E แสดงผลลัพธ์ที่ดีที่สุดในการทดสอบทัวริง ชนะการทดสอบ 3 ครั้ง (ในปี 2543, 2544 และ 2547)

ลิงค์

• ทัวริง A. M. เครื่องจักรคอมพิวเตอร์และความฉลาด // ใน: Hofstader D., Dennett D. ดวงตาแห่งจิตใจ - ซามารา: Bakhrakh-M, 2003. - หน้า 47-59.
• หนังสือเป็นภาษาอังกฤษ: โรเจอร์ เพนโรส “The Emperor’s New Mind”
• บทความโดยอลัน ทัวริง:
  • อลัน ทัวริง “เครื่องจักรคอมพิวเตอร์และความฉลาด” มายด์ เล่ม 1 ลิกซ์ ไม่ใช่ 236 ตุลาคม 1950 หน้า 433-460.
  • ออนไลน์:
• บทความโดย G. Oppy และ D. Dowe เกี่ยวกับการทดสอบทัวริงจากสารานุกรมปรัชญาสแตนฟอร์ด (เป็นภาษาอังกฤษ)
• "การทดสอบทัวริง: 50 ปีต่อมา" ทบทวนการทำงาน 50 ปีในการทดสอบทัวริงจากมุมมองของปี 2000

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

ตัดตอนมาจากบทความ Wikipedia "อลัน ทัวริง"

ฟังก์ชันที่คำนวณได้โดยสัญชาตญาณใดๆ ก็สามารถคำนวณได้เพียงบางส่วนหรือเทียบเท่ากับที่คำนวณได้ด้วยเครื่องทัวริงบางเครื่อง

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

ในบทความชื่อ “The Church-Turing Thesis” พวกเขาเขียนเกี่ยวกับเขาดังนี้:

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

วิทยานิพนธ์ของคริสตจักรทัวริง- ข้อความพื้นฐานสำหรับวิทยาศาสตร์หลายแขนง เช่น ทฤษฎีความสามารถในการคำนวณ วิทยาการคอมพิวเตอร์ ไซเบอร์เนติกส์เชิงทฤษฎี ฯลฯ คำกล่าวนี้จัดทำโดย Alonzo Church และ Alan Turing ในช่วงกลางทศวรรษ 1930

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

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

วิทยานิพนธ์ฟิสิกส์ของคริสตจักรทัวริงอ่าน: ฟังก์ชันใดๆ ที่สามารถคำนวณโดยอุปกรณ์ฟิสิคัลสามารถคำนวณโดยเครื่องทัวริงได้.

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

เครื่องทัวริงสากล

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

คำนิยามที่เป็นทางการ

โปรแกรมของเครื่องทัวริงที่กำหนดสามารถเขียนได้โดยใช้ตัวอักษรจำกัดบางตัวซึ่งประกอบด้วยสัญลักษณ์สถานะ วงเล็บ ลูกศร ฯลฯ ลองแสดงว่าตัวอักษรของเครื่องนี้เป็น Σ 1 (\displaystyle \Sigma _(1))- จากนั้นเครื่องทัวริงสากล คุณสำหรับคลาสตัวอักษรของรถยนต์ Σ 2 (\displaystyle \Sigma _(2))และ เคเทปอินพุตเรียกว่าเครื่องทัวริงด้วย เค+1เทปทางเข้าและตัวอักษร Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1)\cup \Sigma _(2))เช่นว่าถ้าสมัครครั้งแรก เคบันทึกค่าอินพุต และเปิด เค+1เป็นโค้ดที่เขียนถูกต้องของเครื่องทัวริงบางเครื่องแล้ว คุณจะสร้างคำตอบเดียวกันกับที่จะสร้างด้วยข้อมูลอินพุตนี้ ม 1 (\รูปแบบการแสดงผล M_(1))หรือจะทำงานได้อย่างไม่มีกำหนดหาก ม 1 (\รูปแบบการแสดงผล M_(1))จะไม่หยุดอยู่กับข้อมูลเหล่านี้

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

การใช้งานซอฟต์แวร์ในภาษาการเขียนโปรแกรม Delphi นั้นค่อนข้างง่าย หนึ่งในการใช้งานเหล่านี้สามารถพบได้บนเว็บไซต์ http://kleron.ucoz.ru/load/24-1-0-52 สามารถดาวน์โหลดและบันทึกเป็นไฟล์ Excel ได้

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

เครื่องทัวริงความน่าจะเป็น

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

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

นอกจากนี้ยังมีคำจำกัดความอื่น:

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

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

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

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

พิจารณาการทำงานของเครื่องทัวริง

เครื่องทัวริงเป็นเทปไม่มีที่สิ้นสุดที่แบ่งออกเป็นเซลล์และแคร่ (อุปกรณ์อ่านและพิมพ์) ที่เคลื่อนที่ไปตามเทป

ดังนั้น ทัวริงแมชชีนจึงได้รับการอธิบายอย่างเป็นทางการด้วยชุดตัวอักษรสองตัว:

A=(a1, a2, a3, …, an) - ตัวอักษรภายนอก ใช้ในการบันทึกข้อมูลต้นฉบับ

Q=(q1, q2, q3,…, qm) - ตัวอักษรภายใน อธิบายชุดสถานะของอุปกรณ์การพิมพ์การอ่าน

แต่ละเซลล์ของเทปสามารถมีอักขระจากตัวอักษรภายนอก A = (a0,a1,…,an) (ในกรณีของเรา A=(0, 1))

การดำเนินการที่อนุญาตของเครื่องทัวริงคือ:

1) เขียนสัญลักษณ์ของตัวอักษรภายนอกใด ๆ ลงในเซลล์ของเทป (สัญลักษณ์ที่มีอยู่ก่อนหน้านี้จะถูกเขียนทับ)

2) ย้ายไปยังเซลล์ที่อยู่ติดกัน

3) เปลี่ยนสถานะเป็นหนึ่งในสถานะที่ระบุด้วยสัญลักษณ์ตัวอักษรภายใน Q

เครื่องทัวริงเป็นหุ่นยนต์ที่ควบคุมโดยโต๊ะ

แถวในตารางสอดคล้องกับสัญลักษณ์ของตัวอักษร A ที่เลือก และคอลัมน์สอดคล้องกับสถานะของเครื่อง Q = (q0,q1,…,qm) เมื่อเริ่มต้นการทำงาน เครื่องทัวริงอยู่ในสถานะ q1 สถานะ q0 เป็นสถานะสุดท้าย เมื่ออยู่ในนั้น เครื่องจะหยุดการทำงาน

ในแต่ละเซลล์ของตารางที่สอดคล้องกับสัญลักษณ์ ai และสถานะ qj บางอัน จะมีคำสั่งที่ประกอบด้วยสามส่วน
· ตัวอักษรจากตัวอักษร A
· ทิศทางการเคลื่อนไหว: ">" (ขวา), "<» (влево) или «.» (на месте)
· สถานะใหม่ของตัวเครื่อง

ในตารางด้านบน ตัวอักษรคือ A =(0, 1, _) (ประกอบด้วยอักขระ 3 ตัว) และตัวอักษรภายในคือ Q=(q1, q2, q3, q4, q0), q0 คือสถานะที่ทำให้ขึ้นบรรทัดใหม่ หยุด.

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

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

ตอนนี้เรามากำหนดสถานะการขนส่งกันดีกว่า ฉันเรียกพวกเขาว่า "รถม้าปรารถนาที่จะทำอะไรบางอย่าง"

q1) แคร่ควรไปทางขวา: ถ้าเห็น 0 มันจะเปลี่ยนเป็น 1 และยังคงอยู่ในสถานะ q1 ถ้าเห็น 1 มันจะเปลี่ยนเป็น 0 และยังคงอยู่ในสถานะ q1 ถ้าเห็น _ มัน กลับไปที่ 1 เซลล์ “ต้องการอย่างอื่น” เช่น เข้าสู่สถานะ q2 มาเขียนเหตุผลของเราลงในตารางของนักแสดงกันดีกว่า สำหรับไวยากรณ์ โปรดดูวิธีใช้โปรแกรม)

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

คุณสามารถรับชมการทำงานของโปรแกรมได้ในวิดีโอ:

ปัญหาที่ 2 ให้ไว้: ลำดับจำกัดของ 0 และ 1 (001101011101) จำเป็นต้องเขียนออกมาหลังจากลำดับนี้ผ่านเซลล์ว่างและในลำดับนี้ให้แทนที่ด้วย 0 ตัวอย่างเช่น

จาก 001101011101 เราได้รับ 000000000000 1111111

อย่างที่คุณเห็นมีเจ็ดอันถูกเขียนขึ้นหลังจากลำดับนี้และมีศูนย์อยู่ในตำแหน่งของพวกเขา

มาเริ่มการสนทนากันดีกว่า เรามาพิจารณาว่าความต้องการการขนส่งระบุใดและจำนวนเท่าใด

q1) เห็น 1 - แก้ไขให้เป็นศูนย์และไปที่สถานะอื่น q2 (มีการแนะนำสถานะใหม่เพื่อให้แคร่ไม่เปลี่ยนสถานะทั้งหมดเป็นศูนย์ในการผ่านครั้งเดียว)

q2) ไม่ต้องเปลี่ยนแปลงอะไรเลย ให้ย้ายไปที่จุดสิ้นสุดของลำดับ

q3) ทันทีที่แคร่เห็นเซลล์ว่าง มันจะก้าวไปทางขวาแล้ววาดเลข 1 ถ้าเห็นเลข 1 มันจะเคลื่อนที่ต่อไปเพื่อลงนามสัญลักษณ์ที่ส่วนท้าย ทันทีที่ฉันวาดหน่วยได้ เราก็ไปที่สถานะ q4

q4) เราอ่านหน่วยที่เป็นลายลักษณ์อักษรโดยไม่มีการเปลี่ยนแปลงอะไรเลย ทันทีที่เราไปถึงเซลล์ว่างที่แยกลำดับออกจากเซลล์ เราจะย้ายไปยังสถานะใหม่ q5

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

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

เราได้รับโปรแกรมดังต่อไปนี้:

คุณสามารถรับชมการทำงานของ Turing Machine ได้ในวิดีโอด้านล่าง

เครื่องทัวริง (MT)- นักแสดงเชิงนามธรรม (เครื่องคำนวณเชิงนามธรรม) ได้รับการแนะนำ อลัน ทัวริงวี 2479เพื่อทำให้แนวคิดเป็นทางการ อัลกอริทึม.

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

การออกแบบเครื่องจักรทัวริง

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

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

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

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

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

เครื่องจักรทัวริงเฉพาะถูกกำหนดโดยการแสดงรายการองค์ประกอบของชุดตัวอักษรของตัวอักษร A ชุดของสถานะ Q และชุดกฎที่เครื่องจักรทำงาน พวกเขามีรูปแบบ: q i a j →q i1 a j1 d k (หากหัวอยู่ในสถานะ q i และตัวอักษร a j ถูกเขียนในเซลล์ที่สังเกตจากนั้นหัวจะไปที่สถานะ q i1, j1 จะถูกเขียนในเซลล์ แทนที่จะเป็น j หัวจะเคลื่อนไหว d k ซึ่งมีสามตัวเลือก: หนึ่งเซลล์ทางซ้าย (L) หนึ่งเซลล์ไปทางขวา (R) คงอยู่กับที่ (N)) สำหรับทุกการกำหนดค่าที่เป็นไปได้ มีกฎอยู่ข้อเดียว ไม่มีกฎเกณฑ์เฉพาะสำหรับสถานะสุดท้ายเท่านั้น ซึ่งครั้งหนึ่งรถจะจอด นอกจากนี้ คุณต้องระบุสถานะสุดท้ายและสถานะเริ่มต้น การกำหนดค่าเริ่มต้นบนเทป และตำแหน่งของหัวเครื่องจักร

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

เรามายกตัวอย่าง MT สำหรับการคูณตัวเลขกัน ระบบจำนวนเอกนารี- เครื่องทำงานตามกฎชุดต่อไปนี้:

ลองใช้ MT 3 ด้วย 2 ในระบบหน่วย:

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

ทัวริงความสมบูรณ์

บทความหลัก: ทัวริงความสมบูรณ์

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

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

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

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

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

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

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

รุ่นต่างๆ ของเครื่องทัวริง

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

เครื่องทัวริงทำงานบนเทปกึ่งอนันต์

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

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

จากนั้นเรากำหนดหมายเลขเซลล์ใหม่ และเราจะถือว่าสัญลักษณ์ "*" ไม่มีอยู่ในพจนานุกรม MT:

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

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

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

สาระสำคัญในคำง่ายๆ

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

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

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

มันทำงานอย่างไร

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

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

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

ตัวเลือกต่างๆ

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

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

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

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

ประโยชน์เชิงปฏิบัติ

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

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

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

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

สิ่งพิมพ์ก่อนหน้า:

แก้ไขล่าสุด: 2013-04-01 10:58:05

แท็กวัสดุ: ,