สารบัญ
8 ความสัมพันธ์: พ.ศ. 2479พ.ศ. 2490การทดสอบทัวริงทฤษฎีการคำนวณทฤษฎีความซับซ้อนในการคำนวณขั้นตอนวิธีปัญญาประดิษฐ์แอลัน ทัวริง
- ทฤษฎีการคำนวณได้
- ทฤษฎีออโตมาตา
- ภาษารูปนัย
- วิทยาการคอมพิวเตอร์เชิงทฤษฎี
- สิ่งประดิษฐ์ของอังกฤษ
พ.ศ. 2479
ทธศักราช 2479 ตรงกับปีคริสต์ศักราช 1936.
พ.ศ. 2490
ทธศักราช 2490 ตรงกับปีคริสต์ศักราช 1947.
การทดสอบทัวริง
การทดสอบของทัวริง เป็นวิธีการที่ แอลัน ทัวริง ได้เสนอขึ้นในปี..
ดู เครื่องทัวริงและการทดสอบทัวริง
ทฤษฎีการคำนวณ
การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation) ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทางฟังก์ชันเวียนบังเกิด ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลแลมดาแคลคูลัสใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น ขั้นตอนวิธีของมาคอฟและระบบของโพสต์ที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้ ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ปัญหาความสัมพันธ์ของโพสต์) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู:en:Presburger arithmetic) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้าง (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้างได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้.
ดู เครื่องทัวริงและทฤษฎีการคำนวณ
ทฤษฎีความซับซ้อนในการคำนวณ
ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า).
ดู เครื่องทัวริงและทฤษฎีความซับซ้อนในการคำนวณ
ขั้นตอนวิธี
ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.
ดู เครื่องทัวริงและขั้นตอนวิธี
ปัญญาประดิษฐ์
ปัญญาประดิษฐ์ (Artificial Intelligence) หรือ เอไอ (AI) หมายถึงความฉลาดเทียมที่สร้างขึ้นให้กับสิ่งที่ไม่มีชีวิต ปัญญาประดิษฐ์เป็นสาขาหนึ่งในด้านวิทยาการคอมพิวเตอร์ และวิศวกรรมเป็นหลัก แต่ยังรวมถึงศาสตร์ในด้านอื่น ๆ อย่างจิตวิทยา ปรัชญา หรือชีววิทยา ซึ่งสาขาปัญญาประดิษฐ์เป็นการเรียนรู้เกี่ยวกับกระบวนการการคิด การกระทำ การให้เหตุผล การปรับตัว หรือการอนุมาน และการทำงานของสมอง แม้ว่าดังเดิมนั้นเป็นสาขาหลักในวิทยาการคอมพิวเตอร์ แต่แนวคิดหลาย ๆ อย่างในศาสตร์นี้ได้มาจากการปรับปรุงเพิ่มเติมจากศาสตร์อื่นๆ เช่น.
ดู เครื่องทัวริงและปัญญาประดิษฐ์
แอลัน ทัวริง
แอลัน แมธิสัน ทัวริง (Alan Mathison Turing; 23 มิถุนายน พ.ศ. 2455 (ค.ศ. 1912) – 7 มิถุนายน พ.ศ. 2497 (ค.ศ. 1954)) เป็นนักคณิตศาสตร์, นักตรรกศาสตร์, นักรหัสวิทยาและวีรบุรุษสงครามชาวอังกฤษ และเป็นที่ยอมรับว่าเป็นบิดาของวิทยาการคอมพิวเตอร์ เขาได้สร้างรูปแบบที่เป็นทางการทางคณิตศาสตร์ของการระบุขั้นตอนวิธีและการคำนวณ โดยใช้เครื่องจักรทัวริง ซึ่งตามข้อปัญหาเชิร์ช-ทัวริงได้กล่าวว่าเป็นรูปแบบของเครื่องจักรคำนวณเชิงกลที่ครอบคลุมทุก ๆ รูปแบบที่เป็นไปได้ในทางปฏิบัติ ในระหว่างสงครามโลกครั้งที่สอง ทัวริงมีส่วนสำคัญในการแกะรหัสลับของฝ่ายเยอรมัน โดยเขาเป็นหัวหน้าของกลุ่ม Hut 8 ที่ทำหน้าที่ในการแกะรหัสของเครื่องอินิกมาที่ใช้ในฝ่ายทหารเรือ หลังจากสงครามเขาได้ออกแบบเครื่องคอมพิวเตอร์อิเล็กทรอนิกส์ที่สามารถโปรแกรมได้เครื่องแรกๆ ของโลกที่ห้องปฏิบัติการฟิสิกส์แห่งชาติ และได้สร้างเครื่องคอมพิวเตอร์ขึ้นจริง ๆ ที่มหาวิทยาลัยแมนเชสเตอร์ รางวัลทัวริงถูกก่อตั้งขึ้นเพื่อยกย่องเขาในเรื่องนี้ นอกจากนั้นแล้ว การทดสอบของทัวริงที่เขาได้เสนอนั้นมีผลอย่างสูงต่อการศึกษาเรื่องปัญญาประดิษฐ์ ซึ่งในขณะมีถกเถียงที่สำคัญว่า เป็นไปได้หรือไม่ที่จะกล่าวว่าเครื่องจักรนั้นมีสำนึกและสามารถคิดได้.
ดู เครื่องทัวริงและแอลัน ทัวริง
ดูเพิ่มเติม
ทฤษฎีการคำนวณได้
- การคำนวณ
- ทฤษฎีการคำนวณได้
- ทฤษฎีบทเวียนบังเกิดของคลีน
- ปัญหาการตัดสินใจ
- ปัญหาการยุติการทำงาน
- เครื่องทัวริง
- แคลคูลัสแลมบ์ดา
ทฤษฎีออโตมาตา
- ทฤษฎีออโตมาตา
- นิพจน์ปรกติ
- เครื่องทัวริง
ภาษารูปนัย
วิทยาการคอมพิวเตอร์เชิงทฤษฎี
- การคำนวณ
- การวางแผนการเคลื่อนที่
- ขั้นตอนวิธี
- นิจพล
- บทนิยามเวียนเกิด
- ปัญหาระดับบรรพบุรุษ
- เครื่องทัวริง
- แคลคูลัสแลมบ์ดา
สิ่งประดิษฐ์ของอังกฤษ
- กรงฟาราเดย์
- กระบวนการกระจกเปียก
- กังหันไอน้ำ
- การเผาขยะ
- ซองจดหมาย
- ฐานข้อมูลเชิงสัมพันธ์
- ดินน้ำมัน
- ตะเกียงเดวี
- ตัวเหนี่ยวนำ
- ถังดับเพลิง
- นาฬิกาดาราศาสตร์
- ปืนใหญ่อัตตาจร
- พอลิเอทิลีนเทเรฟทาเลต
- ฟุตบอล
- มอเตอร์แนวราบ
- ยางรัด
- รถถัง
- สะพานคานรูปกล่อง
- สไลด์รูล
- หลอดสุญญากาศ
- หลอดไส้ร้อนแบบธรรมดา
- อาหารจานด่วน
- เกมปาเป้า
- เครื่องกำเนิดไฟฟ้า
- เครื่องจักรไอน้ำ
- เครื่องซักผ้า
- เครื่องทัวริง
- เรือดำน้ำ
- เรือโฮเวอร์คราฟต์
- เวิลด์ไวด์เว็บ
- เว็บเซิร์ฟเวอร์
- เว็บเบราว์เซอร์
- เว็บแคม
- เหล็กกล้าไร้สนิม
- แปรงสีฟัน
- แว่นกันแดด
- แว่นขยาย
- โซดา
- โทรสาร
- ไม้ขีดไฟ
หรือที่รู้จักกันในชื่อ Turing machineเครื่องจักรทัวริง