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

ผลลัพธ์ที่น่าสนใจคือการอินทิเกรต (ในความหมายของอินทิกรัลของรีมันน์ ) สามารถคำนวณได้^{[ 1 ]}นี่อาจถือได้ว่าน่าประหลาดใจ เนื่องจากอินทิกรัล (โดยคร่าวๆ) คือผลรวมอนันต์ แม้ว่าผลลัพธ์นี้จะสามารถอธิบายได้ด้วยข้อเท็จจริงที่ว่าฟังก์ชันที่คำนวณได้ ทุกฟังก์ชัน จากถึงมีความต่อเนื่องสม่ำเสมอแต่สิ่งที่น่าสังเกตคือค่าสัมบูรณ์ของความต่อเนื่องสามารถคำนวณได้เสมอโดยไม่ต้องระบุอย่างชัดเจน ข้อเท็จจริงที่น่าประหลาดใจในทำนองเดียวกันคือการหาอนุพันธ์ของฟังก์ชันเชิงซ้อนก็สามารถคำนวณได้เช่นกัน ในขณะที่ผลลัพธ์เดียวกันนี้เป็นเท็จสำหรับฟังก์ชันจริงดู§ ผลลัพธ์พื้นฐาน ${\displaystyle \mathbb {[} 0,1]}$${\displaystyle \mathbb {R} }$

ผลลัพธ์ที่กระตุ้นให้เกิดความคิดข้างต้นไม่มีสิ่งใดเทียบเคียงได้ในการวิเคราะห์เชิงสร้างสรรค์ของบิชอปแต่เป็นรูปแบบการวิเคราะห์เชิงสร้างสรรค์ที่แข็งแกร่งกว่าซึ่งพัฒนาโดยบราวเวอร์ต่างหากที่ให้สิ่งที่เทียบเคียงได้ในตรรกะเชิงสร้างสรรค์

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

เครื่องจักรทัวริงประเภทที่ 2 คือเครื่องจักรทัวริงที่มีเทปสามม้วน ได้แก่ เทปอินพุตซึ่งอ่านได้อย่างเดียว เทปทำงานซึ่งสามารถเขียนและอ่านได้ และที่สำคัญคือ เทปเอาต์พุตซึ่ง "เพิ่มข้อมูลได้อย่างเดียว"

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

ในกรณีของจำนวนจริง การแสดงผลแบบทศนิยมหรือเลขฐานสองตามปกติจะไม่เหมาะสม ดังนั้นจึงมักใช้การแสดงผลแบบตัวเลขมีเครื่องหมาย ซึ่งเสนอโดย Brouwer เป็นครั้งแรก: ระบบตัวเลขเป็นฐาน 2 แต่ตัวเลขคือ(แทน) 0 และ 1 โดยเฉพาะอย่างยิ่ง หมายความว่าสามารถแสดงได้ทั้งในรูป และ${\displaystyle {\overline {1}}}$${\displaystyle -1}$${\displaystyle 1/2}$${\displaystyle 0.1}$${\displaystyle 1.{\overline {1}}}$

เพื่อให้เข้าใจว่าเหตุใดการใช้สัญกรณ์ทศนิยมจึงไม่เหมาะสม ลองพิจารณาปัญหาการคำนวณค่าและโดยให้ผลลัพธ์ในรูปแบบทศนิยม ค่าของคือหรือหากให้ผลลัพธ์แบบหลังมา ตัวอย่างเช่น จะต้องอ่านค่า จำนวนหลักจำกัดของก่อนที่จะเลือกหลักก่อนจุดทศนิยมในแต่ถ้าหลักที่ ของลดลงเหลือ 2 ผลลัพธ์สำหรับ ก็จะผิด ในทำนองเดียวกัน การเลือกแบบแรกสำหรับก็อาจผิดได้ในบางครั้ง นี่คือภาวะกลืนไม่เข้าคายไม่ออกของคนทำตารางนั่นเอง ${\displaystyle z=x+y}$${\displaystyle x=0.(3)}$${\displaystyle y=0.(6)}$${\displaystyle z}$${\displaystyle z}$${\displaystyle 0.(9)}$${\displaystyle 1.(0)}$${\displaystyle n}$${\displaystyle x}$${\displaystyle 1}$${\displaystyle z}$${\displaystyle n+1}$${\displaystyle x}$${\displaystyle z}$${\displaystyle 0.(9)}$${\displaystyle z}$

นอกเหนือจากตัวเลขที่มีเครื่องหมายแล้ว ยังมีลำดับโคชีและลำดับเดเดคินด์ที่สามารถนำมาใช้แทนได้ในหลักการ

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

ผลลัพธ์เกี่ยวกับการคำนวณที่เกี่ยวข้องกับเซตอนันต์มักเกี่ยวข้องกับการตั้งชื่อ ซึ่งเป็นแผนที่ระหว่างเซตเหล่านั้นและการแสดงแทนแบบเวียนซ้ำของเซตย่อยของเซตเหล่านั้น การตั้งชื่อบนเซตหนึ่งก่อให้เกิดโทโพโลยีเหนือเซตนั้นดังที่ได้อธิบายไว้ด้านล่าง

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

