เอมิล ลีออน โพสต์
เกิด	วันที่ 11 กุมภาพันธ์ พ.ศ. 2440 ออกัสตูฟ เขตผู้ ว่าการซูวาว์กีรัฐสภาโปแลนด์จักรวรรดิรัสเซีย ( ปัจจุบันคือโปแลนด์)
เสียชีวิต	21 เมษายน 2497 (21 เมษายน 1954)(อายุ 57 ปี) นครนิวยอร์ก สหรัฐอเมริกา
อัลมา มัธยฐาน	วิทยาลัยซิตี้แห่งนิวยอร์ก (ปริญญาตรี, 1917) [ 1 ]มหาวิทยาลัยโคลัมเบีย (ปริญญาโท 1918, ปริญญาเอก 1920) [ 2 ]
เป็นที่รู้จักในด้าน	การกำหนดสูตร 1 ปัญหาการติดต่อสื่อสารของโพสต์ การ พิสูจน์ความสมบูรณ์ของแคลคูลัสเชิง ประพจน์ ของPrincipiaสูตรผกผันของโพสต์ แลตทิซของโพสต์ทฤษฎีบทของโพ สต์
เส้นทางอาชีพด้านวิทยาศาสตร์
ฟิลด์	คณิตศาสตร์ตรรกศาสตร์​
สถาบันต่างๆ	มหาวิทยาลัยพรินซ์ตัน
วิทยานิพนธ์	บทนำสู่ทฤษฎีทั่วไปของประพจน์พื้นฐาน (1920)
อาจารย์ที่ปรึกษาปริญญาเอก	แคสเซียส แจ็กสัน คีย์เซอร์

เอมิล ลีออน โพสต์ ( / p oʊ s t / ; 11 กุมภาพันธ์ 1897 – 21 เมษายน 1954) เป็นนักคณิตศาสตร์และนักตรรกศาสตร์ ชาวอเมริกัน เขาเป็นที่รู้จักกันดีที่สุดจากผลงานในสาขาที่ต่อมากลายเป็นที่รู้จักในชื่อทฤษฎีความสามารถในการคำนวณ

โพสต์เกิดที่ออกัสตอฟจังหวัด ซูวาว กี โปแลนด์ ภายใต้การปกครองของรัฐสภา จักรวรรดิรัสเซีย (ปัจจุบันคือโปแลนด์) ใน ครอบครัว ชาวยิวโปแลนด์ที่อพยพไปยังนครนิวยอร์กในเดือนพฤษภาคม พ.ศ. 2447 บิดามารดาของเขาคืออาร์โนลด์และเพิร์ล โพสต์^{[ 2 ]}

โพสต์สนใจดาราศาสตร์ แต่เมื่ออายุสิบสองปีเขาเสียแขนซ้ายไปในอุบัติเหตุทางรถยนต์ การสูญเสียครั้งนี้เป็นอุปสรรคสำคัญต่อการเป็นนักดาราศาสตร์มืออาชีพ ทำให้เขาตัดสินใจเรียนคณิตศาสตร์แทนดาราศาสตร์^{[ 3 ]}

โพสต์เข้าเรียนที่โรงเรียนมัธยมทาวน์เซนด์ แฮร์ริสและศึกษาต่อจนจบการศึกษาจากวิทยาลัยซิตี้แห่งนิวยอร์กในปี พ.ศ. 2460 โดยได้รับปริญญาตรีวิทยาศาสตร์สาขาคณิตศาสตร์^{[ 1 ]}

หลังจากสำเร็จการศึกษาระดับปริญญาเอกสาขาคณิตศาสตร์ในปี 1920 จากมหาวิทยาลัยโคลัมเบียโดยมีแคสเซียส แจ็กสัน คีย์เซอร์ เป็นอาจารย์ที่ปรึกษา เขาได้ทำงานวิจัยหลังปริญญาเอกที่มหาวิทยาลัยพรินซ์ตันในปีการศึกษา 1920–1921 จากนั้นโพสต์ก็ได้เป็นครูสอนคณิตศาสตร์ระดับมัธยมปลายในนครนิวยอร์ก

โพสต์แต่งงานกับเกอร์ทรูด ซิงเกอร์ (1900–1956) ในปี 1929 และมีลูกสาวด้วยกันหนึ่งคน คือ ฟิลลิส โพสต์ กู๊ดแมน (1932–1995) ^{[ 4 ]}โพสต์ใช้เวลาทำวิจัยไม่เกินสามชั่วโมงต่อวันตามคำแนะนำของแพทย์ เพื่อหลีกเลี่ยงอาการคลุ้มคลั่ง ซึ่งเขาประสบมาตั้งแต่สมัยเรียนที่มหาวิทยาลัยพรินซ์ตัน^{[ 5 ]}

