ผลต่างระหว่างรุ่นของ "เครื่องทัวริง"
ล โรบอต เพิ่ม: be-x-old:Машына Т'юрынга; ปรับแต่งให้อ่านง่าย |
ล r2.6.4) (โรบอต แก้ไข: be-x-old:Машына Т’юрынга |
||
บรรทัด 16: | บรรทัด 16: | ||
[[ar:آلة تورنج]] |
[[ar:آلة تورنج]] |
||
[[be:Машына Т'юрынга]] |
[[be:Машына Т'юрынга]] |
||
[[be-x-old:Машына |
[[be-x-old:Машына Т’юрынга]] |
||
[[bg:Машина на Тюринг]] |
[[bg:Машина на Тюринг]] |
||
[[bs:Turingova mašina]] |
[[bs:Turingova mašina]] |
รุ่นแก้ไขเมื่อ 13:56, 19 มีนาคม 2554
เครื่องจักรทัวริง (อังกฤษ: Turing machine) คือเครื่องจักรนามธรรมที่แอลัน ทัวริงได้คิดค้นขึ้นใน ค.ศ. 1936 (พ.ศ. 2479) เพื่อการนิยามอัลกอริทึมหรือ 'กระบวนการเชิงกล' อย่างชัดเจนแบบคณิตศาสตร์ เครื่องจักรทัวริงได้ถูกใช้อย่างแพร่หลายในการศึกษาวิทยาการคอมพิวเตอร์เชิงทฤษฎี โดยเฉพาะในทฤษฎีความซับซ้อนในการคำนวณและทฤษฎีการคำนวณ ข้อปัญหา (thesis) ที่ว่าโมเดลของเครื่องจักรทัวริงนั้นครอบคลุมกระบวนการเชิงกลทั้งหมด ในการคำนวณทางตรรกศาสตร์และคณิตศาสตร์ เป็นที่รู้จักกันในชื่อข้อปัญหาของเชิร์ช-ทัวริง
แนวคิดของเครื่องจักรทัวริงนั้นต้องการจะอธิบายการทำงานของคนที่ปฏิบัติตามขั้นตอนที่ระบุไว้อย่างชัดเจน เพื่อแก้ไขข้อมูลที่ถูกบันทึกไว้ในกระดาษที่เรียงต่อกันความยาวไม่จำกัด โดยที่กระดาษแผ่นหนึ่งจะสามารถเก็บสัญลักษณ์ได้หนึ่งตัวจากสัญลักษณ์ที่เป็นไปได้จำนวนจำกัด ผู้ปฏิบัติงานนั้นจะต้องจดจำสถานะหนึ่งจากสถานะที่เป็นไปได้ที่มีจำนวนจำกัด และขั้นตอนที่ระบุให้เขาทำงานนั้นจะอยู่ในลักษณะเช่น "ถ้าสถานะของคุณคือ 42 และสัญลักษณ์บนกระดาษที่คุณเห็นคือ '0', ให้เปลี่ยนสัญลักษณ์นี้เป็น '1', จดจำว่าสถานะใหม่เป็น 17 และไปทำงานต่อกับกระดาษแผ่นถัดไป"
เครื่องจักรทัวริงนั้นไม่เกี่ยวข้องกับการทดสอบของทัวริง ซึ่งถูกใช้เพื่ออธิบายความหมายของปัญญาประดิษฐ์โดยทัวริง
เครื่องจักรทัวริงที่สามารถจำลองการทำงานของเครื่องจักรทัวริงเครื่องใด ๆ ก็ได้เรียกว่า เครื่องจักรทัวริงสากล (universal Turing machine) หรือเรียกสั้นๆ ว่า เครื่องจักรสากล ทัวริงอธิบายไว้ใน ค.ศ. 1947 (พ.ศ. 2490) ว่า
- สามารถแสดงได้ว่ามีเครื่องจักรพิเศษในรูปแบบนี้ ที่สามารถทำงานของเครื่องจักรอื่น ๆ ในรูปแบบดังกล่าวได้ทั้งหมด นอกจากนี้เครื่องจักรนี้ยังสามารถใช้เป็นโมเดลสำหรับเครื่องจักรในแบบอื่น ๆ เครื่องจักรพิเศษนี้สามารถเรียกได้ว่าเป็นเครื่องจักรสากล