ลักษณะเฉพาะของอัลกอริทึมคือความพยายามที่จะทำให้คำว่าอัลก อริทึมเป็นทางการ อัลกอริทึมไม่มีคำจำกัดความที่เป็นทางการที่เป็นที่ยอมรับโดยทั่วไป นักวิจัย^{[ 1 ]}กำลังทำงานอย่างแข็งขันในปัญหานี้ บทความนี้จะนำเสนอ "ลักษณะเฉพาะ" บางประการของแนวคิด "อัลกอริทึม" ในรายละเอียดเพิ่มเติม

ในช่วง 200 ปีที่ผ่านมา นิยามของอัลกอริทึมมีความซับซ้อนและละเอียดมากขึ้นเรื่อยๆ เนื่องจากนักวิจัยพยายามที่จะกำหนดความหมายของคำนี้ให้ชัดเจน ที่จริงแล้ว อาจมี "อัลกอริทึม" มากกว่าหนึ่งประเภท แต่ส่วนใหญ่เห็นพ้องกันว่า อัลกอริทึมเกี่ยวข้องกับการกำหนดกระบวนการทั่วไปสำหรับการสร้างจำนวนเต็ม "ผลลัพธ์" จากจำนวนเต็ม "อินพุต" อื่นๆ โดยที่ "พารามิเตอร์อินพุต" นั้นอาจเป็นค่าใดๆ ก็ได้และไม่มีที่สิ้นสุด หรืออาจมีขอบเขตจำกัดแต่ยังคงเปลี่ยนแปลงได้ โดยการจัดการสัญลักษณ์ที่แยกแยะได้ (ตัวเลขนับ) ด้วยชุดกฎที่จำกัด ซึ่งบุคคลสามารถทำได้ด้วยกระดาษและดินสอ

รูปแบบการจัดการตัวเลขที่พบได้บ่อยที่สุด ทั้งในคณิตศาสตร์เชิงรูปธรรมและในชีวิตประจำวัน ได้แก่ (1) ฟังก์ชันเรียกซ้ำที่คำนวณโดยบุคคลด้วยกระดาษและดินสอ และ (2) เครื่องจักรทัวริงหรือเทียบเท่าทัวริง ได้แก่ แบบ จำลองเครื่องจักรลงทะเบียน แบบดั้งเดิม หรือ "เครื่องจักรนับ" แบบจำลองเครื่องจักรเข้าถึงแบบสุ่ม^{[ 1 ]} (RAM) แบบจำลอง เครื่องจักรโปรแกรมจัดเก็บเข้าถึงแบบสุ่ม (RASP) และ " คอมพิวเตอร์ " ซึ่งเป็นสิ่งที่เทียบเท่ากันในเชิงฟังก์ชัน

เมื่อเราทำการ "คำนวณเลข" เรากำลังคำนวณโดยใช้ "ฟังก์ชันเรียกซ้ำ" ในรูปแบบย่อที่เราเรียนรู้ในโรงเรียนประถม เช่น การบวกและการลบ

หลักฐานที่แสดงว่าทุก "ฟังก์ชันเวียนเกิด" ที่เราสามารถคำนวณด้วยมือได้เราก็สามารถคำนวณด้วยเครื่องจักรได้และในทางกลับกัน—โปรดสังเกตการใช้คำว่าคำนวณกับประมวลผล —นั้นน่าทึ่งมาก แต่ความเท่าเทียมกันนี้ ประกอบกับข้อสันนิษฐาน (ข้ออ้างที่ยังไม่ได้รับการพิสูจน์) ที่ว่าสิ่งนี้รวมถึง การคำนวณ/การประมวลผล ทุกอย่างบ่งชี้ว่าเหตุใดจึงมีการเน้นย้ำอย่างมากในการใช้ เครื่องจักร ที่เทียบเท่ากับเครื่องจักรทัวริงในการกำหนดอัลกอริทึมเฉพาะ และเหตุใดคำจำกัดความของ "อัลกอริทึม" เองจึงมักอ้างอิงถึง " เครื่องจักรทัวริง " เรื่องนี้จะกล่าวถึงในรายละเอียดเพิ่มเติมภายใต้ การจำแนกลักษณะ ของ Stephen Kleene

ต่อไปนี้เป็นบทสรุปของการจำแนกประเภทที่รู้จักกันดี (Kleene, Markov, Knuth) พร้อมกับการจำแนกประเภทที่นำเสนอองค์ประกอบใหม่ ๆ ซึ่งเป็นองค์ประกอบที่ขยายความนิยามหรือมีส่วนช่วยให้ได้นิยามที่แม่นยำยิ่งขึ้น

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

มีความเห็นพ้องกันมากขึ้นเกี่ยวกับการ "กำหนดลักษณะ" ของแนวคิดเรื่อง "อัลกอริทึมแบบง่าย"

อัลกอริทึมทั้งหมดจำเป็นต้องระบุไว้ในภาษาที่เป็นทางการ และ "แนวคิดเรื่องความเรียบง่าย" เกิดขึ้นจากความเรียบง่ายของภาษาลำดับชั้นของชอมสกี (1956)เป็นลำดับชั้นการบรรจุของกลุ่มไวยากรณ์ที่เป็นทางการที่สร้างภาษาที่เป็นทางการใช้สำหรับการจำแนกประเภทของภาษาโปรแกรมและเครื่องจักรนามธรรม

จาก มุมมอง ของลำดับชั้นของชอมสกีหากอัลกอริทึมสามารถระบุได้ด้วยภาษาที่เรียบง่ายกว่า (กว่าภาษาที่ไม่จำกัด) ก็สามารถอธิบายได้ด้วยภาษาประเภทนั้น มิเช่นนั้นก็จะเป็น "อัลกอริทึมที่ไม่จำกัด" ทั่วไป

ตัวอย่างเช่น ภาษามาโคร "อเนกประสงค์" เช่นM4นั้นไม่มีข้อจำกัด ( สมบูรณ์แบบตามทฤษฎีบททัวริง ) แต่ภาษามาโครของตัวประมวลผลล่วงหน้าของภาษา C นั้นมีข้อจำกัด ดังนั้นอัลกอริทึมใดๆ ที่แสดงในภาษาประมวลผลล่วงหน้าของภาษา Cจึงเป็นเพียง "อัลกอริทึมแบบง่าย"

ดูเพิ่มเติมที่ความสัมพันธ์ระหว่างระดับความซับซ้อน

ต่อไปนี้คือคุณลักษณะที่พึงประสงค์ของอัลกอริทึมที่กำหนดไว้อย่างดี ดังที่ได้กล่าวไว้ใน Scheider และ Gersting (1995):

• การดำเนินการที่ไม่คลุมเครือ: อัลกอริทึมต้องมีขั้นตอนที่เฉพาะเจาะจงและระบุไว้อย่างชัดเจน ขั้นตอนเหล่านั้นควรมีความแม่นยำเพียงพอที่จะระบุได้อย่างชัดเจนว่าต้องทำอะไรในแต่ละขั้นตอน
• เป็นระเบียบ: ลำดับการดำเนินการที่แน่นอนในอัลกอริทึมควรได้รับการกำหนดไว้อย่างชัดเจน
• ความเป็นไปได้: ขั้นตอนทั้งหมดของอัลกอริทึมควรเป็นไปได้ (หรือเรียกอีกอย่างว่าสามารถคำนวณได้อย่างมีประสิทธิภาพ )
• อินพุต: อัลกอริทึมควรสามารถรับชุดอินพุตที่กำหนดไว้อย่างชัดเจนได้
• ผลลัพธ์: อัลกอริทึมควรสร้างผลลัพธ์บางอย่างออกมา เพื่อให้สามารถใช้เหตุผลวิเคราะห์ความถูกต้องของอัลกอริทึมได้
• ความจำกัด: อัลกอริทึมควรสิ้นสุดหลังจากจำนวนคำสั่งที่จำกัด^{[ 2 ]}

คุณสมบัติของอัลกอริธึมเฉพาะที่อาจเป็นที่ต้องการ ได้แก่ ประสิทธิภาพ ด้านพื้นที่และเวลา ความสามารถในการใช้งานทั่วไป (เช่น สามารถจัดการกับข้อมูลป้อนเข้าได้หลายประเภท) หรือความแน่นอน

ในช่วงต้นปี ค.ศ. 1870 ดับเบิลยู. สแตนลีย์ เจวอนส์ได้นำเสนอ "เครื่องจักรตรรกะ" (เจวอนส์ 1880:200) สำหรับการวิเคราะห์ตรรกบทหรือรูปแบบตรรกะ อื่นๆ เช่น ข้อโต้แย้งที่ลดรูปเป็นสมการบูลีน โดยใช้สิ่งที่คูตูราต์ (1914) เรียกว่า " เปียโนตรรกะชนิดหนึ่ง... ความเท่าเทียมกันที่แสดงถึงข้อสมมติ... จะถูก "เล่น" บนแป้นพิมพ์คล้ายกับเครื่องพิมพ์ดีด... เมื่อข้อสมมติทั้งหมดถูก "เล่น" แล้ว แผงจะแสดงเฉพาะส่วนประกอบที่มีผลรวมเท่ากับ 1 นั่นคือ... ส่วนรวมทางตรรกะ วิธีการเชิงกลนี้มีข้อได้เปรียบเหนือวิธีการทางเรขาคณิตของเวนน์..." (คูตูราต์ 1914:75)

ในส่วนของจอห์น เวนน์นักตรรกศาสตร์ร่วมสมัยกับเจวอนส์ เขาไม่ค่อยประทับใจนัก โดยแสดงความคิดเห็นว่า "สำหรับผมแล้ว สิ่งประดิษฐ์ใดๆ ที่รู้จักในปัจจุบันหรือที่อาจจะค้นพบในอนาคตนั้น ไม่ สมควรได้รับชื่อว่าเครื่องจักรเชิงตรรกะ" (ตัวเอียงเพิ่มเติม เวนน์ 1881:120) แต่สิ่งที่สำคัญในเชิงประวัติศาสตร์ต่อแนวคิดที่กำลังพัฒนาของ "อัลกอริทึม" คือคำอธิบายของเขาเกี่ยวกับปฏิกิริยาเชิงลบที่มีต่อเครื่องจักรที่ "อาจมีประโยชน์อย่างแท้จริงโดยทำให้เราหลีกเลี่ยงการทำงานที่หลีกเลี่ยงไม่ได้ได้"

(1) "ประการแรก มีการนำเสนอข้อมูลของเราด้วยภาษาตรรกะที่ถูกต้อง"

(2) "ประการที่สอง เราต้องแปลงข้อความเหล่านี้ให้เป็นรูปแบบที่เครื่องยนต์สามารถทำงานได้ – ในกรณีนี้คือการลดข้อเสนอแต่ละข้อให้เหลือการปฏิเสธขั้นพื้นฐาน"

(3) "ประการที่สาม คือ การรวมหรือการดำเนินการเพิ่มเติมของสถานที่ของเราหลังจากการลดดังกล่าว"

(4) "สุดท้าย ผลลัพธ์จะต้องได้รับการตีความหรืออ่านออกมา ซึ่งโดยทั่วไปแล้วขั้นตอนสุดท้ายนี้เปิดโอกาสให้ใช้ทักษะและความเฉลียวฉลาดได้มาก"

เขาสรุปว่า "ผมมองไม่เห็นว่าเครื่องจักรใดจะช่วยเราได้ ยกเว้นในขั้นตอนที่สามนี้ ดังนั้นจึงดูน่าสงสัยมากว่าสิ่งใด ๆ ในลักษณะนี้สมควรได้รับการเรียกว่าเครื่องจักรเชิงตรรกะหรือไม่" (Venn 1881:119–121)

ส่วนนี้มีความยาวและรายละเอียดมากกว่าส่วนอื่นๆ เนื่องจากมีความสำคัญต่อหัวข้อ: คลีนเป็นคนแรกที่เสนอว่าการคำนวณ/การประมวลผลทั้งหมด — ทุกประเภททั้งหมด —สามารถคำนวณได้อย่างเทียบเท่ากัน โดย (i) ใช้ตัวดำเนินการแบบ เรียกซ้ำพื้นฐานห้า ตัว บวกกับตัวดำเนินการพิเศษหนึ่งตัวที่เรียกว่าตัวดำเนินการมิวหรือ (ii) คำนวณโดยการกระทำของเครื่องจักรทัวริงหรือแบบจำลองที่เทียบเท่า

