เครื่องนามธรรมคืออะไร?

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

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

Wolfram Mathworld

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

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