ผลต่างระหว่างรุ่นของ "เครื่องทัวริง"
ล robot Adding: sr:Тјурингова машина |
ล robot Adding: uk:Машина Т'юрінга |
||
บรรทัด 45: | บรรทัด 45: | ||
[[sv:Turingmaskin]] |
[[sv:Turingmaskin]] |
||
[[tr:Turing makinesi]] |
[[tr:Turing makinesi]] |
||
[[uk:Машина Т'юрінга]] |
|||
[[zh:图灵机]] |
[[zh:图灵机]] |
รุ่นแก้ไขเมื่อ 18:47, 1 กรกฎาคม 2549
เครื่องจักรทัวริง (the Turing machine) คือเครื่องจักรนามธรรมที่แอลัน ทัวริงได้คิดค้นขึ้นใน ค.ศ. 1936 (พ.ศ. 2479) เพื่อการนิยามอัลกอริทึมหรือ 'กระบวนการเชิงกล' อย่างชัดเจนแบบคณิตศาสตร์ เครื่องจักรทัวริงได้ถูกใช้อย่างแพร่หลายในการศึกษาวิทยาการคอมพิวเตอร์เชิงทฤษฎี โดยเฉพาะในทฤษฎีความซับซ้อนในการคำนวณและทฤษฎีการคำนวณ ข้อปัญหา (thesis) ที่ว่าโมเดลของเครื่องจักรทัวริงนั้นครอบคลุมกระบวนการเชิงกลทั้งหมด ในการคำนวณทางตรรกศาสตร์และคณิตศาสตร์ เป็นที่รู้จักกันในชื่อข้อปัญหาของเชิร์ช-ทัวริง
แนวคิดของเครื่องจักรทัวริงนั้นต้องการจะอธิบายการทำงานของคนที่ปฏิบัติตามขั้นตอนที่ระบุไว้อย่างชัดเจน เพื่อแก้ไขข้อมูลที่ถูกบันทึกไว้ในกระดาษที่เรียงต่อกันความยาวไม่จำกัด โดยที่กระดาษแผ่นหนึ่งจะสามารถเก็บสัญลักษณ์ได้หนึ่งตัวจากสัญลักษณ์ที่เป็นไปได้จำนวนจำกัด ผู้ปฏิบัติงานนั้นจะต้องจดจำสถานะหนึ่งจากสถานะที่เป็นไปได้ที่มีจำนวนจำกัด และขั้นตอนที่ระบุให้เขาทำงานนั้นจะอยู่ในลักษณะเช่น "ถ้าสถานะของคุณคือ 42 และสัญลักษณ์บนกระดาษที่คุณเห็นคือ '0', ให้เปลี่ยนสัญลักษณ์นี้เป็น '1', จดจำว่าสถานะใหม่เป็น 17 และไปทำงานต่อกับกระดาษแผ่นถัดไป"
เครื่องจักรทัวริงนั้นไม่เกี่ยวข้องกับการทดสอบของทัวริง ซึ่งถูกใช้เพื่ออธิบายความหมายของปัญญาประดิษฐ์โดยทัวริง
เครื่องจักรทัวริงที่สามารถจำลองการทำงานของเครื่องจักรทัวริงเครื่องใด ๆ ก็ได้เรียกว่า เครื่องจักรทัวริงสากล (universal Turing machine) หรือเรียกสั้นๆ ว่า เครื่องจักรสากล ทัวริงอธิบายไว้ใน ค.ศ. 1947 (พ.ศ. 2490) ว่า
- สามารถแสดงได้ว่ามีเครื่องจักรพิเศษในรูปแบบนี้ ที่สามารถทำงานของเครื่องจักรอื่น ๆ ในรูปแบบดังกล่าวได้ทั้งหมด นอกจากนี้เครื่องจักรนี้ยังสามารถใช้เป็นโมเดลสำหรับเครื่องจักรในแบบอื่น ๆ เครื่องจักรพิเศษนี้สามารถเรียกได้ว่าเป็นเครื่องจักรสากล