นอกจากนี้ เขายังแสดงความคิดเห็นว่าทั้งสองอย่างนี้สามารถใช้เป็นนิยามของอัลกอริทึมได้

ผู้อ่านที่เพิ่งได้อ่านคำต่อไปนี้เป็นครั้งแรกอาจจะสับสน ดังนั้นจึงจำเป็นต้องมีคำอธิบายสั้นๆการคำนวณหมายถึงการทำด้วยมือ ส่วน การประมวลผลหมายถึง การประมวลผลด้วยเครื่องทัวริง (หรือเครื่องที่เทียบเท่า) (บางครั้งผู้เขียนอาจใช้คำสลับกัน) เราสามารถนึกถึง "ฟังก์ชัน" ได้ว่าเป็น "กล่องป้อนข้อมูล-แสดงผล" ที่บุคคลใส่จำนวนธรรมชาติที่เรียกว่า "อาร์กิวเมนต์" หรือ "พารามิเตอร์" (แต่เฉพาะจำนวนนับรวมถึง 0 ซึ่งเป็นจำนวนเต็มที่ไม่เป็นลบ) และได้ผลลัพธ์เป็นจำนวนเต็มที่ไม่เป็นลบเพียงจำนวนเดียว (โดยทั่วไปเรียกว่า "คำตอบ") ลองนึกถึง "กล่องฟังก์ชัน" ว่าเป็นเหมือนคนตัวเล็กๆ ที่กำลังคำนวณด้วยมือโดยใช้ "การเรียกซ้ำทั่วไป" หรือประมวลผลด้วยเครื่องทัวริง (หรือเครื่องที่เทียบเท่า)

คำว่า "สามารถคำนวณได้อย่างมีประสิทธิภาพ" นั้นมีความหมายกว้างกว่า และหมายถึง "สามารถคำนวณได้ด้วยกระบวนการวิธีการ เทคนิค ... อะไรก็ตาม..." คำว่า "การเรียกซ้ำทั่วไป" เป็นวิธีที่คลีนใช้เขียนสิ่งที่ปัจจุบันเรียกว่า "การเรียกซ้ำ" เฉยๆ อย่างไรก็ตาม "การเรียกซ้ำแบบดั้งเดิม" ซึ่งเป็นการคำนวณโดยใช้ตัวดำเนินการเรียกซ้ำทั้งห้าตัวนั้น เป็นรูปแบบการเรียกซ้ำที่ด้อยกว่า เนื่องจากขาดการเข้าถึงตัวดำเนินการมิว (mu) ตัวที่หก ซึ่งจำเป็นเฉพาะในบางกรณีเท่านั้น ดังนั้น ในชีวิตส่วนใหญ่จึงดำเนินไปได้โดยใช้เพียง "ฟังก์ชันเรียกซ้ำแบบดั้งเดิม" เท่านั้น

ในปี ค.ศ. 1943 คลีนได้เสนอสิ่งที่ต่อมาเป็นที่รู้จักในชื่อวิทยานิพนธ์ของเชิร์ช :

