อ่าน 2 นาที
ปัญหาฟังก์ชันเลขชี้กำลังของทาร์สกี
ในทฤษฎีแบบจำลองปัญหาฟังก์ชันเลขชี้กำลังของ Tarskiถามว่าทฤษฎีของจำนวนจริงพร้อมกับฟังก์ชันเลขชี้กำลังสามารถตัดสินได้หรือไม่Alfred Tarskiได้แสดงให้เห็นก่อนหน้านี้ว่าทฤษฎีของจำนวนจริง.
ปัญหาฟังก์ชันเลขชี้กำลังของทาร์สกี
ในทฤษฎีแบบจำลองปัญหาฟังก์ชันเลขชี้กำลังของ Tarskiถามว่าทฤษฎีของจำนวนจริงพร้อมกับฟังก์ชันเลขชี้กำลังสามารถตัดสินได้หรือไม่Alfred Tarskiได้แสดงให้เห็นก่อนหน้านี้ว่าทฤษฎีของจำนวนจริง (โดยไม่มีฟังก์ชันเลขชี้กำลัง) สามารถตัดสินได้[ 1 ]
ปัญหา
ฟิลด์จำนวนจริงเรียงลำดับ (Ordered Real Field) เป็นโครงสร้างเหนือภาษาของวงแหวนเรียงลำดับ (Ordered Rings)โดยมีการตีความตามปกติที่กำหนดให้กับแต่ละสัญลักษณ์ ทาร์สกีได้พิสูจน์แล้วว่าทฤษฎีของฟิลด์จำนวนจริง นั้นสามารถตัดสินได้ (Decidable Theory of the real field ) กล่าวคือ เมื่อกำหนดประโยค ใดๆ ก็ตาม จะมีขั้นตอนที่มีประสิทธิภาพในการพิจารณาว่า เป็น จริง หรือไม่
จากนั้นเขาถามว่า หากเพิ่มฟังก์ชันเอกภาคเข้าไปในภาษา ซึ่งถูกตีความว่าเป็นฟังก์ชันเลขชี้กำลังบนเพื่อให้ได้โครงสร้างดังกล่าวสถานการณ์ นี้ยังคงเป็นเช่นนั้นอยู่หรือไม่
ผลลัพธ์แบบมีเงื่อนไขและเทียบเท่า
ปัญหาสามารถลดทอนลงเหลือเพียงการค้นหาขั้นตอนที่มีประสิทธิภาพในการพิจารณาว่าพหุนามเอกซ์โพเนน เชียลที่กำหนด ในตัวแปรและมีสัมประสิทธิ์ในนั้นมีคำตอบใน หรือ ไม่ Macintyre & Wilkie (1996)แสดงให้เห็นว่าสมมติฐานของ Schanuelบ่งชี้ว่ามีขั้นตอนดังกล่าวอยู่ และด้วยเหตุนี้จึงให้คำตอบแบบมีเงื่อนไขสำหรับปัญหาของ Tarski [ 2 ]สมมติฐานของ Schanuel เกี่ยวข้องกับจำนวนเชิงซ้อนทั้งหมด ดังนั้นจึงคาดว่าจะเป็นผลลัพธ์ที่แข็งแกร่งกว่าความสามารถในการตัดสินของและในความเป็นจริง Macintyre และ Wilkie พิสูจน์แล้วว่าจำเป็นต้องมีเพียงเวอร์ชันจริงของสมมติฐานของ Schanuel เท่านั้นเพื่อบ่งชี้ถึงความสามารถในการตัดสินของทฤษฎีนี้
แม้แต่สมมติฐานของ Schanuel ในรูปแบบจริงก็ไม่ใช่เงื่อนไขที่จำเป็นสำหรับการตัดสินได้ของทฤษฎี ในบทความของ Macintyre และ Wilkie พวกเขาแสดงให้เห็นว่าผลลัพธ์ที่เทียบเท่ากับการตัดสินได้ของทฤษฎีนั้นคือสิ่งที่พวกเขาเรียกว่าสมมติฐานของ Schanuel แบบอ่อน สมมติฐานนี้กล่าวว่ามีกระบวนการที่มีประสิทธิภาพซึ่งเมื่อกำหนดพหุนามเลขชี้กำลังในตัวแปรที่มีสัมประสิทธิ์เป็นจำนวนเต็มจะได้จำนวนเต็มที่ขึ้นอยู่กับและเป็นเช่นนั้น ถ้าเป็น คำตอบ ที่ไม่เอกฐานของระบบ
จากนั้นก็เลือกอย่างใดอย่าง หนึ่ง
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ ปัญหาฟังก์ชันเลขชี้กำลังของทาร์สกี
ในทฤษฎีแบบจำลองปัญหาฟังก์ชันเลขชี้กำลังของ Tarskiถามว่าทฤษฎีของจำนวนจริงพร้อมกับฟังก์ชันเลขชี้กำลังสามารถตัดสินได้หรือไม่Alfred Tarskiได้แสดงให้เห็นก่อนหน้านี้ว่าทฤษฎีของจำนวนจริง.
ปัญหา
ฟิลด์จำนวนจริงเรียงลำดับ (Ordered Real Field) เป็นโครงสร้างเหนือภาษาของ วงแหวนเรียงลำดับ (Ordered Rings) โดยมีการตีความตามปกติที่กำหนดให้กับแต่ละสัญลักษณ์ ทาร์สกีได้พิสูจน์แล้วว่าทฤษฎีของฟิลด์จำนวนจริง นั้นสามารถตัดสินได้ (Decidable Theory of the real field )...
ผลลัพธ์แบบมีเงื่อนไขและเทียบเท่า
ปัญหาสามารถลดทอนลงเหลือเพียงการค้นหาขั้นตอนที่มีประสิทธิภาพในการพิจารณาว่า พหุนามเอกซ์โพเนน เชียลที่กำหนด ในตัวแปรและมีสัมประสิทธิ์ในนั้นมีคำตอบใน หรือ ไม่ Macintyre & Wilkie (1996) แสดงให้เห็นว่า สมมติฐานของ Schanuel บ่งชี้ว่ามีขั้นตอนดังกล่าวอยู่...