ทฤษฎีการคำนวณและภาษาโปรแกรม

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ทฤษฎีการคำนวณและภาษาโปรแกรม

ทฤษฎีการคำนวณ vs. ภาษาโปรแกรม

การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation) ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทางฟังก์ชันเวียนบังเกิด ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลแลมดาแคลคูลัสใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น ขั้นตอนวิธีของมาคอฟและระบบของโพสต์ที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้ ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ปัญหาความสัมพันธ์ของโพสต์) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู:en:Presburger arithmetic) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้าง (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้างได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้. ษาโปรแกรม คือภาษาประดิษฐ์ชนิดหนึ่งที่ออกแบบขึ้นมาเพื่อสื่อสารชุดคำสั่งแก่เครื่องจักร โดยเฉพาะอย่างยิ่งคอมพิวเตอร์ ภาษาโปรแกรมสามารถใช้สร้างโปรแกรมที่ควบคุมพฤติกรรมของเครื่องจักร และ/หรือ แสดงออกด้วยขั้นตอนวิธี (algorithm) อย่างตรงไปตรงมา ผู้เขียนโปรแกรมซึ่งหมายถึงผู้ที่ใช้ภาษาโปรแกรมเรียกว่า โปรแกรมเมอร์ (programmer) ภาษาโปรแกรมในยุคแรกเริ่มนั้นเกิดขึ้นก่อนที่คอมพิวเตอร์จะถูกประดิษฐ์ขึ้น โดยถูกใช้เพื่อควบคุมการทำงานของเครื่องทอผ้าของแจ็กการ์ดและเครื่องเล่นเปียโน ภาษาโปรแกรมต่าง ๆ หลายพันภาษาถูกสร้างขึ้นมา ส่วนมากใช้ในวงการคอมพิวเตอร์ และสำหรับวงการอื่นภาษาโปรแกรมก็เกิดขึ้นใหม่ทุก ๆ ปี ภาษาโปรแกรมส่วนใหญ่อธิบายการคิดคำนวณในรูปแบบเชิงคำสั่ง อาทิลำดับของคำสั่ง ถึงแม้ว่าบางภาษาจะใช้การอธิบายในรูปแบบอื่น ตัวอย่างเช่น ภาษาที่สนับสนุนการเขียนโปรแกรมเชิงฟังก์ชัน หรือการเขียนโปรแกรมเชิงตรรกะ การพรรณนาถึงภาษาโปรแกรมหนึ่ง ๆ มักจะแบ่งออกเป็นสองส่วนได้แก่ วากยสัมพันธ์ (รูปแบบ) และอรรถศาสตร์ (ความหมาย) บางภาษาถูกนิยามขึ้นด้วยเอกสารข้อกำหนด (ตัวอย่างเช่น ภาษาซีเป็นภาษาหนึ่งที่กำหนดโดยมาตรฐานไอโซ) ในขณะที่ภาษาอื่นอย่างภาษาเพิร์ลรุ่น 5 และก่อนหน้านั้น ใช้การทำให้เกิดผลแบบอ้างอิง (reference implementation) เป็นลักษณะเด่น.

ภาษาเพิร์ล

right ภาษาเพิร์ล (Perl) (ย่อมาจาก Practical Extraction and Report Language) เป็นภาษาโปรแกรมแบบไดนามิก พัฒนาโดยนายแลร์รี วอลล์ (Larry Wall) ในปี ค.ศ. 1987 เพื่อใช้งานกับระบบปฏิบัติการยูนิกซ์ ภาษาเพิร์ล นั้นถูกออกแบบมาให้ใช้งานได้ง่าย โครงสร้างของภาษาจึงไม่ซับซ้อน มีลักษณะคล้ายกับภาษาซี นอกจากนี้เพิร์ลยังได้แนวคิดบางอย่างมาจากเชลล์สคริปต์, ภาษา AWK, sed และ Lisp ปัจจุบันเวอร์ชันล่าสุดคือ 5.18.0.

ทฤษฎีการคำนวณและภาษาเพิร์ล · ภาษาเพิร์ลและภาษาโปรแกรม · ดูเพิ่มเติม »