จอห์น ไมฮิลล์

จอห์น อาร์. ไมฮิลล์ (John R. Myhill) (11 สิงหาคม ค.ศ. 1923 – 15 กุมภาพันธ์ ค.ศ. 1987) เป็นนักคณิตศาสตร์ชาวอังกฤษผู้มีบทบาทสำคัญในการวางรากฐานด้านตรรกศาสตร์คณิตศาสตร์ ทฤษฎีการคำนวณ และทฤษฎีภาษาทางการ ผลงานของเขาได้รับการยอมรับอย่างกว้างขวางในแวดวงวิชาการระดับสากล

ประวัติและการศึกษา

ไมฮิลล์สำเร็จการศึกษาระดับปริญญาเอกสาขาคณิตศาสตร์จากมหาวิทยาลัยฮาร์วาร์ดในปี ค.ศ. 1949 ภายใต้การดูแลของวิลลาร์ด แวน ออร์แมน ควีน (Willard Van Orman Quine) นักปรัชญาและนักตรรกศาสตร์ชื่อดัง ตลอดอาชีพการทำงานของเขา ไมฮิลล์ได้สอนในมหาวิทยาลัยหลายแห่ง และดำรงตำแหน่งศาสตราจารย์ที่มหาวิทยาลัยแห่งรัฐนิวยอร์กที่บัฟฟาโล (SUNY Buffalo) ตั้งแต่ปี ค.ศ. 1966 จนกระทั่งเสียชีวิตในปี ค.ศ. 1987

ผลงานทางวิชาการที่สำคัญ

ผลงานของไมฮิลล์ครอบคลุมหลายสาขาในคณิตศาสตร์บริสุทธิ์และวิทยาการคอมพิวเตอร์เชิงทฤษฎี ดังนี้:

• ทฤษฎีภาษาทางการ: เขาได้ร่วมพิสูจน์ ทฤษฎีบทไมฮิลล์-เนโรด (Myhill–Nerode theorem) ร่วมกับอนิล เนโรด ซึ่งเป็นเครื่องมือสำคัญในการจำแนกภาษาปกติ (regular languages) โดยพิจารณาจากจำนวนคำนำหน้า (prefixes) ที่ไม่สมมูลกัน
• ทฤษฎีการคำนวณ: เขามีส่วนร่วมใน ทฤษฎีบทไรซ์-ไมฮิลล์-ชาปิโร (Rice–Myhill–Shapiro theorem) หรือที่รู้จักกันทั่วไปในชื่อทฤษฎีบทของไรซ์ ซึ่งว่าด้วยความไม่สามารถตัดสินได้ (undecidability) ของคุณสมบัติของฟังก์ชันบางส่วน นอกจากนี้ยังมี ทฤษฎีบทไอโซมอร์ฟิซึมของไมฮิลล์ (Myhill isomorphism theorem) ที่ใช้ในการศึกษาการสมสัณฐานของเซตในเชิงการคำนวณ
• ทฤษฎีออโตมาตา: ไมฮิลล์ได้พิสูจน์ ทฤษฎีบทสวนอีเดน (Garden of Eden theorem) ร่วมกับอี. เอฟ. มัวร์ และเป็นผู้ตั้งโจทย์ปัญหา Firing Squad Synchronization Problem ซึ่งเป็นปัญหาคลาสสิกในการออกแบบออโตมาตาให้ทำงานประสานกัน
• ตรรกศาสตร์และทฤษฎีเซต: เขาได้เสนอระบบสัจพจน์สำหรับทฤษฎีเซตเชิงสัญชาตญาณ (intuitionistic Zermelo–Fraenkel) ที่หลีกเลี่ยงสัจพจน์แห่งการเลือกและกฎของมัชฌิมวิภัช
• ปฏิทรรศน์รัสเซลล์-ไมฮิลล์: เขาได้ค้นพบปฏิทรรศน์ทางตรรกศาสตร์ที่เกี่ยวข้องกับระบบที่ข้อเสนอทางตรรกะสามารถเป็นสมาชิกของชั้น (classes) ได้ ซึ่งเป็นการขยายความจากแนวคิดของเบอร์ทรันด์ รัสเซลล์