" วิทยานิพนธ์ที่ 1ฟังก์ชันที่คำนวณได้อย่างมีประสิทธิภาพทุกฟังก์ชัน (ภาคแสดงที่ตัดสินได้อย่างมีประสิทธิภาพ) เป็นฟังก์ชันเรียกซ้ำทั่วไป" (กล่าวไว้ครั้งแรกโดย Kleene ในปี 1943 (พิมพ์ซ้ำหน้า 274 ใน Davis, ed. The Undecidable ; ปรากฏแบบตรงตัวใน Kleene (1952) หน้า 300)

โดยสรุปแล้ว ในการคำนวณ ฟังก์ชัน ใดๆการดำเนินการเพียงอย่างเดียวที่บุคคลต้องการ (ในทางเทคนิคและในเชิงรูปแบบ) คือตัวดำเนินการพื้นฐาน 6 ตัวของฟังก์ชันเรียกซ้ำ "ทั่วไป" (ปัจจุบันเรียกว่าตัวดำเนินการของฟังก์ชันเรียกซ้ำมิว )

คำกล่าวแรกของ Kleene เกี่ยวกับเรื่องนี้อยู่ในหัวข้อ " 12. ทฤษฎีเชิงอัลกอริทึม " ต่อมาเขาได้ขยายความเพิ่มเติมในตำราของเขา (1952) ดังนี้:

"วิทยานิพนธ์ข้อที่ 1 และข้อผกผันของมันให้คำจำกัดความที่ชัดเจนของแนวคิดเกี่ยวกับขั้นตอนการคำนวณ (การตัดสินใจ) หรืออัลกอริทึมสำหรับกรณีของฟังก์ชัน (ภาคแสดง) ของจำนวนธรรมชาติ" (หน้า 301, เพิ่มตัวหนาเพื่อเน้น)

(การที่เขาใช้คำว่า "การตัดสินใจ" และ "ภาคแสดง" ขยายแนวคิดเรื่องความสามารถในการคำนวณไปสู่การจัดการสัญลักษณ์โดยทั่วไปมากขึ้น เช่นที่เกิดขึ้นใน "การพิสูจน์" ทางคณิตศาสตร์)

เรื่องนี้อาจฟังดูไม่น่ากลัวอย่างที่คิด – การเรียกซ้ำแบบ "ทั่วไป" เป็นเพียงวิธีการนำตัวดำเนินการทั้งห้าของฟังก์ชันเรียกซ้ำพื้นฐาน มาใช้ในการคำนวณทางคณิตศาสตร์ในชีวิตประจำวันของเรา โดยเพิ่ม ตัวดำเนินการมิว (mu)เข้าไปตามความจำเป็น ที่จริงแล้ว Kleene ได้ยกตัวอย่างฟังก์ชันเรียกซ้ำพื้นฐานไว้ 13 ตัวอย่าง และ Boolos–Burgess–Jeffrey ก็ได้เพิ่มตัวอย่างอื่นๆ อีกหลายตัวอย่าง ซึ่งส่วนใหญ่ผู้อ่านน่าจะคุ้นเคยกันดีอยู่แล้ว เช่น การบวก การลบ การคูณและการหาร การยกกำลัง ฟังก์ชัน CASE การต่อสตริง ฯลฯ สำหรับรายชื่อฟังก์ชันเรียกซ้ำพื้นฐานทั่วไป โปรดดูที่ " ฟังก์ชัน เรียกซ้ำพื้นฐานที่ใช้กันทั่วไปบางส่วน "

เหตุใดจึงใช้ฟังก์ชันเรียกซ้ำทั่วไปแทนที่จะใช้ฟังก์ชันเรียกซ้ำแบบดั้งเดิม?

Kleene และคณะ (ดู §55 ฟังก์ชันเวียนเกิดทั่วไป หน้า 270 ใน Kleene 1952) จำเป็นต้องเพิ่มตัวดำเนินการเวียนเกิดตัวที่หก เรียกว่า ตัวดำเนินการลดค่าต่ำสุด (เขียนว่า ตัวดำเนินการ μ หรือตัวดำเนินการมิว ) เนื่องจากAckermann (1925) ได้สร้างฟังก์ชันที่เติบโตอย่างมหาศาล— ฟังก์ชัน Ackermann—และRózsa Péter (1935) ได้สร้างวิธีการทั่วไปในการสร้างฟังก์ชันเวียนเกิดโดยใช้อาร์กิวเมนต์แนวทแยงของ Cantorซึ่งทั้งสองอย่างนี้ไม่สามารถอธิบายได้ด้วยตัวดำเนินการฟังก์ชันเวียนเกิดพื้นฐาน 5 ตัว สำหรับฟังก์ชัน Ackermann นั้น:

"...ในแง่หนึ่ง ความยาวของ อัลกอริธึ มการ คำนวณ ของฟังก์ชันแบบเรียกซ้ำที่ไม่ใช่ฟังก์ชันแบบเรียกซ้ำแบบดั้งเดิม จะเพิ่มขึ้นเร็วกว่าค่าของฟังก์ชันแบบเรียกซ้ำแบบดั้งเดิมใดๆ" (Kleene (1935) พิมพ์ซ้ำหน้า 246 ในThe Undecidableพร้อมเชิงอรรถที่ 13 เกี่ยวกับความจำเป็นของตัวดำเนินการเพิ่มเติม ตัวอักษรหนาเพิ่มเติม)

แต่ความจำเป็นในการใช้ตัวดำเนินการมิว (mu-operator) นั้นพบได้น้อย ดังที่ระบุไว้ข้างต้นโดยรายการการคำนวณทั่วไปของคลีน (Kleene) ผู้คนใช้ชีวิตประจำวันอย่างมีความสุขโดยการคำนวณฟังก์ชันแบบเรียกซ้ำพื้นฐานโดยไม่ต้องกลัวว่าจะเจอกับตัวเลขประหลาดที่เกิดจากฟังก์ชันของแอคเคอร์แมน (เช่นการยกกำลังเกินพิกัด )

ทฤษฎีบทของทิวริงตั้งสมมติฐานว่า "ฟังก์ชันที่คำนวณได้ทั้งหมด" สามารถคำนวณได้ด้วยแบบจำลองเครื่องจักรทิวริงและแบบจำลองที่เทียบเท่ากัน

เพื่อให้บรรลุเป้าหมายนี้อย่างมีประสิทธิภาพ คลีนได้ขยายแนวคิดของ "คำนวณได้" โดยขยายขอบเขตให้กว้างขึ้น—โดยอนุญาตให้รวม "ฟังก์ชันทั้งหมด" และ "ฟังก์ชันบางส่วน" เข้าไปในแนวคิดของ "ฟังก์ชัน" ฟังก์ชันทั้งหมดคือฟังก์ชันที่กำหนดได้สำหรับจำนวนธรรมชาติทั้งหมด (จำนวนเต็มบวก รวมทั้ง 0) ฟังก์ชันบางส่วนคือฟังก์ชันที่กำหนดได้สำหรับ จำนวนธรรมชาติ บางจำนวนแต่ไม่ใช่ทั้งหมด—การระบุ "บางจำนวน" ต้องมาจาก "จุดเริ่มต้น" ดังนั้น การรวม "ฟังก์ชันบางส่วน" จึงขยายแนวคิดของฟังก์ชันไปสู่ฟังก์ชันที่ "ไม่สมบูรณ์" ฟังก์ชันทั้งหมดและฟังก์ชันบางส่วนอาจคำนวณได้ด้วยมือหรือคำนวณด้วยเครื่องจักรก็ได้

ตัวอย่าง:

"ฟังก์ชัน": รวมถึง "การลบทั่วไปm  −  n " และ "การบวกm  +  n "

"ฟังก์ชันบางส่วน": "การลบทั่วไป" m  −  nหาค่าไม่ได้เมื่ออนุญาตเฉพาะจำนวนธรรมชาติ (จำนวนเต็มบวกและศูนย์) เป็นอินพุต – เช่น 6 − 7 หาค่าไม่ได้

ฟังก์ชันโดยรวม: "การบวก" m  +  nถูกกำหนดไว้สำหรับจำนวนเต็มบวกทุกจำนวนและศูนย์

ต่อไปนี้เราจะพิจารณาคำจำกัดความของ Kleene เกี่ยวกับ "ความสามารถในการคำนวณ" ในเชิงรูปแบบ:

นิยาม: "ฟังก์ชันบางส่วน φ สามารถคำนวณได้ถ้ามีเครื่องจักร M ที่สามารถคำนวณฟังก์ชันนั้นได้" (Kleene (1952) หน้า 360)

"นิยาม 2.5 ฟังก์ชันn -ary f ( x ₁ , ..., x _n ) เรียกว่าคำนวณได้บางส่วนถ้ามีเครื่องจักรทัวริง Z อยู่จริง โดยที่

f ( x ₁ , ..., x _n ) = Ψ _Z ^{( n )} ( x ₁ , ..., [ x _n )

ในกรณีนี้ เรากล่าวว่า [เครื่องจักร] Z คำนวณfหากf ( x ₁ , ..., x _n ) เป็นฟังก์ชันสมบูรณ์แล้ว จะเรียกว่าสามารถคำนวณได้ (Davis (1958) หน้า 10)

ด้วยเหตุนี้ เราจึงได้ข้อสรุปของทัวริง ดังนี้ :

"ฟังก์ชันทุกฟังก์ชันที่โดยธรรมชาติแล้วจะถือว่าสามารถคำนวณได้นั้น สามารถคำนวณได้...โดยเครื่องจักรเครื่องใดเครื่องหนึ่งของเขา..." (Kleene (1952) หน้า 376)

แม้ว่า Kleene จะไม่ได้ยกตัวอย่าง "ฟังก์ชันที่คำนวณได้" แต่ก็มีผู้อื่นยกตัวอย่างไว้ เช่น Davis (1958) ได้นำเสนอตาราง Turing สำหรับฟังก์ชัน Constant, Successor และ Identity ซึ่งเป็นหนึ่งในห้าตัวดำเนินการของฟังก์ชัน เรียกซ้ำแบบดั้งเดิม

สามารถคำนวณได้ด้วยเครื่องจักรทัวริง:

การบวก (หรือฟังก์ชันค่าคงที่หากตัวถูกดำเนินการตัวใดตัวหนึ่งเป็น 0)

เพิ่มค่า (ฟังก์ชันสืบทอด)

การลบแบบทั่วไป (ซึ่งกำหนดไว้เฉพาะเมื่อx ≥ y เท่านั้น ) ดังนั้น " x  −  y " จึงเป็นตัวอย่างของฟังก์ชันที่คำนวณได้บางส่วน

การลบที่ถูกต้องx ┴ y (ตามที่นิยามไว้ข้างต้น)

ฟังก์ชันเอกลักษณ์ : สำหรับแต่ละi จะมี ฟังก์ชัน U _Z ⁿ = Ψ _Z ⁿ ( x ₁ , ..., x _n ) ที่ดึงx _iออกจากเซตของอาร์กิวเมนต์ ( x ₁ , ..., x _n )

การคูณ

Boolos–Burgess–Jeffrey (2002) ให้คำอธิบายเชิงร้อยแก้วเกี่ยวกับเครื่องจักรทัวริงไว้ดังนี้:

การเพิ่มเป็นสองเท่า: 2 เพนนี

ความเท่าเทียมกัน

ส่วนที่เพิ่มเข้าไป

การคูณ

ในส่วนของเครื่องนับ (counter machine)ซึ่ง เป็นแบบจำลอง เครื่องจักรเชิงนามธรรมที่เทียบเท่ากับเครื่องจักรทัวริง (Turing machine):

ตัวอย่างที่คำนวณได้ด้วยเครื่องลูกคิด (ดู Boolos–Burgess–Jeffrey (2002))

ส่วนที่เพิ่มเข้าไป

การคูณ

การยกกำลัง: (คำอธิบายขั้นตอนวิธีในรูปแบบผังงาน/แผนภาพบล็อก)

การสาธิตความสามารถในการคำนวณโดยเครื่องลูกคิด (Boolos–Burgess–Jeffrey (2002)) และโดยเครื่องนับ (Minsky 1967):

ตัวดำเนินการฟังก์ชันแบบเรียกซ้ำทั้งหก:

1. ฟังก์ชันศูนย์
2. ฟังก์ชันสืบทอด
3. ฟังก์ชันเอกลักษณ์
4. ฟังก์ชันองค์ประกอบ
5. การเรียกซ้ำแบบดั้งเดิม (อุปนัย)
6. การลดให้เหลือน้อยที่สุด

ข้อเท็จจริงที่ว่าแบบจำลองลูกคิด/เครื่องนับสามารถจำลองฟังก์ชันเวียนเกิดได้นั้น เป็นข้อพิสูจน์ว่า: ถ้าฟังก์ชันนั้น "คำนวณได้ด้วยเครื่องจักร" แล้ว ฟังก์ชันนั้นก็ "คำนวณได้ด้วยมือโดยใช้การเวียนเกิดบางส่วน" ทฤษฎีบทที่ XXIX ของ Kleene :

" ทฤษฎีบทที่ XXIX: "ฟังก์ชันย่อยที่คำนวณได้ทุกฟังก์ชัน φ เป็นฟังก์ชันย่อยแบบเรียกซ้ำ... " (ตัวเอียงในต้นฉบับ หน้า 374)

ส่วนกลับปรากฏในทฤษฎีบทที่ 28 ของเขา เมื่อรวมกันแล้ว สิ่งเหล่านี้ประกอบกันเป็นหลักฐานพิสูจน์ความเท่าเทียมกันของพวกมัน ซึ่งก็คือทฤษฎีบทที่ 30 ของคลีน

ด้วยทฤษฎีบท XXX ของเขา คลีนพิสูจน์ความเท่าเทียมกันของ "วิทยานิพนธ์" ทั้งสอง ได้แก่ วิทยานิพนธ์ของเชิร์ชและวิทยานิพนธ์ของทัวริง (คลีนสามารถตั้งสมมติฐาน (คาดเดา) เกี่ยวกับความจริงของวิทยานิพนธ์ทั้งสองได้เท่านั้น – เขายังไม่ได้พิสูจน์ )

ทฤษฎีบท XXX: ฟังก์ชันบางส่วนประเภทต่อไปนี้ ... มีสมาชิกเหมือนกัน: (a) ฟังก์ชันเวียนเกิดบางส่วน (b) ฟังก์ชันที่คำนวณได้ ... (หน้า 376)

นิยามของ "ฟังก์ชันเวียนเกิดบางส่วน": "ฟังก์ชันเวียนเกิดบางส่วน φ เรียกว่าฟังก์ชันเวียนเกิดบางส่วนใน [ฟังก์ชันเวียนเกิดบางส่วน] ψ ₁ , ... ψ _nถ้ามีระบบสมการ E ที่กำหนด φ แบบเวียนเกิดจาก [ฟังก์ชันเวียนเกิดบางส่วน] ψ ₁ , ... ψ _n " (หน้า 326)

ดังนั้น ตามทฤษฎีบท XXX ของคลีน: ไม่ว่าวิธีการใดในการสร้างตัวเลขจากตัวเลขป้อนเข้า—ฟังก์ชันเวียนเกิดที่คำนวณด้วยมือหรือคำนวณโดยเครื่องจักรทัวริงหรือเทียบเท่า—จะส่งผลให้ได้ " ฟังก์ชัน ที่คำนวณได้จริง " หากเรายอมรับสมมติฐานที่ว่าการ คำนวณ ทุกอย่างสามารถทำได้โดยวิธีใดวิธีหนึ่งอย่างเทียบเท่ากัน เราก็ยอมรับทั้งทฤษฎีบท XXX ของคลีน (ความเทียบเท่า) และวิทยานิพนธ์ของเชิร์ช-ทัวริง (สมมติฐานของ "ทุกอย่าง") แล้ว

แนวคิดในการแยกวิทยานิพนธ์ของ Church และ Turing ออกจาก "วิทยานิพนธ์ Church–Turing" ปรากฏให้เห็นไม่เพียงแต่ใน Kleene (1952) เท่านั้น แต่ยังรวมถึง Blass-Gurevich (2003) ด้วย อย่างไรก็ตาม แม้จะมีความเห็นพ้องกัน แต่ก็มีความเห็นที่แตกต่างกันเช่นกัน:

"...เราไม่เห็นด้วยกับคลีนที่กล่าวว่าแนวคิดเรื่องอัลกอริทึมเป็นที่เข้าใจกันดีนัก อันที่จริง แนวคิดเรื่องอัลกอริทึมในปัจจุบันนั้นมีความซับซ้อนและหลากหลายกว่าในสมัยของทัวริงเสียอีก และยังมีอัลกอริทึมหลายประเภท ทั้งแบบสมัยใหม่และแบบคลาสสิก ที่ทัวริงไม่ได้กล่าวถึงโดยตรง เช่น อัลกอริทึมที่โต้ตอบกับสภาพแวดล้อม อัลกอริทึมที่มีอินพุตเป็นโครงสร้างนามธรรม และอัลกอริทึมเชิงเรขาคณิต หรือโดยทั่วไปแล้ว อัลกอริทึมที่ไม่ใช่แบบไม่ต่อเนื่อง" (Blass-Gurevich (2003) หน้า 8, เน้นตัวหนา)

Andrey Markov Jr. (1954) ได้ให้คำจำกัดความของอัลกอริทึมไว้ดังนี้:

"1. ในทางคณิตศาสตร์ "อัลกอริทึม" โดยทั่วไปหมายถึงสูตรที่แน่นอนซึ่งกำหนดกระบวนการคำนวณที่นำไปสู่ผลลัพธ์ที่ต้องการจากข้อมูลเริ่มต้นต่างๆ..."

"คุณลักษณะสามประการต่อไปนี้เป็นลักษณะเฉพาะของอัลกอริทึมและเป็นตัวกำหนดบทบาทของอัลกอริทึมในวิชาคณิตศาสตร์:

"ก) ความแม่นยำของคำสั่ง ซึ่งไม่เปิดโอกาสให้เกิดความไม่แน่นอน และความเข้าใจได้โดยทั่วไป — ความแน่นอนของอัลกอริทึม"

"ข) ความเป็นไปได้ในการเริ่มต้นด้วยข้อมูลเริ่มต้น ซึ่งอาจแตกต่างกันไปภายในขอบเขตที่กำหนด - ความเป็นทั่วไปของอัลกอริทึม"

"ค) การวางแนวทางของอัลกอริทึมไปสู่การได้มาซึ่งผลลัพธ์ที่ต้องการ ซึ่งได้มาจริง ๆ ในท้ายที่สุดด้วยข้อมูลเริ่มต้นที่เหมาะสม — ความน่าเชื่อถือของอัลกอริทึม" (หน้า 1)

เขายอมรับว่าคำจำกัดความนี้ "ไม่ได้มุ่งหมายความแม่นยำทางคณิตศาสตร์" (หน้า 1) งานเขียนเชิงวิชาการของเขาในปี 1954 เป็นความพยายามที่จะกำหนดความหมายของอัลกอริทึมให้แม่นยำยิ่งขึ้น เขาเห็นว่าคำจำกัดความที่ได้—อัลกอริทึม "ปกติ" ของเขา—นั้น "เทียบเท่ากับแนวคิดของฟังก์ชันแบบเรียกซ้ำ " (หน้า 3) คำจำกัดความของเขามีองค์ประกอบหลักสี่ส่วน (บทที่ II.3 หน้า 63 เป็นต้นไป):

"1. ขั้นตอนพื้นฐานที่แยกจากกัน โดยแต่ละขั้นตอนจะดำเนินการตามกฎการแทนที่ข้อใดข้อหนึ่ง... [กฎที่ให้ไว้ในตอนต้น]

"2. ... ขั้นตอนที่มีลักษณะเฉพาะในระดับท้องถิ่น ... [ดังนั้นอัลกอริทึมจะไม่เปลี่ยนแปลงสัญลักษณ์มากกว่าจำนวนที่กำหนดไว้ทางด้านซ้ายหรือด้านขวาของคำ/สัญลักษณ์ที่สังเกต]

"3. กฎสำหรับสูตรการแทนที่ ... [เขาเรียกรายการเหล่านี้ว่า "โครงร่าง" ของอัลกอริทึม]

"4. ...วิธีการแยกแยะ "การแทนที่ขั้นสุดท้าย" [เช่น สถานะ "สุดท้าย" ที่สามารถแยกแยะได้]

ในบทนำ มาร์คอฟตั้งข้อสังเกตว่า "ความสำคัญทั้งหมดสำหรับคณิตศาสตร์" ของความพยายามที่จะกำหนดอัลกอริทึมให้แม่นยำยิ่งขึ้นนั้นจะ "เกี่ยวข้องกับปัญหาของรากฐานเชิงสร้างสรรค์สำหรับคณิตศาสตร์" (หน้า 2) เอียน สจ๊วต (ดู Encyclopædia Britannica) มีความเชื่อที่คล้ายคลึงกัน: "... การวิเคราะห์เชิงสร้างสรรค์นั้นมีลักษณะทางอัลกอริทึมคล้ายคลึงกับวิทยาศาสตร์คอมพิวเตอร์มาก..." สำหรับข้อมูลเพิ่มเติม โปรดดูคณิตศาสตร์เชิงสร้างสรรค์และสัญชาตญาณนิยม

ความสามารถในการจำแนกและตำแหน่งที่ตั้ง : แนวคิดทั้งสองนี้ปรากฏขึ้นครั้งแรกในสมัยของทิวริง (ค.ศ. 1936–1937)

"ช่องสี่เหลี่ยมที่สังเกตใหม่จะต้องสามารถจดจำได้ทันทีโดยคอมพิวเตอร์ [ sic : ในปี 1936 คอมพิวเตอร์ถือเป็นบุคคล] ผมคิดว่าเป็นการสมเหตุสมผลที่จะสมมติว่าช่องสี่เหลี่ยมเหล่านั้นจะต้องอยู่ห่างจากช่องสี่เหลี่ยมที่สังเกตได้ก่อนหน้านี้ไม่เกินจำนวนคงที่ที่กำหนดไว้ สมมติว่าช่องสี่เหลี่ยมที่สังเกตใหม่แต่ละช่องอยู่ภายในระยะ L ช่องจากช่องสี่เหลี่ยมที่สังเกตได้ก่อนหน้านี้ช่องใดช่องหนึ่ง" (Turing (1936) หน้า 136 ใน Davis ed. Undecidable )

แนวคิดเรื่องความเป็นท้องถิ่นปรากฏเด่นชัดในงานของ Gurevich และ Gandy (1980) (ซึ่ง Gurevich อ้างถึง) "หลักการข้อที่สี่สำหรับกลไก" ของ Gandy คือ "หลักการของความเป็นเหตุเป็นผลในระดับท้องถิ่น":

“ตอนนี้เรามาถึงหลักการที่สำคัญที่สุดของเราแล้ว ในการวิเคราะห์ของทัวริง ข้อกำหนดที่ว่าการกระทำขึ้นอยู่กับส่วนที่จำกัดของบันทึกนั้น มาจากข้อจำกัดของมนุษย์ เราจึงแทนที่ข้อจำกัดนี้ด้วยข้อจำกัดทางกายภาพ ซึ่งเราเรียกว่าหลักการของสาเหตุเฉพาะที่เหตุผลของหลักการนี้มาจากการแพร่กระจายของผลกระทบและสัญญาณที่มีความเร็วจำกัด ฟิสิกส์ร่วมสมัยปฏิเสธความเป็นไปได้ของการกระทำทันทีในระยะไกล” (Gandy (1980) หน้า 135 ใน J. Barwise et al.)

1936 : คำกล่าวอ้างที่มีชื่อเสียงพอสมควรจากเคิร์ท เกอเดลปรากฏใน "หมายเหตุเพิ่มเติมในการตรวจทาน [ของฉบับพิมพ์ภาษาเยอรมันดั้งเดิม] ในบทความของเขาเรื่อง "ว่าด้วยความยาวของการพิสูจน์" ซึ่งแปลโดยมาร์ติน เดวิสปรากฏในหน้า 82–83 ของ หนังสือ The Undecidableนักเขียนหลายคน เช่น คลีน, กูเรวิช, แกนดี เป็นต้น ได้อ้างอิงคำกล่าวต่อไปนี้:

"ดังนั้น แนวคิดของ 'คำนวณได้' จึงเป็น 'สัมบูรณ์' ในความหมายที่แน่นอน ในขณะที่แนวคิดเชิงอภิคณิตศาสตร์อื่นๆ ที่คุ้นเคยเกือบทั้งหมด (เช่น พิสูจน์ได้ นิยามได้ ฯลฯ) ขึ้นอยู่กับระบบที่ใช้ในการนิยามแนวคิดเหล่านั้นอย่างเป็นสาระสำคัญ" (หน้า 83)

ปี 1963 : ใน "หมายเหตุ" ลงวันที่ 28 สิงหาคม 1963 ที่เพิ่มเข้ามาในบทความที่มีชื่อเสียงของเขาเรื่อง On Formally Undecidable Propositions (1931) เกอเดลได้กล่าวไว้ (ในเชิงอรรถ) ว่าเขาเชื่อว่า " ระบบที่เป็นทางการ " มี "คุณสมบัติเฉพาะที่ว่า การให้เหตุผลในระบบเหล่านั้น โดยหลักการแล้ว สามารถถูกแทนที่ได้อย่างสมบูรณ์ด้วยอุปกรณ์เชิงกล" (หน้า 616 ใน van Heijenoort) "...เนื่องจากผลงานของ AM Turing ทำให้สามารถให้คำจำกัดความที่แม่นยำและเพียงพออย่างไม่ต้องสงสัยของแนวคิดทั่วไปของระบบที่เป็นทางการได้แล้ว [และ] สามารถสร้างทฤษฎีบทที่ VI และ XI ในรูปแบบทั่วไปได้อย่างสมบูรณ์" (หน้า 616) ในหมายเหตุปี 1964 ในงานอื่น เขาก็แสดงความคิดเห็นเดียวกันนี้อย่างหนักแน่นและละเอียดมากขึ้น

1964 : ในเอกสารเพิ่มเติมที่ลงวันที่ 1964 ซึ่งแนบมากับบทความที่นำเสนอต่อสถาบันเพื่อการศึกษาขั้นสูงในฤดูใบไม้ผลิปี 1934 เกอเดลได้ขยายความเชื่อของเขาว่า "ระบบที่เป็นทางการ" คือระบบที่สามารถทำให้เป็นเครื่องจักรได้:

"ผลสืบเนื่องมาจากความก้าวหน้าในภายหลัง โดยเฉพาะอย่างยิ่งจากข้อเท็จจริงที่ว่า ด้วยผลงานของ เอ.เอ็ม. ทัวริง ทำให้สามารถให้คำจำกัดความที่แม่นยำและเพียงพออย่างไม่ต้องสงสัยของแนวคิดทั่วไปของระบบที่เป็นทางการได้แล้ว... ผลงานของทัวริงได้วิเคราะห์แนวคิดของ "กระบวนการเชิงกล" (หรือที่รู้จักกันในชื่อ "อัลกอริทึม" หรือ "กระบวนการคำนวณ" หรือ "กระบวนการเชิงผสมแบบจำกัด") แนวคิดนี้แสดงให้เห็นว่าเทียบเท่ากับ "เครื่องจักรทัวริง"* ระบบที่เป็นทางการสามารถนิยามได้ง่ายๆ ว่าเป็นกระบวนการเชิงกลใดๆ สำหรับการสร้างสูตรที่เรียกว่าสูตรที่พิสูจน์ได้..." (หน้า 72 ในMartin Davis ed. The Undecidable : "Postscriptum" to "On Undecidable Propositions of Formal Mathematical Systems" ปรากฏในหน้า 39, loc. cit.)

เครื่องหมาย * แสดงถึงเชิงอรรถที่ Gödel อ้างอิงถึงบทความของAlan Turing (1937) และEmil Post (1936) จากนั้นจึงกล่าวข้อความที่น่าสนใจดังต่อไปนี้:

"ส่วนนิยามที่เทียบเท่ากันก่อนหน้านี้ของความสามารถในการคำนวณ ซึ่งอย่างไรก็ตามไม่เหมาะสมกับวัตถุประสงค์ของเรามากนัก โปรดดูAlonzo Church , Am. J. Math., vol. 58 (1936) [ปรากฏในThe Undecidableหน้า 100-102])

นิยามของเชิร์ชครอบคลุมถึงสิ่งที่เรียกว่า " การเรียกซ้ำ " และ " แคลคูลัสแลมบ์ดา " (เช่น ฟังก์ชันที่กำหนดได้ด้วย λ) หมายเหตุเชิงอรรถที่ 18 ของเขากล่าวว่า เขาได้หารือเกี่ยวกับความสัมพันธ์ระหว่าง "ความสามารถในการคำนวณอย่างมีประสิทธิภาพ" และ "การเรียกซ้ำ" กับเกอเดล แต่เขาตั้งคำถามเกี่ยวกับ "ความสามารถในการคำนวณอย่างมีประสิทธิภาพ" และ "การกำหนดได้ด้วย λ" อย่างอิสระ:

"ตอนนี้เรากำหนดแนวคิด...ของฟังก์ชันจำนวนเต็มบวกที่คำนวณได้อย่างมีประสิทธิภาพโดยการระบุให้เหมือนกับแนวคิดของฟังก์ชันเวียนเกิดของจำนวนเต็มบวก¹⁸ (หรือของฟังก์ชันจำนวนเต็มบวกที่กำหนดได้ด้วย λ)

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

"ในทางกลับกัน มันก็เป็นความจริงเช่นกัน..." (หน้า 100, สิ่งที่ไม่สามารถตัดสินได้)

จากข้อความนี้และข้อความต่อไปนี้ ดูเหมือนว่าสำหรับเกอเดลแล้ว เครื่องจักรทัวริงนั้นเพียงพอแล้ว และแคลคูลัสแลมบ์ดานั้น "เหมาะสมน้อยกว่ามาก" เขายังกล่าวต่อไปอีกว่า ในส่วนของข้อจำกัดของเหตุผลของมนุษย์นั้น ยังไม่มีข้อสรุปที่แน่ชัด

("โปรดทราบว่าคำถามที่ว่ามีกระบวนการที่ไม่ใช่เชิงกลแบบจำกัด** ที่ไม่เทียบเท่ากับอัลกอริทึมใด ๆ หรือไม่นั้น ไม่มีส่วนเกี่ยวข้องใด ๆ กับความเพียงพอของคำจำกัดความของ "ระบบที่เป็นทางการ" และ "กระบวนการเชิงกล") (หน้า 72, อ้างอิงเดิม)

"(สำหรับทฤษฎีและกระบวนการในความหมายทั่วไปที่ระบุไว้ในเชิงอรรถ ** สถานการณ์อาจแตกต่างออกไป โปรดทราบว่าผลลัพธ์ที่กล่าวถึงในหมายเหตุท้ายบทไม่ได้กำหนดขอบเขตใดๆ สำหรับพลังแห่งเหตุผลของมนุษย์ แต่เป็นการกำหนดขอบเขตสำหรับศักยภาพของรูปแบบนิยมบริสุทธิ์ในคณิตศาสตร์) (หน้า 73 อ้างอิงเดิม)

หมายเหตุ **: "เช่น กรณีที่เกี่ยวข้องกับการใช้คำศัพท์เชิงนามธรรมโดยพิจารณาจากความหมายของคำเหล่านั้น ดูบทความของฉันใน Dial. 12(1958), หน้า 280" (หมายเหตุนี้ปรากฏในหน้า 72, loc. cit)

มินสกี (1967) กล่าวอย่างตรงไปตรงมาว่า "อัลกอริทึมคือ "กระบวนการที่มีประสิทธิภาพ" และปฏิเสธที่จะใช้คำว่า "อัลกอริทึม" อีกต่อไปในเนื้อหาของเขา อันที่จริง ดัชนีของเขาแสดงให้เห็นอย่างชัดเจนว่าเขารู้สึกอย่างไรเกี่ยวกับ "อัลกอริทึมคำพ้องความหมายของกระบวนการที่มีประสิทธิภาพ" (หน้า 311):

"ในส่วนต่อไป เราจะใช้คำหลัง [ ขั้นตอนที่มีประสิทธิภาพ ] คำทั้งสองมีความหมายใกล้เคียงกัน แต่มีนัยยะความหมายที่แตกต่างกันเล็กน้อยในบริบทต่างๆ โดยเฉพาะอย่างยิ่งสำหรับคำว่า 'อัลกอริทึม'" (ตัวเอียงในต้นฉบับ หน้า 105)

นักเขียนท่านอื่น ๆ (เช่น Knuth ด้านล่าง) ใช้คำว่า "กระบวนการที่มีประสิทธิภาพ" ซึ่งทำให้เกิดคำถามว่า: แนวคิดเรื่อง "กระบวนการที่มีประสิทธิภาพ" ของ Minsky คืออะไร? เขาเริ่มต้นด้วย:

"...ชุดกฎเกณฑ์ที่บอกเราอย่างแม่นยำในแต่ละช่วงเวลาว่าควรประพฤติตนอย่างไร" (หน้า 106)

แต่เขายอมรับว่าเรื่องนี้อาจถูกวิพากษ์วิจารณ์ได้:

"...คำวิจารณ์ที่ว่าการตีความกฎนั้นขึ้นอยู่กับบุคคลหรือตัวแทนบางคน" (หน้า 106)

การปรับปรุงของเขาคืออะไร? คือการ "ระบุ รายละเอียดของกลไกที่จะตีความกฎเหล่านั้นไปพร้อมกับคำแถลงของกฎ" เพื่อหลีกเลี่ยงกระบวนการที่ "ยุ่งยาก" ในการ "ทำซ้ำเช่นนี้สำหรับแต่ละขั้นตอน" เขาหวังที่จะระบุ " กลุ่มของกลไกที่ปฏิบัติตามกฎอย่างเป็นเอกภาพ" "สูตร" ของเขาคือ :

"(1) ภาษาที่ใช้ในการแสดงชุดกฎพฤติกรรม และ

“(2) เครื่องจักร เครื่องเดียวที่สามารถตีความคำสั่งในภาษาและดำเนินการตามขั้นตอนของแต่ละกระบวนการที่ระบุไว้” (ตัวเอียงในต้นฉบับ คำพูดทั้งหมดในย่อหน้านี้ หน้า 107)

อย่างไรก็ตาม ในท้ายที่สุด เขายังคงกังวลว่า "เรื่องนี้ยังคงมีแง่มุมที่เป็นอัตวิสัยอยู่ ผู้คนต่างกันอาจไม่เห็นด้วยว่าขั้นตอนใดควรเรียกว่ามีประสิทธิภาพ" (หน้า 107)

แต่ Minsky ก็ไม่ย่อท้อ เขาจึงนำเสนอ "การวิเคราะห์กระบวนการคำนวณของ Turing" (บทที่ 5.2 ของเขา) ทันที โดยเขาอ้างถึงสิ่งที่เขาเรียกว่า " วิทยานิพนธ์ ของ Turing "

"กระบวนการใดๆ ก็ตามที่สามารถเรียกได้ว่าเป็นขั้นตอนที่มีประสิทธิภาพตามธรรมชาติ สามารถเกิดขึ้นได้ด้วยเครื่องจักรทัวริง" (หน้า 108. (มินสกีแสดงความคิดเห็นว่าในรูปแบบทั่วไปนี้เรียกว่า " วิทยานิพนธ์ของเชิร์ช ")

หลังจากวิเคราะห์ "ข้อโต้แย้งของทัวริง" (บทที่ 5.3 ของเขา) เขาตั้งข้อสังเกตว่า "ความเท่าเทียมกันของสูตรเชิงสัญชาตญาณหลายประการ" ของทัวริง เชิร์ช คลีน โพสต์ และสมุลเลียน "...นำเราไปสู่การสันนิษฐานว่าแท้จริงแล้วมีแนวคิด 'เชิงวัตถุวิสัย' หรือ 'เชิงสัมบูรณ์' อยู่" ดังที่โรเจอร์ส [1959] กล่าวไว้ว่า:

"ในแง่นี้ แนวคิดเรื่องฟังก์ชันที่คำนวณได้อย่างมีประสิทธิภาพเป็นหนึ่งในแนวคิด 'สัมบูรณ์' เพียงไม่กี่อย่างที่เกิดขึ้นจากงานวิจัยสมัยใหม่ในรากฐานของคณิตศาสตร์" (มินสกี หน้า 111 อ้างอิงจาก โรเจอร์ส ฮาร์ทลีย์ จูเนียร์ (1959) ทฤษฎีปัจจุบันของการคำนวณของเครื่องจักรทัวริงวารสาร SIAM 7, 114-130)

ในหนังสือ Theory of Recursive Functions and Effective Computability ปี 1967 ของ Hartley Rogers เขาได้อธิบายลักษณะของ "อัลกอริทึม" อย่างคร่าวๆ ว่าเป็น "กระบวนการทางธุรการ (เช่น กระบวนการที่กำหนดได้แน่นอน กระบวนการทางบัญชี) ... ที่นำไปใช้กับ ... ข้อมูลป้อนเข้า เชิงสัญลักษณ์ และในที่สุดจะให้ผลลัพธ์ เชิงสัญลักษณ์ที่สอดคล้องกันสำหรับข้อมูลป้อนเข้าแต่ละรายการ " (หน้า 1) จากนั้นเขาก็อธิบายแนวคิดนี้ "ในเชิงประมาณและโดยสัญชาตญาณ" ว่ามี "คุณลักษณะ" 10 ประการ โดย 5 ประการนั้น เขาอ้างว่า "นักคณิตศาสตร์แทบทุกคนจะเห็นด้วย" (หน้า 2) ส่วนอีก 5 ประการที่เหลือ เขาอ้างว่า "ไม่ชัดเจนเท่ากับข้อ 1 ถึง 5 และเราอาจพบข้อตกลงทั่วไปน้อยกว่า" (หน้า 3)

5 ข้อที่ "เห็นได้ชัด" ได้แก่:

• 1. อัลกอริทึม คือชุดคำสั่งที่มีขนาดจำกัด
• 2. มีตัวแทนประมวลผลที่มีประสิทธิภาพอยู่
• 3. "มีสิ่งอำนวยความสะดวกสำหรับการสร้าง จัดเก็บ และเรียกใช้ขั้นตอนในการคำนวณ"
• 4. จากเงื่อนไขข้อ #1 และ #2 ตัวแทนจะคำนวณใน "ลักษณะทีละขั้นตอนแบบไม่ต่อเนื่อง" โดยไม่ใช้วิธีการต่อเนื่องหรืออุปกรณ์อนาล็อก
• 5. ตัวแทนการคำนวณดำเนินการคำนวณต่อไป "โดยไม่ต้องอาศัยวิธีการหรืออุปกรณ์สุ่ม เช่น ลูกเต๋า" (ในเชิงอรรถ โรเจอร์สตั้งคำถามว่าข้อ 4 และข้อ 5 เหมือนกันจริงหรือไม่)

ประเด็นที่เหลืออีก 5 ประเด็นที่เขาเปิดโอกาสให้มีการอภิปราย ได้แก่:

• 6. ไม่มีข้อจำกัดตายตัวเกี่ยวกับขนาดของข้อมูลนำเข้า
• 7. ไม่มีข้อจำกัดตายตัวเกี่ยวกับขนาดของชุดคำสั่ง
• 8. ไม่มีข้อจำกัดตายตัวเกี่ยวกับปริมาณพื้นที่จัดเก็บข้อมูลในหน่วยความจำ
• 9. ขอบเขตจำกัดคงที่ของความจุหรือความสามารถของตัวแทนการคำนวณ (โรเจอร์สยกตัวอย่างกลไกง่ายๆ ที่คล้ายกับเครื่องจักรโพสต์ทัวริงหรือเครื่องจักรนับจำนวน )
• 10. ข้อจำกัดเกี่ยวกับระยะเวลาในการคำนวณ -- "เราควรจะมีแนวคิดบางอย่าง 'ล่วงหน้า' ไหมว่าการคำนวณจะใช้เวลานานเท่าใด?" (หน้า 5) โรเจอร์สต้องการ "เพียงให้การคำนวณสิ้นสุดลงหลังจากจำนวนขั้นตอนที่จำกัดเท่านั้น เราไม่ได้ยืนยันถึงความสามารถในการประมาณจำนวนนี้ล่วงหน้า" (หน้า 5)

Knuth (1968, 1973) ได้ระบุคุณสมบัติห้าประการที่ได้รับการยอมรับอย่างกว้างขวางว่าเป็นข้อกำหนดสำหรับอัลกอริทึม:

1. ความจำกัด : "อัลกอริทึมจะต้องสิ้นสุดลงหลังจากดำเนินการครบจำนวนขั้นตอนที่จำกัด ... จำนวนที่จำกัด มาก ๆจำนวนที่สมเหตุสมผล"
2. ความชัดเจน : "แต่ละขั้นตอนของอัลกอริทึมจะต้องถูกกำหนดไว้อย่างแม่นยำ การกระทำที่จะต้องดำเนินการจะต้องระบุอย่างชัดเจนและไม่คลุมเครือสำหรับแต่ละกรณี"
3. ข้อมูลนำเข้า : "...ปริมาณที่ป้อนให้ในเบื้องต้นก่อนที่อัลกอริทึมจะเริ่มทำงาน ข้อมูลนำเข้าเหล่านี้ได้มาจากชุดวัตถุที่ระบุไว้"
4. ผลลัพธ์ : "...ปริมาณที่มีความสัมพันธ์ที่กำหนดไว้กับปัจจัยนำเข้า"
5. ประสิทธิภาพ : "...การดำเนินการทั้งหมดที่จะต้องกระทำในอัลกอริทึมจะต้องเป็นพื้นฐานมากพอที่ในทางทฤษฎีแล้วสามารถทำได้อย่างแม่นยำและภายในระยะเวลาที่จำกัดโดยมนุษย์โดยใช้กระดาษและดินสอ"

Knuth ยกตัวอย่างอัลกอริทึมแบบยุคลิดในการหาตัวหารร่วมมากที่สุด ของ จำนวนธรรมชาติสอง จำนวน (ดู Knuth เล่ม 1 หน้า 2)

Knuth ยอมรับว่า แม้คำอธิบายเกี่ยวกับอัลกอริทึมของเขาจะเข้าใจได้ง่าย แต่ก็ขาดความเข้มงวดในเชิงรูปแบบ เนื่องจากไม่ชัดเจนนักว่า "กำหนดไว้อย่างแม่นยำ" หรือ "ระบุอย่างเข้มงวดและไม่คลุมเครือ" หรือ "พื้นฐานเพียงพอ" หมายถึงอะไร เป็นต้น เขาพยายามในทิศทางนี้ในเล่มแรกของเขา โดยกำหนดรายละเอียดสิ่งที่เขาเรียกว่า " ภาษาเครื่อง " สำหรับ " MIX ในตำนาน ...คอมพิวเตอร์โพลีอันแซทูเรตเครื่องแรกของโลก" (หน้า 120 เป็นต้นไป) อัลกอริทึมหลายตัวในหนังสือของเขาเขียนด้วยภาษา MIX นอกจากนี้เขายังใช้แผนภาพต้นไม้แผนภาพการไหลและแผนภาพ สถานะ ด้วย

"ความดี" ของอัลกอริทึม "อัลกอริทึมที่ดีที่สุด" : คนูธกล่าวว่า "ในทางปฏิบัติ เราไม่เพียงต้องการอัลกอริทึมเท่านั้น แต่เราต้องการ อัลกอริทึม ที่ดีด้วย ..." เขาเสนอว่าเกณฑ์บางประการของความดีของอัลกอริทึม ได้แก่ จำนวนขั้นตอนในการทำงานของอัลกอริทึม "ความสามารถในการปรับตัวให้เข้ากับคอมพิวเตอร์ ความเรียบง่ายและความสง่างาม ฯลฯ" เมื่อมีอัลกอริทึมหลายตัวที่ใช้ในการคำนวณเดียวกัน อัลกอริทึมใด "ดีที่สุด"? เขาเรียกการสอบถามประเภทนี้ว่า "การวิเคราะห์อัลกอริทึม: เมื่อกำหนดอัลกอริทึมแล้ว จะต้องพิจารณาคุณลักษณะด้านประสิทธิภาพของมัน" (ข้อความทั้งหมดในย่อหน้านี้: คนูธ เล่ม 1 หน้า 7)

สโตน (1972) และคนูธ (1968, 1973) เป็นศาสตราจารย์ที่มหาวิทยาลัยสแตนฟอร์ดในเวลาเดียวกัน ดังนั้นจึงไม่น่าแปลกใจหากจะมีลักษณะคล้ายคลึงกันในคำจำกัดความของพวกเขา (ตัวหนาเพื่อเน้น):

"โดยสรุป...เรานิยามอัลกอริทึมว่าเป็นชุดของกฎที่กำหนดลำดับการดำเนินการ อย่างแม่นยำ โดยที่แต่ละกฎมีประสิทธิภาพและแน่นอนและลำดับนั้นจะสิ้นสุดลงในเวลาที่จำกัด" (เน้นตัวหนา หน้า 8)

สโตนมีความโดดเด่นเนื่องจากการอธิบายอย่างละเอียดเกี่ยวกับสิ่งที่ถือเป็นกฎที่มี "ประสิทธิภาพ" – หุ่นยนต์ ของเขา หรือบุคคลที่ทำหน้าที่เป็นหุ่นยนต์ ต้องมีข้อมูลและความสามารถบางอย่างอยู่ภายในและหากไม่มีข้อมูลและความสามารถนั้นจะต้องถูกจัดหาให้ใน "อัลกอริทึม"

"เพื่อให้ผู้คนปฏิบัติตามกฎของอัลกอริทึมได้กฎ เหล่านั้น ต้องถูกกำหนดขึ้นมาเพื่อให้สามารถปฏิบัติตามได้ในลักษณะคล้ายหุ่นยนต์กล่าวคือ โดยไม่ต้องใช้ความคิด... อย่างไรก็ตาม หากคำสั่ง [ในการแก้สมการกำลังสอง ตัวอย่างของเขา] จะต้องได้รับการปฏิบัติตามโดยผู้ที่รู้วิธีการคำนวณทางคณิตศาสตร์ แต่ไม่รู้วิธีการหาค่ารากที่สอง เราก็ต้องจัดเตรียมชุดกฎสำหรับการหาค่ารากที่สองด้วย เพื่อให้สอดคล้องกับนิยามของอัลกอริทึม" (หน้า 4-5)

นอกจากนี้ "... คำสั่งบางอย่างก็ไม่เหมาะสมเพราะอาจต้องการให้หุ่นยนต์มีความสามารถเกินกว่าที่เราคิดว่าสมเหตุสมผล " เขาให้ตัวอย่างของหุ่นยนต์ที่ถูกถามว่า "พระเจ้าเฮนรีที่ 8 เป็นกษัตริย์แห่งอังกฤษหรือไม่" และให้พิมพ์ 1 ถ้าใช่ และ 0 ถ้าไม่ใช่ แต่หุ่นยนต์นั้นไม่เคยได้รับข้อมูลนี้มาก่อน และที่แย่กว่านั้น หากหุ่นยนต์ถูกถามว่าอริสโตเติลเป็นกษัตริย์แห่งอังกฤษหรือไม่ และหุ่นยนต์ได้รับเพียงห้าชื่อ มันก็จะไม่รู้ว่าจะตอบอย่างไร ดังนั้น:

“นิยามโดยสัญชาตญาณของลำดับคำสั่งที่ยอมรับได้ คือ ลำดับที่แต่ละคำสั่งได้รับการกำหนดไว้อย่างแม่นยำเพื่อรับประกันว่าหุ่นยนต์จะสามารถปฏิบัติตามได้ ” (หน้า 6)

หลังจากให้คำจำกัดความแล้ว สโตนได้แนะนำ แบบจำลอง เครื่องจักรทัวริงและระบุว่าชุดห้าคู่ซึ่งเป็นคำสั่งของเครื่องจักรนั้นคือ “อัลกอริทึม ... ที่รู้จักกันในชื่อโปรแกรมเครื่องจักรทัวริง” (หน้า 9) หลังจากนั้นทันที เขาก็กล่าวต่อไปว่า “ การคำนวณของเครื่องจักรทัวริงอธิบายได้โดยการระบุว่า:

"1. ตัวอักษรเทป

"2. รูปแบบ การนำเสนอ พารามิเตอร์[อินพุต]บนเทป

"3. สถานะเริ่มต้นของเครื่องจักรทัวริง

"4. รูปแบบที่คำตอบ [ผลลัพธ์]จะถูกแสดงบนเทปเมื่อเครื่องทัวริงหยุดทำงาน

5. โปรแกรมเครื่องจักร (ตัวเอียงเพิ่มเติม หน้า 10)

ข้อกำหนดที่เจาะจงนี้เกี่ยวกับสิ่งที่จำเป็นสำหรับ "การคำนวณ" สอดคล้องกับเจตนารมณ์ของสิ่งที่จะตามมาในงานของ Blass และ Gurevich

" การคำนวณคือกระบวนการที่เราดำเนินการจากวัตถุที่กำหนดไว้เบื้องต้น เรียกว่าอินพุตตามชุดกฎที่กำหนดไว้ เรียกว่าโปรแกรม ขั้นตอนหรืออัลกอริทึมผ่านขั้นตอน ต่างๆ และได้ผลลัพธ์สุดท้าย เรียกว่าเอาต์พุตอัลกอริทึมซึ่งเป็นชุดกฎที่ดำเนินการจากอินพุตไปยังเอาต์พุต ต้องมีความแม่นยำและชัดเจน โดยแต่ละขั้นตอนที่ต่อเนื่องกันจะต้องกำหนดไว้อย่างชัดเจน แนวคิดเรื่องความสามารถในการคำนวณเกี่ยวข้องกับวัตถุเหล่านั้นที่สามารถระบุได้ในหลักการโดยการคำนวณ..." (ตัวเอียงในต้นฉบับ ตัวหนาเพิ่มในหน้า 3)

ในช่วงกลางทศวรรษ 1960 ขณะที่เดวิด เบอร์ลินสกีเป็นนักศึกษาอยู่ที่มหาวิทยาลัยพรินซ์ตัน เขาเป็นลูกศิษย์ของอลอนโซ เชิร์ช (ดูหน้า 160) หนังสือของเขาในปี 2000 เรื่องThe Advent of the Algorithm: The 300-year Journey from an Idea to the Computerมีคำจำกัดความของอัลกอริทึม ดังต่อไปนี้ :

" ในมุมมองของนักตรรกศาสตร์:

" อัลกอริทึมคือ"

กระบวนการที่มีขอบเขตจำกัด

เขียนด้วยคำศัพท์เชิงสัญลักษณ์ที่กำหนดไว้ตายตัว

อยู่ภายใต้การควบคุมตามคำสั่งที่แม่นยำ

เคลื่อนที่ทีละขั้นอย่างกระจัดกระจาย 1, 2, 3, ...

ซึ่งการดำเนินการนั้นไม่จำเป็นต้องใช้ไหวพริบหรือความฉลาดหลักแหลม

สัญชาตญาณ สติปัญญา หรือความเฉียบแหลม

และสิ่งนั้นย่อมต้องจบลงในที่สุด (ตัวหนาและตัวเอียงในต้นฉบับ หน้า xviii)

การอ่านงานของ Gurevich ปี 2000 อย่างละเอียดถี่ถ้วน นำไปสู่ข้อสรุป (หรือการอนุมาน?) ว่าเขาเชื่อว่า "อัลกอริทึม" แท้จริงแล้วคือ "เครื่องจักรทัวริง" หรือ " เครื่องจักรพอยน์เตอร์ " ที่กำลังทำการคำนวณ "อัลกอริทึม" ไม่ใช่เพียงแค่ตารางสัญลักษณ์ที่ชี้นำพฤติกรรมของเครื่องจักร หรือไม่ใช่แค่ตัวอย่างหนึ่งของเครื่องจักรที่ทำการคำนวณโดยใช้ชุดพารามิเตอร์อินพุตเฉพาะ หรือไม่ใช่เครื่องจักรที่ตั้งโปรแกรมไว้อย่างเหมาะสมโดยที่ปิดเครื่องอยู่ แต่แท้จริงแล้วอัลกอริทึมคือเครื่องจักรที่กำลังทำการคำนวณใดๆ ก็ตามที่มันสามารถทำได้ Gurevich ไม่ได้กล่าวออกมาตรงๆ เช่นนี้ ดังนั้นข้อสรุป (หรือการอนุมาน?) ข้างต้นจึงอาจเปิดให้มีการถกเถียงได้:

"...อัลกอริทึมทุกตัวสามารถจำลองได้ด้วยเครื่องจักรทัวริง...โปรแกรมสามารถจำลองได้ และด้วยเหตุนี้จึงสามารถให้ความหมายที่แม่นยำได้ด้วยเครื่องจักรทัวริง" (หน้า 1)

“มักคิดกันว่าปัญหาของการกำหนดรูปแบบอย่างเป็นทางการของแนวคิดอัลกอริทึมแบบลำดับนั้นได้รับการแก้ไขโดย Church [1936] และ Turing [1936] ตัวอย่างเช่น ตามที่ Savage [1987] กล่าวไว้ อัลกอริทึมคือกระบวนการ คำนวณ ที่กำหนดโดยเครื่องจักร Turing Church และ Turing ไม่ได้แก้ปัญหาของการกำหนดรูปแบบอย่างเป็นทางการของแนวคิดอัลกอริทึมแบบลำดับ แต่พวกเขาได้ให้รูปแบบอย่างเป็นทางการ (ที่แตกต่างกันแต่เทียบเท่ากัน) ของแนวคิดฟังก์ชันที่คำนวณได้ และอัลกอริทึมนั้นมีมากกว่าฟังก์ชันที่มันคำนวณ (ตัวเอียงเพิ่มหน้า 3)

"แน่นอนว่า แนวคิดเรื่องอัลกอริทึมและฟังก์ชันที่คำนวณได้นั้นมีความเกี่ยวข้องกันอย่างใกล้ชิด: ตามคำนิยามแล้ว ฟังก์ชันที่คำนวณได้คือฟังก์ชันที่สามารถคำนวณได้ด้วยอัลกอริทึม . . . (หน้า 4)"

ในงานเขียนของ Blass และ Gurevich ปี 2002 ผู้เขียนได้นำเสนอบทสนทนาระหว่าง "Quisani" ("Q") และ "Authors" (A) โดยใช้ Yiannis Moshovakis เป็นตัวอย่าง ซึ่งพวกเขาได้กล่าวออกมาตรงๆ ว่า:

" A:เพื่อให้เห็นชัดเจนถึงความขัดแย้ง เรามาพูดถึงสองประเด็นที่เห็นพ้องกันก่อน ประการแรก มีบางสิ่งที่เป็นอัลกอริทึมอย่างชัดเจนตามคำจำกัดความของทุกคน เช่น เครื่องจักรทัวริง เครื่องจักรสถานะเชิงนามธรรมแบบลำดับเวลา และอื่นๆ ... ประการที่สอง ในอีกด้านหนึ่งคือข้อกำหนดที่ไม่ถือว่าเป็นอัลกอริทึมตามคำจำกัดความของทุกคน เนื่องจากไม่ได้ระบุวิธีการคำนวณใดๆ ... ประเด็นคือข้อมูลต้องมีความละเอียดมากแค่ไหนจึงจะนับว่าเป็นอัลกอริทึม ... โมโชวาคิสยอมรับบางสิ่งที่เราเรียกว่าข้อกำหนดเชิงประกาศ และเขาน่าจะใช้คำว่า "การนำไปใช้" สำหรับสิ่งที่เราเรียกว่าอัลกอริทึม" (ย่อหน้าถูกรวมเข้าด้วยกันเพื่อให้ง่ายต่อการอ่าน, 2002:22)

การใช้คำว่า "การนำไปปฏิบัติ" ในลักษณะนี้ตรงประเด็นกับคำถามอย่างมาก ในช่วงต้นของบทความ Q ได้กล่าวถึงการตีความของเขาเกี่ยวกับ Moshovakis ไว้ว่า:

"...เขาคงคิดว่างานภาคปฏิบัติของคุณ [กูเรวิชทำงานให้กับไมโครซอฟต์] บังคับให้คุณคิดถึงการนำไปใช้มากกว่าอัลกอริทึม เขาเต็มใจที่จะระบุว่าการนำไปใช้คือเครื่องจักร แต่เขากล่าวว่าอัลกอริทึมเป็นสิ่งที่ทั่วไปกว่านั้น สรุปได้ว่า คุณบอกว่าอัลกอริทึมเป็นเครื่องจักร แต่โมสโชวาคิสบอกว่าไม่ใช่" (2002:3)

แต่ผู้เขียนกลับวกวนตรงนี้ โดยกล่าวว่า "[มา]ยึดติดกับคำว่า "อัลกอริทึม" และ "เครื่องจักร" กันเถอะ" ซึ่งทำให้ผู้อ่านสับสนอีกครั้ง เราต้องรอจนถึง Dershowitz และ Gurevich ปี 2007 จึงจะได้พบกับหมายเหตุเชิงอรรถต่อไปนี้:

" . . . อย่างไรก็ตาม หากเรายอมรับมุมมองของโมโชวาคิสแล้ว สิ่งที่เราตั้งใจจะอธิบายก็คือ "การนำอัลกอริทึมไปใช้" (ดูเชิงอรรถที่ 9 2007:6)

Blass และ Gurevich อธิบายว่างานของพวกเขาพัฒนามาจากแนวคิดของเครื่องจักรทัวริงและเครื่องจักรพอยน์เตอร์โดยเฉพาะอย่างยิ่งเครื่องจักร Kolmogorov-Uspensky (เครื่องจักร KU) เครื่องจักรปรับเปลี่ยนการจัดเก็บข้อมูล Schönhage (SMM) และออโตมาตาเชื่อมโยงตามที่ Knuth กำหนดไว้ นอกจากนี้ งานของ Gandy และ Markov ยังได้รับการกล่าวถึงว่าเป็นผู้บุกเบิกที่มีอิทธิพลอีกด้วย

กูเรวิชได้ให้คำจำกัดความที่ "แข็งแกร่ง" ของอัลกอริทึม (เน้นตัวหนา):

"...ข้อโต้แย้งอย่างไม่เป็นทางการของทิวริงที่สนับสนุนวิทยานิพนธ์ของเขานั้น เป็นการพิสูจน์วิทยานิพนธ์ที่แข็งแกร่งกว่า นั่นคือทุกอัลกอริทึมสามารถจำลองได้ด้วยเครื่องจักรทิวริง ...ในทางปฏิบัติ มันคงเป็นเรื่องไร้สาระ...[อย่างไรก็ตาม] [สามารถ]ทำให้เครื่องจักรทิวริงเป็นแบบทั่วไปได้หรือไม่ เพื่อให้อัลกอริทึมใดๆ ก็ตาม ไม่ว่าจะนามธรรมแค่ไหน ก็สามารถจำลองได้ด้วยเครื่องจักรแบบทั่วไป?...แต่สมมติว่าเครื่องจักรทิวริงแบบทั่วไปดังกล่าวมีอยู่จริง สถานะของมันจะเป็นอย่างไร?... โครงสร้างลำดับที่หนึ่ง ... ชุดคำสั่งขนาดเล็กเฉพาะเจาะจงก็เพียงพอในทุกกรณี... การคำนวณเป็นการวิวัฒนาการของสถานะ ...อาจไม่แน่นอน...สามารถโต้ตอบกับสภาพแวดล้อมได้...[อาจเป็น]แบบขนานและหลายตัวแทน...[อาจมี] ความหมายเชิงพลวัต...[รากฐานสองประการของงานของพวกเขาคือ:] วิทยานิพนธ์ของทิวริง...[และ] แนวคิดของโครงสร้าง (ลำดับที่หนึ่ง) ของ [Tarski 1933]" (Gurevich 2000, หน้า 1-2)

วลีข้างต้นที่ว่าการคำนวณในฐานะวิวัฒนาการของสถานะแตกต่างอย่างมากจากคำจำกัดความของ Knuth และ Stone ซึ่งก็คือ "อัลกอริทึม" ในฐานะโปรแกรมเครื่องจักรทัวริง แต่กลับสอดคล้องกับสิ่งที่ทัวริงเรียกว่าการกำหนดค่าที่สมบูรณ์ (ดูคำจำกัดความของทัวริงใน Undecidable หน้า 118) ซึ่งรวมถึงทั้งคำสั่งปัจจุบัน (สถานะ) และสถานะของเทป [ดู Kleene (1952) หน้า 375 ซึ่งเขาแสดงตัวอย่างเทปที่มีสัญลักษณ์ 6 ตัวอยู่บนนั้น โดยช่องอื่นๆ ว่างเปล่า และวิธีการแปลงสถานะตารางและเทปที่รวมกันให้เป็นแบบ Gödel]

ในตัวอย่างอัลกอริธึมเราจะเห็นวิวัฒนาการของสถานะด้วยตนเอง

นักปรัชญาแดเนียล เดนเน็ตต์วิเคราะห์ความสำคัญของวิวัฒนาการในฐานะกระบวนการเชิงอัลกอริทึมในหนังสือของเขาเรื่องDarwin's Dangerous Idea ที่ตีพิมพ์ ในปี 1995 เดนเน็ตต์ระบุคุณลักษณะสำคัญสามประการของอัลกอริทึม:

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

จากผลการวิเคราะห์นี้ เดนเน็ตต์จึงสรุปว่า "ตามทฤษฎีของดาร์วิน วิวัฒนาการเป็นกระบวนการตามขั้นตอนวิธี" (หน้า 60)

อย่างไรก็ตาม ในหน้าก่อนหน้านี้ เขาได้ก้าวไปไกลกว่านั้นมาก ในบริบทของบทที่ชื่อว่า "กระบวนการในฐานะอัลกอริทึม" เขาได้กล่าวไว้ว่า:

"แต่แล้ว...มีข้อจำกัดใดๆ บ้างไหมเกี่ยวกับสิ่งที่อาจถือได้ว่าเป็นกระบวนการเชิงอัลกอริทึม? ผมคิดว่าคำตอบคือไม่มี ถ้าคุณต้องการ คุณสามารถปฏิบัติต่อกระบวนการใดๆ ในระดับนามธรรมว่าเป็นกระบวนการเชิงอัลกอริทึมได้...หากสิ่งที่คุณสงสัยคือความสม่ำเสมอของเม็ดทราย [ในมหาสมุทร] หรือความแข็งแกร่งของใบมีด [เหล็กกล้าชุบแข็ง] คำอธิบายเชิงอัลกอริทึมจะเป็นสิ่งที่ตอบสนองความอยากรู้ของคุณได้ และมันจะเป็นความจริง..."

"ไม่ว่าผลลัพธ์ของอัลกอริทึมจะน่าประทับใจเพียงใด กระบวนการพื้นฐานก็ประกอบด้วยเพียงชุด ขั้นตอนที่ไร้ความ คิดซึ่งดำเนินต่อเนื่องกันไปโดยปราศจากความช่วยเหลือจากการกำกับดูแลอย่างชาญฉลาดใดๆ พวกมันเป็น 'อัตโนมัติ' ตามคำจำกัดความ นั่นคือการทำงานของหุ่นยนต์" (หน้า 59)

จากข้อความข้างต้น ยังไม่ชัดเจนว่าเดนเน็ตต์กำลังกล่าวว่าโลกทางกายภาพด้วยตัวมันเองและปราศจากผู้สังเกตการณ์นั้นมีลักษณะ เป็นอัลกอริทึม (การคำนวณ) โดยเนื้อแท้หรือว่าผู้สังเกตการณ์ที่ประมวลผลสัญลักษณ์เป็นสิ่งที่เพิ่ม "ความหมาย" ให้กับการสังเกตการณ์เหล่านั้น

แดเนียล เดนเน็ตต์เป็นผู้สนับสนุนปัญญาประดิษฐ์เชิงแข็งแกร่ง (Strong Artificial Intelligence ) ซึ่งเป็นแนวคิดที่ว่าโครงสร้างเชิงตรรกะของอัลกอริทึมนั้นเพียงพอที่จะอธิบายจิตใจได้จอห์น เซิร์ลผู้สร้าง การทดลองทางความคิด ห้องจีน (Chinese Room Thought Experiment) อ้างว่า " ไวยากรณ์ [นั่นคือโครงสร้างเชิงตรรกะ] นั้นไม่เพียงพอสำหรับ เนื้อหา เชิงความหมาย [นั่นคือความหมาย]" ( Searle 2002 , หน้า 16) กล่าวอีกนัยหนึ่ง "ความหมาย" ของสัญลักษณ์นั้นสัมพันธ์กับจิตใจที่ใช้สัญลักษณ์นั้น อัลกอริทึม—โครงสร้างเชิงตรรกะ—เพียงอย่างเดียวนั้นไม่เพียงพอสำหรับจิตใจ

เซิร์ลเตือนผู้ที่อ้างว่ากระบวนการทางอัลกอริทึม (การคำนวณ) เป็นสิ่งที่มีอยู่โดยธรรมชาติ (ตัวอย่างเช่น นักจักรวาลวิทยา นักฟิสิกส์ นักเคมี เป็นต้น):

การคำนวณ [...] เป็นสิ่งที่สัมพันธ์กับผู้สังเกต และนี่เป็นเพราะการคำนวณถูกนิยามในแง่ของการจัดการสัญลักษณ์ แต่แนวคิดของ 'สัญลักษณ์' ไม่ใช่แนวคิดทางฟิสิกส์หรือเคมี สิ่งใดสิ่งหนึ่งจะเป็นสัญลักษณ์ได้ก็ต่อเมื่อมันถูกใช้ ถูกปฏิบัติ หรือถูกมองว่าเป็นสัญลักษณ์ ข้อโต้แย้งเรื่องห้องจีนแสดงให้เห็นว่าความหมายไม่ใช่สิ่งที่อยู่ภายในไวยากรณ์ แต่สิ่งที่แสดงให้เห็นคือไวยากรณ์ไม่ใช่สิ่งที่อยู่ภายในฟิสิกส์ [...] สิ่งใดสิ่งหนึ่งจะเป็นสัญลักษณ์ได้ก็ต่อเมื่อสัมพันธ์กับผู้สังเกต ผู้ใช้ หรือตัวแทนบางคนที่กำหนดการตีความเชิงสัญลักษณ์ให้กับมัน [...] คุณสามารถกำหนดการตีความเชิงคำนวณให้กับสิ่งใดก็ได้ แต่ถ้าคำถามถามว่า "จิตสำนึกเป็นสิ่งที่คำนวณได้ภายในหรือไม่" คำตอบคือไม่มีอะไรที่คำนวณได้ภายใน [เน้นตัวเอียงเพื่อเน้นย้ำ] การคำนวณมีอยู่ก็ต่อเมื่อสัมพันธ์กับตัวแทนหรือผู้สังเกตบางคนที่กำหนดการตีความเชิงคำนวณให้กับปรากฏการณ์บางอย่าง นี่เป็นประเด็นที่ชัดเจน ฉันน่าจะเห็นมันเมื่อสิบปีที่แล้ว แต่ฉันไม่ได้เห็น

สำหรับตัวอย่างของการนำวิธีการกำหนดคุณสมบัตินี้ไปใช้กับอัลกอริทึมการบวก "m+n" โปรดดูที่ตัวอย่างอัลกอริทึม

ตัวอย่างใน Boolos-Burgess-Jeffrey (2002) (หน้า 31–32) แสดงให้เห็นถึงความแม่นยำที่จำเป็นในการกำหนดรายละเอียดของอัลกอริทึมอย่างครบถ้วน ในกรณีนี้คือการบวกเลขสองจำนวน: m+n ซึ่งคล้ายกับข้อกำหนดของ Stone ข้างต้น

(i) พวกเขาได้หารือเกี่ยวกับบทบาทของ "รูปแบบตัวเลข" ในการคำนวณและเลือกใช้ "สัญกรณ์นับ" เพื่อแสดงตัวเลข:

"แน่นอนว่าการคำนวณในทางปฏิบัติอาจยากกว่าเมื่อใช้สัญลักษณ์บางแบบมากกว่าแบบอื่น... แต่... ในทางทฤษฎีแล้วสามารถทำได้ด้วยสัญลักษณ์อื่น ๆ เพียงแค่แปลงข้อมูล... เพื่อจุดประสงค์ในการกำหนดกรอบแนวคิดเรื่องความสามารถในการคำนวณอย่างเข้มงวด การใช้สัญลักษณ์แบบโมนาดิกหรือแบบนับจึงสะดวกกว่า" (หน้า 25-26)

(ii) ในตอนต้นของตัวอย่าง พวกเขาระบุว่าเครื่องจักรที่จะใช้ในการคำนวณคือเครื่องจักรทัวริงพวกเขาได้ระบุไว้ก่อนหน้านี้แล้ว (หน้า 26) ว่าเครื่องจักรทัวริงจะเป็นแบบ 4-tuple ไม่ใช่แบบ 5-tuple สำหรับข้อมูลเพิ่มเติมเกี่ยวกับข้อตกลงนี้ โปรดดูที่เครื่องจักรทัวริง

(iii) ก่อนหน้านี้ผู้เขียนได้ระบุว่าตำแหน่งของหัวอ่านเทปจะถูกระบุด้วยตัวห้อยทางด้านขวาของสัญลักษณ์ที่สแกน สำหรับข้อมูลเพิ่มเติมเกี่ยวกับธรรมเนียมนี้ โปรดดูที่เครื่องจักรทัวริง (ต่อไปนี้ใช้ตัวหนาเพื่อเน้น):

"เรายังไม่ได้ให้คำจำกัดความอย่างเป็นทางการว่าฟังก์ชันเชิงตัวเลขใดที่สามารถคำนวณได้ด้วยเครื่องจักรทัวริงโดยระบุวิธีการแสดงอินพุต หรืออาร์กิวเมนต์บนเครื่องจักร และวิธีการแสดง เอาต์พุตหรือค่าต่างๆ ข้อกำหนดของเราสำหรับฟังก์ชัน k ตำแหน่งจากจำนวนเต็มบวกไปยังจำนวนเต็มบวกมีดังนี้:

"(ก) [ รูปแบบตัวเลขเริ่มต้น: ] อาร์กิวเมนต์ m ₁ , ... m _k , ... จะถูกแทนด้วยสัญกรณ์เอกภาค [เอกภาพ] โดยใช้บล็อกของจำนวนขีดเหล่านั้น โดยแต่ละบล็อกคั่นด้วยช่องว่างหนึ่งช่อง บนเทปที่ว่างเปล่า

ตัวอย่าง: 3+2, 111B11

(b) [ ตำแหน่งหัวอ่านเริ่มต้น สถานะเริ่มต้น: ] ในขั้นต้น เครื่องจะสแกนเลข 1 ทางซ้ายสุดบนเทป และจะอยู่ในสถานะเริ่มต้น สถานะ 1

ตัวอย่าง: 3+2, 1 ₁ 111B11

"(c) [ การคำนวณสำเร็จ -- รูปแบบตัวเลขเมื่อหยุดทำงาน: ] หากฟังก์ชันที่จะคำนวณกำหนดค่า n ให้กับอาร์กิวเมนต์ที่แสดงอยู่บนเทปในตอนเริ่มต้น เครื่องจะหยุดทำงานบนเทปที่มีบล็อกของเส้นขีด และหากไม่ใช่บล็อกของเส้นขีด เครื่องจะหยุดทำงานบนเทปที่ว่างเปล่า...

ตัวอย่าง: 3+2, 11111

"(d) [ การคำนวณสำเร็จ -- ตำแหน่งหัวอ่านเมื่อหยุด: ] ในกรณีนี้ [c] เครื่องจะหยุดการสแกนเลข 1 ตัวแรกสุดบนเทป...

ตัวอย่าง: 3+2, 1 _n 1111

"(e) [ การคำนวณไม่สำเร็จ -- ล้มเหลวในการหยุดหรือหยุดด้วยรูปแบบตัวเลขที่ไม่เป็นมาตรฐาน: ] หากฟังก์ชันที่จะคำนวณไม่ได้กำหนดค่าให้กับอาร์กิวเมนต์ที่แสดงไว้บนเทปในตอนเริ่มต้น เครื่องจะไม่หยุดเลย หรือจะหยุดในรูปแบบที่ไม่เป็นมาตรฐาน..."(ibid)

ตัวอย่าง: B _n 11111 หรือ B11 _n 111 หรือ B11111 _n

ข้อกำหนดนี้ยังไม่สมบูรณ์: ยังต้องการทราบตำแหน่งที่จะวางคำสั่งและรูปแบบของคำสั่งในเครื่องด้วย--

(iv) ใน ตารางของ เครื่องสถานะจำกัดหรือในกรณีของเครื่องทัวริงสากลบนเทป และ

(v) ตารางคำแนะนำในรูปแบบที่กำหนด

ประเด็นหลังนี้สำคัญมาก Boolos-Burgess-Jeffrey ได้สาธิต (หน้า 36) ว่าความสามารถในการคาดเดาของรายการในตารางทำให้สามารถ "ย่อ" ตารางได้โดยการจัดเรียงรายการตามลำดับและละเว้นสถานะอินพุตและสัญลักษณ์ อันที่จริง การคำนวณเครื่องจักรทัวริงตัวอย่างนั้นต้องการเพียง 4 คอลัมน์ดังแสดงในตารางด้านล่าง (แต่โปรดทราบว่า: ข้อมูลเหล่านี้ถูกนำเสนอต่อเครื่องจักรในรูปแบบแถว ):

สำหรับตัวอย่างของการนำวิธีการกำหนดคุณสมบัตินี้ไปใช้กับอัลกอริทึมการบวก "m+n" โปรดดูที่ตัวอย่างอัลกอริทึม

Sipser เริ่มต้นด้วยการให้คำจำกัดความของ "อัลกอริทึม" ดังนี้:

"โดยทั่วไปแล้วอัลกอริทึมคือชุดคำสั่งง่ายๆ สำหรับการดำเนินการบางอย่าง อัลกอริทึมเป็นสิ่งที่พบเห็นได้ทั่วไปในชีวิตประจำวัน บางครั้งจึงถูกเรียกว่าขั้นตอนหรือสูตร (ตัวเอียงในต้นฉบับ หน้า 154)"

"...จุดสนใจที่แท้จริงของเรานับจากนี้ไปคืออัลกอริทึม กล่าวคือ เครื่องจักรทัวริงเป็นเพียงแบบจำลองที่แม่นยำสำหรับนิยามของอัลกอริทึม ... เราเพียงแค่ต้องคุ้นเคยกับเครื่องจักรทัวริงมากพอที่จะเชื่อว่ามันครอบคลุมอัลกอริทึมทั้งหมด" (หน้า 156)

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

"แต่โปรดทราบว่า การใช้สัญกรณ์เอกภาคในการเข้ารหัสตัวเลข (เช่น ตัวเลข 17 ที่เข้ารหัสด้วยเลขเอกภาค 11111111111111111) นั้นไม่สมเหตุสมผล เพราะมีขนาดใหญ่กว่าการเข้ารหัสที่สมเหตุสมผลอย่างแท้จริง เช่น สัญกรณ์ฐานkสำหรับk ≥ 2 อย่างมากในเชิงเลขยกกำลัง" (หน้า 259)

Van Emde Boas แสดงความคิดเห็นเกี่ยวกับปัญหาที่คล้ายกันในส่วนที่เกี่ยวกับ แบบจำลองนามธรรมของการคำนวณ แบบหน่วยความจำเข้าถึงแบบสุ่ม (RAM) ซึ่งบางครั้งใช้แทนเครื่องจักรทัวริงเมื่อทำการ "วิเคราะห์อัลกอริทึม" ว่า "การไม่มีหรือการมีอยู่ของการดำเนินการจัดการบิตแบบคูณและแบบขนานมีความเกี่ยวข้องกับความเข้าใจที่ถูกต้องของผลลัพธ์บางอย่างในการวิเคราะห์อัลกอริทึม"

". . . แทบจะไม่มีสิ่งใดที่เป็นส่วนขยายที่ 'บริสุทธิ์' ของแบบจำลอง RAM มาตรฐานในการวัดเวลาแบบสม่ำเสมอเลย ไม่ว่าจะเป็นการใช้เลขคณิตแบบบวกเท่านั้น หรืออาจจะรวมคำสั่งการคูณและ/หรือคำสั่งบูลีนแบบบิตที่สมเหตุสมผลทั้งหมดบนตัวดำเนินการขนาดเล็กเข้าไปด้วยก็ได้" (Van Emde Boas, 1990:26)

ในส่วนของ "ภาษาอธิบาย" สำหรับอัลกอริทึมนั้น Sipser ได้สานต่องานที่ Stone และ Boolos-Burgess-Jeffrey เริ่มไว้ (เน้นตัวหนา) เขาเสนอระดับการอธิบายอัลกอริทึมของเครื่องจักรทัวริงสามระดับ (หน้า 157):

คำอธิบายระดับสูง : "โดยที่เราใช้...ข้อความบรรยายเพื่ออธิบายอัลกอริทึม โดยไม่สนใจรายละเอียดการใช้งาน ในระดับนี้เราไม่จำเป็นต้องกล่าวถึงว่าเครื่องจักรจัดการเทปหรือหัวอ่านอย่างไร"

คำอธิบายการใช้งาน : "ซึ่งเราใช้...ข้อความบรรยายเพื่ออธิบายวิธีการที่เครื่องจักรทัวริงเคลื่อนหัวอ่านและวิธีการจัดเก็บข้อมูลบนเทป ในระดับนี้เราไม่ได้ให้รายละเอียดเกี่ยวกับสถานะหรือฟังก์ชันการเปลี่ยนสถานะ"

คำอธิบายอย่างเป็นทางการ : "...ระดับคำอธิบายที่ละเอียดที่สุด...ซึ่งระบุสถานะ ฟังก์ชันการเปลี่ยนสถานะ และอื่นๆ ของเครื่องจักรทัวริงอย่างครบถ้วน"

ใน Yanofsky (2011) ^{[ 3 ]}อัลกอริทึมถูกกำหนดให้เป็นเซตของโปรแกรมที่ใช้อัลกอริทึมนั้น โดยเซตของโปรแกรมทั้งหมดจะถูกแบ่งออกเป็นคลาสสมมูล แม้ว่าเซตของโปรแกรมจะไม่ก่อให้เกิดหมวดหมู่ แต่เซตของอัลกอริทึมกลับก่อให้เกิดหมวดหมู่ที่มีโครงสร้างเพิ่มเติม เงื่อนไขที่อธิบายว่าเมื่อใดที่โปรแกรมสองโปรแกรมจะเทียบเท่ากันนั้น กลายเป็นความสัมพันธ์ที่สอดคล้องกันซึ่งให้โครงสร้างเพิ่มเติมแก่หมวดหมู่ของอัลกอริทึม

ใน Seiller (2024) ^{[ 4 ]}อัลกอริทึมถูกกำหนดให้เป็นกราฟที่มีป้ายกำกับขอบ พร้อมกับการตีความป้ายกำกับเป็นแผนที่ในโครงสร้างข้อมูลนามธรรม คำจำกัดความนี้ให้มาพร้อมกับคำจำกัดความอย่างเป็นทางการของโปรแกรม (และแบบจำลองการคำนวณ) ซึ่งช่วยให้สามารถกำหนดแนวคิดของการใช้งานได้อย่างเป็นทางการ นั่นคือเมื่อโปรแกรมใช้งานอัลกอริทึม แนวคิดของอัลกอริทึมที่ได้มานี้หลีกเลี่ยงปัญหาที่ทราบกันดีบางประการ และเข้าใจได้ว่าเป็นข้อกำหนดบางอย่าง โดยเฉพาะอย่างยิ่ง โปรแกรมที่กำหนดสามารถ (และในความเป็นจริง มักจะ) ใช้งานอัลกอริทึมหลายตัวได้ คุณลักษณะสำคัญอีกประการหนึ่งของแนวทางนี้คือการคำนึงถึงข้อเท็จจริงที่ว่าอัลกอริทึมที่กำหนดสามารถนำไปใช้ในแบบจำลองการคำนวณที่แตกต่างกัน (และอาจไม่เกี่ยวข้องกัน) ได้