Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นขึ้น
ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation)
ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทาง ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น และที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ
นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้
ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู en:Presburger arithmetic) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ
นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทาง (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มี (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด
โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ไม่พึ่งบริบทได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของ
ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้. ถ้ากลุ่ม X เป็นซับเซ็ตแท้ของ Y เราจะแสดง X ด้านล่าง Y และมีเส้นทึบเชื่อมระหว่างสองกลุ่ม. ถ้า X เป็นซับเซ็ตแต่ไม่ทราบแน่นอนว่าจะเท่ากันหรือไม่ เราจะเชื่อมด้วยเส้นที่บางกว่าและเป็นเส้นประ.
| ||||||||||
 | | |||||||||
|
| |||||||||
| ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||
 | ||||||||||
| ||||||||||
| ||||||||||
| | | | | | |||||
| | | | | ||||||
| | | | | ||||||
| | |
| |||||||
| | | | | | |||||
| | |
|
|
| |||||
| | | | | ||||||
| |
| ||||||||
| | | | |||||||
|
| |||||||||
| | |||||||||
| ||||||||||
| ||||||||||
| ||||||||||
อ้างอิง
- Garey, Michael R., and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
- Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
- Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. One of the standard references in the field.
- Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
- The Complexity Zoo 2007-11-18 ที่ เวย์แบ็กแมชชีน: A huge list of complexity classes, as reference for experts.
- Computability Logic 2011-04-11 ที่ เวย์แบ็กแมชชีน: A theory of interactive computation. The main web source on this new subject.
ดูเพิ่ม
- Computability logic
- Interactive computation
- Important publications in computability
- Open problems in computability
- Calculation
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud karsuksaekiywkb thvsdikarkhanwn erimkhunemuxtnstwrrsthiyisib kxncamikarkhidkhnkhun inchwngewladngklaw nkkhnitsastriderimsuksawa pyhathangkhnitsastridbangthisamarthaekiddwywithiphunthan aelapyhaidthiimsamarthaekid khntxnaerkkkhuxkarihidwawithiphunthaninkaraekpyhannkhuxxairbang nnkhux phwkekhatxngkaromedlxyangepnthangkarkhxngkarkhanwn formal model of computation idmikarsrangomedlinrupaebbtang makmay omedlekhruxngckrthwringmxngkarkhanwnepnkarthangankhxngekhruxngckrthithanganbnethpekbtwxksrthimikhwamyawimcakd odymihwxan ekhiynthicathangankbchxngbnethpthilachxng xikomedlhnungphicarnakarkhanwnphanthang sungichfngkchnaelakarprakxbkn composition khxngfngkchnthithanganbntwelkh omedlichwithikhlaykn nxkcakniyngmiomedlxun echn aelathiichiwyakrnbnstring omedlthangkartangehlaniidrbkaraesdngwamikhwamsamarthethiybethakn nnkhux karkhanwnidthikrathaidodyomedlhnungcasamarththaidinxikomedldwyechnkn omedlehlaniyngmikhwamsamarthethaknkbekhruxngkhxmphiwetxrthwipthieraichxyu thaerasmmtiwaekhruxngkhxmphiwetxrnnmihnwykhwamcaimrucb nxkcakni yngepnthiechuxknxikwa thuk omedlkarkhanwnthi smehtusmphl camikhwamsamarthethiybethakbekhruxngckrthwring sungkhwamechuxnieriykwa Church Turing thesis sastrthisuksaekiywkbkhxbekhtkhxngpyhathikhanwniddwyomedlkhxngekhruxngckraebbtangnnkhux thvsdikarkhanwnid thvsdikarkhanwnsuksaomedlkarkhanwn phrxmkbkhidcakdkhxngkarkhanwn echn pyhaidthisamarthphisucnidwaimsamarthaekiddwykhxmphiwetxr du pyhakaryutikarthangan hrux pyhaidbangthisamarthaekikhiddwykhxmphiwetxr aettxngkarewlamhasalcnthaihkarhakhatxbnnepnipimid du en Presburger arithmetic karhakhatxbyakkwakartrwckhatxbkhxngpyhahruxim du klumkhwamsbsxn phi aela exnphi sastrthisuksaekiywkbewlaaelaenuxthithitxngkarsahrbpyhatang khux thvsdikhwamsbsxninkarkhanwn nxkcakomedlinkarkhanwnthwipaelw yngmirupaebbinkarkhanwnxun thingaykwann echn omedlkhxngniphcnprkti thiepnwithithiichkahndrupaebbkhxngstringinyuniks aelainbangphasakhxmphiwetxr echn phasaephirl odymiomedl echn ekhruxngckrsthanacakdthimikhwamsamarthethiybethakn omedlthimikhwamsamarthkwaomedlniphcn regular echn omedlthixthibaykarkhanwnphanthang context free grammar ichsahrbrabuiwyakrnkhxngphasaopraekrm odythimi pushdown automata epnxikrupaebbthiethiybethakn kepnomedlyxykhxngfngkchnewiynbngekid omedlthiaetktangknxacmikhwamsamarththiaetktangknid xikwithihnungthicawdkhwamsamarthkhxngomedltang kkhuxkarsuksaklumkhxngphasathangkar formal language thiomedlehlannsamarthsrangid yktwxyangechn ekhruxngckrsthanacakdsamarthsrangidephiyngphasathiethiybethakbniphcn regular swnekhruxngckrkdlngnnsamarthsrangphasathirabudwyiwyakrnimphungbribthiddwy radbkhwamsamarththangphasathangkarkhxngomedlehlaniepnthimakhxng tarangdanlangaesdngklumkhxngpyha hruxphasa hruxiwyakrn thiphicarnainthvsdikarkhanwnid thaklum X epnsbestaethkhxng Y eracaaesdng X danlang Y aelamiesnthubechuxmrahwangsxngklum tha X epnsbestaetimthrabaennxnwacaethaknhruxim eracaechuxmdwyesnthibangkwaaelaepnesnpra pyhakartdsinicType 0 Recursively enumerable UndecidableDecidableEXPSPACEEXPTIMEType 1 Context Sensitive exnphiBPP BQP exnphibriburnphiNCType 2 Context Free Type 3 Regular xangxingGarey Michael R and David S Johnson Computers and Intractability A Guide to the Theory of NP Completeness New York W H Freeman amp Co 1979 The standard reference on NP Complete problems an important category of problems whose solutions appear to require an impractically long time to compute Hein James L Theory of Computation Sudbury MA Jones amp Bartlett 1996 A gentle introduction to the field appropriate for second year undergraduate computer science students Hopcroft John E and Jeffrey D Ullman Introduction to Automata Theory Languages and Computation Reading MA Addison Wesley 1979 One of the standard references in the field Taylor R Gregory Models of Computation New York Oxford University Press 1998 An unusually readable textbook appropriate for upper level undergraduates or beginning graduate students The Complexity Zoo 2007 11 18 thi ewyaebkaemchchin A huge list of complexity classes as reference for experts Computability Logic 2011 04 11 thi ewyaebkaemchchin A theory of interactive computation The main web source on this new subject duephimComputability logic Interactive computation Important publications in computability Open problems in computability Calculation