ความแตกต่างระหว่างโมเดลทั้งสองอยู่ที่ข้อเท็จจริงที่ว่าโปรแกรมที่มีพฤติกรรมที่ดีบนจำนวนที่คำนวณได้ (ในแง่ของความเป็นฟังก์ชันสมบูรณ์) ไม่จำเป็นต้องมีพฤติกรรมที่ดีบนจำนวนจริงใดๆ ตัวอย่างเช่น มีฟังก์ชันที่คำนวณได้บนจำนวนจริงที่คำนวณได้ซึ่งแมปช่วงปิดที่มีขอบเขตบางช่วงไปยังช่วงเปิดที่ไม่มีขอบเขต^{[ 3 ]}ฟังก์ชันเหล่านี้ไม่สามารถขยายไปยังจำนวนจริงใดๆ ได้ (โดยไม่ทำให้เป็นฟังก์ชันบางส่วน) เนื่องจากฟังก์ชันที่คำนวณได้ทั้งหมดมีความต่อเนื่อง และสิ่งนี้จะละเมิดทฤษฎีบทค่าสุดขีดเนื่องจากพฤติกรรมประเภทนั้นอาจถือได้ว่าผิดปกติ จึงเป็นเรื่องปกติที่จะยืนยันว่าฟังก์ชันควรได้รับการพิจารณาว่าเป็นฟังก์ชันสมบูรณ์ก็ต่อเมื่อเป็นฟังก์ชันสมบูรณ์บน จำนวนจริง ทั้งหมดไม่ใช่เฉพาะจำนวนที่คำนวณได้เท่านั้น ${\displaystyle \mathbb {R} \to \mathbb {R} }$

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

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

ผลลัพธ์พื้นฐานประการหนึ่งของการวิเคราะห์ที่คำนวณได้คือฟังก์ชันที่คำนวณได้ ทุกฟังก์ชัน จากไปเป็นฟังก์ชันต่อเนื่อง [ ^{5 ] เมื่อ}พิจารณาต่อไปอีก จะเห็นได้ว่ามีความคล้ายคลึงกันระหว่างแนวคิดพื้นฐานในโทโพโลยีและแนวคิดพื้นฐานในความสามารถในการคำนวณ: ${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} }$

• ฟังก์ชันที่คำนวณได้นั้นคล้ายคลึงกับฟังก์ชันต่อเนื่อง
• เซต ที่ตัดสินได้บางส่วนนั้นคล้ายคลึงกับเซตเปิด
• เซตที่ตัดสินใจร่วมได้นั้นคล้ายคลึงกับเซตปิด
• มีสิ่งที่เทียบเคียงได้กับความกะทัดรัด เชิงโทโพโลยีที่สามารถคำนวณได้ กล่าวคือ เซตย่อยของจะมีความกะทัดรัดที่คำนวณได้ก็ต่อเมื่อมีกระบวนการตัดสินใจกึ่งๆ " " ที่เมื่อได้รับ述语ที่ตัดสินใจได้กึ่งๆ เป็นอินพุต จะตัดสินใจกึ่งๆ ว่าทุกจุดในเซตนั้นตรงตาม述语หรือ ไม่${\displaystyle S}$${\displaystyle \mathbb {R} }$${\displaystyle \forall _{S}}$${\displaystyle P}$${\displaystyle S}$${\displaystyle P}$
• แนวคิดเรื่องความกะทัดรัดที่คำนวณได้ข้างต้นนั้นสอดคล้องกับทฤษฎีบทไฮเนอ-โบเรล ในรูปแบบที่คล้ายคลึงกัน โดยเฉพาะอย่างยิ่ง ช่วงหน่วยนั้นมีความกะทัดรัดที่คำนวณได้${\displaystyle [0,1]}$
• ปริภูมิแบบไม่ต่อเนื่องในทางโทโพโลยีมีความคล้ายคลึงกับเซตในทางความสามารถในการคำนวณ ซึ่งความเท่าเทียมกันระหว่างสมาชิกนั้นสามารถตัดสินได้แบบกึ่งๆ
• ปริภูมิเฮาส์ดอร์ฟในทางโทโพโลยีมีความคล้ายคลึงกับเซตในทางความสามารถในการคำนวณ ซึ่งความไม่เท่ากันระหว่างสมาชิกนั้นสามารถตัดสินได้แบบกึ่งๆ
• มีความคล้ายคลึงกันอย่างมากระหว่างระดับความไม่ต่อเนื่องของฟังก์ชันในลำดับชั้นของโบเรลและระดับความไม่สามารถคำนวณได้ซึ่งกำหนดโดยลำดับชั้นของไวห์เราช์

การเปรียบเทียบชี้ให้เห็นว่าโทโพโลยีทั่วไปและความสามารถในการคำนวณนั้นเกือบจะเป็นภาพสะท้อนซึ่งกันและกัน การเปรียบเทียบนี้ได้รับการทำให้เข้มงวดในกรณีของพื้นที่กระชับเฉพาะที่ [ ^{7 ] ซึ่ง}ส่งผลให้เกิดการสร้างสาขาย่อยของโทโพโลยีทั่วไป เช่นทฤษฎีโดเมนที่ศึกษาพื้นที่โทโพโลยีซึ่งแตกต่างจากพื้นที่เฮาส์ดอร์ฟที่คนส่วนใหญ่ศึกษาในการวิเคราะห์ทางคณิตศาสตร์ — พื้นที่เหล่านี้กลายเป็นธรรมชาติภายใต้การเปรียบเทียบ

• ลำดับสเปคเกอร์

• ความสามารถในการคำนวณและความซับซ้อนในเครือข่ายการวิเคราะห์