ในปี พ.ศ. 2479 เขาได้รับการแต่งตั้งให้ดำรงตำแหน่งในภาควิชาคณิตศาสตร์ที่วิทยาลัยซิตี้แห่งนิวยอร์ก เขาเสียชีวิตในเดือนเมษายน พ.ศ. 2497 ด้วยอาการหัวใจ วาย หลังจากได้รับการรักษาด้วยการช็อกไฟฟ้าเพื่อ รักษาอาการ ซึมเศร้า^{[ 5 ] [ 6 ]}

ในวิทยานิพนธ์ระดับปริญญาเอกของเขา ซึ่งต่อมาได้ย่อและตีพิมพ์เป็น "บทนำสู่ทฤษฎีทั่วไปของประพจน์พื้นฐาน" (1921) โพสต์ได้พิสูจน์ว่าแคลคูลัสเชิงประพจน์ของPrincipia Mathematica นั้นสมบูรณ์ กล่าวคือ สัจนิรันดร์ทั้งหมดเป็นทฤษฎีบทเมื่อกำหนด สัจพจน์ของ Principiaและกฎของการแทนที่และmodus ponensโพสต์ยังได้คิดค้นตารางความจริงขึ้นโดยอิสระจากซี.เอส. เพียร์ซและลุดวิก วิทเกนสไตน์และนำไปใช้ประโยชน์ทางคณิตศาสตร์ได้เป็นอย่างดี หนังสืออ้างอิงที่มีชื่อเสียงของ ฌอง ฟาน เฮเยนอร์ทเกี่ยวกับตรรกศาสตร์ทางคณิตศาสตร์ (1966) ได้พิมพ์ซ้ำบทความคลาสสิกของโพสต์ในปี 1921 ซึ่งนำเสนอผลลัพธ์เหล่านี้

ขณะอยู่ที่มหาวิทยาลัยพรินซ์ตัน โพสต์เกือบจะค้นพบความไม่สมบูรณ์ของPrincipia Mathematicaซึ่งเคิร์ท เกอเดลได้พิสูจน์ในปี 1931 โพสต์ไม่ได้เผยแพร่แนวคิดของเขาในตอนแรก เนื่องจากเขาเชื่อว่าเขาต้องการ 'การวิเคราะห์ที่สมบูรณ์' เพื่อให้แนวคิดนั้นได้รับการยอมรับ^{[ 2 ]}ดังที่โพสต์กล่าวไว้ในโปสการ์ดถึงเกอเดลในปี 1938:

ฉันคงค้นพบทฤษฎีบทของเกอเดลในปี พ.ศ. 2464 หากฉันเป็นเกอเดล^{[ 7 ]}

ในปี ค.ศ. 1936 อลัน โพสต์ ได้พัฒนา แบบจำลองทางคณิตศาสตร์ของการคำนวณโดยอิสระจากอลัน ทัวริง ซึ่งโดยพื้นฐานแล้วเทียบเท่ากับแบบจำลอง เครื่องจักรทัวริงเขาตั้งใจให้แบบจำลองนี้เป็นแบบจำลองแรกในชุดแบบจำลองที่มีกำลังการคำนวณเท่ากันแต่มีความซับซ้อนเพิ่มขึ้นเรื่อยๆ และตั้งชื่อบทความของเขาว่าFormulation 1แบบจำลองนี้บางครั้งเรียกว่า "เครื่องจักรของโพสต์" หรือเครื่องจักรโพสต์-ทัวริงแต่ไม่ควรสับสนกับเครื่องจักรแท็กของโพสต์ หรือ ระบบแคนอนิกของโพสต์ชนิดพิเศษอื่นๆ ซึ่งเป็นแบบจำลองการคำนวณที่ใช้การเขียนสตริงใหม่และพัฒนาขึ้นโดยโพสต์ในช่วงทศวรรษ ค.ศ. 1920 แต่ตีพิมพ์ครั้งแรกในปี ค.ศ. 1943 เทคนิคการเขียนใหม่ของโพสต์ในปัจจุบันแพร่หลายในการกำหนดและออกแบบภาษาโปรแกรม และแคลคูลัสแลมบ์ดาของเชิร์ชก็เป็นอิทธิพลที่โดดเด่นของตรรกศาสตร์สมัยใหม่แบบคลาสสิกต่อการคำนวณเชิงปฏิบัติ โพสต์คิดค้นวิธีการ "สัญลักษณ์เสริม" ซึ่งเขาสามารถใช้แทนภาษาที่สร้างโดยโพสต์ใดๆ ได้อย่างเป็นแคนอนิก และแท้จริงแล้วยังสามารถแทนฟังก์ชันที่คำนวณได้หรือเซตที่คำนวณได้ทั้งหมดอีกด้วย

ระบบการติดต่อสื่อสารได้รับการแนะนำโดย Post ในปี พ.ศ. 2489 เพื่อเป็นตัวอย่างง่ายๆ ของความไม่สามารถตัดสินได้ [ ^{8 ] เขา}แสดงให้เห็นว่าปัญหาการติดต่อสื่อสารของ Post (PCP) ในการปฏิบัติตามข้อจำกัดนั้นโดยทั่วไปแล้วไม่สามารถตัดสินได้ ความไม่สามารถตัดสินได้ของปัญหาการติดต่อสื่อสารกลายเป็นสิ่งที่จำเป็นอย่างยิ่งในการได้รับผลลัพธ์ความไม่สามารถตัดสินได้ในทฤษฎีภาษา ทางการ

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

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

• Post, Emil L. (1919). "ฟังก์ชันแกมมาทั่วไป" . Annals of Mathematics . ชุดที่สอง. 20 (3): 202– 217. doi : 10.2307/1967871 . JSTOR  1967871 .
• Post, Emil L. (1921). "บทนำสู่ทฤษฎีทั่วไปของประพจน์พื้นฐาน". American Journal of Mathematics . 43 (3): 163– 185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR  2370324 .
• Post, Emil L. (1936). "กระบวนการรวมเชิงจำกัด – การกำหนดสูตร 1". วารสารตรรกศาสตร์เชิงสัญลักษณ์ 1 ( 3): 103– 105. doi : 10.2307/2269031 . JSTOR  2269031 . S2CID  40284503 .
• Post, Emil L. (1940). "กลุ่มพหุนาม" . ธุรกรรมของสมาคมคณิตศาสตร์อเมริกัน . 48 (2): 208– 350. doi : 10.2307/1990085 . JSTOR  1990085 .
• Post, Emil L. (1943). "การลดรูปอย่างเป็นทางการของปัญหาการตัดสินใจเชิงรวมทั่วไป" American Journal of Mathematics . 65 (2): 197– 215. doi : 10.2307/2371809 . JSTOR  2371809 .
• Post, Emil L. (1944). "เซตของจำนวนเต็มบวกที่สามารถนับได้แบบเวียนซ้ำและปัญหาการตัดสินใจของเซตเหล่านั้น"วารสารของสมาคมคณิตศาสตร์อเมริกัน 50 ( 5): 284– 316. doi : 10.1090/s0002-9904-1944-08111-1 .นำเสนอแนวคิดสำคัญเรื่องการลดรูปหลายต่อหนึ่ง (many-one reduction )

• ลำดับชั้นทางคณิตศาสตร์
• ความสมบูรณ์เชิงฟังก์ชัน
• รายชื่อการค้นพบหลายรายการ
• รายชื่อผู้บุกเบิกในสาขาวิทยาการคอมพิวเตอร์

• Anshel, Iris Lee; Anshel, Michael (พฤศจิกายน 1993). "จากทฤษฎีบทโพสต์-มาร์คอฟ ผ่านปัญหาการตัดสินใจ ไปจนถึงการเข้ารหัสแบบกุญแจสาธารณะ" The American Mathematical Monthly . 100 (9). Mathematical Association of America: 835– 844. doi : 10.2307/2324657 . JSTOR  2324657 .

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

• เดวิส, มาร์ติน, บรรณาธิการ (1993). สิ่งที่ไม่สามารถตัดสินได้ . โดเวอร์. หน้า  288–406 . ISBN 0-486-43228-9.

  ตีพิมพ์ซ้ำบทความหลายฉบับจากวารสาร Post

• เดวิส, มาร์ติน (1994). "เอมิล แอล. โพสต์: ชีวิตและผลงานของเขา". ความสามารถในการแก้ปัญหา ความสามารถในการพิสูจน์ ความสามารถในการกำหนดนิยาม: ผลงานรวมของเอมิล แอล. โพสต์ . เบิร์คเฮาเซอร์. หน้า  xi– xxviii.

  บทความชีวประวัติ

• Jackson, Allyn (พฤษภาคม 2008). "บทสัมภาษณ์กับ Martin Davis" . Notices of the AMS . 55 (5): 560– 571.

  มีข้อมูลมากมายเกี่ยวกับเอมิล โพสต์ ซึ่งได้มาจากความทรงจำโดยตรงของเขา

• Jackson, Allyn (ตุลาคม 2018). "Emil Post: Psychological Fidelity" . Inference: International Review of Science . doi : 10.37282/991819.18.48 . S2CID  240012225 .

  บทความชีวประวัติ

• เอกสารของเอมิล ลีออน โพสต์ ปี 1927-1991สมาคมปรัชญาอเมริกัน ฟิลาเดลเฟียรัฐเพนซิลเวเนีย
• "เฉลิมฉลอง Emil Post และ 'ปัญหาที่แก้ไม่ตก' ของเขาเรื่องเกม Tag: 100 ปีต่อมา" YouTube Wolfram 19 พฤษภาคม 2021 เก็บถาวรจากต้นฉบับเมื่อ 21 ธันวาคม 2021