نظرية الحوسبة

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من النظرية الحسابية)
اذهب إلى التنقل اذهب إلى البحث

نظرية الحوسبة أو النظرية الحسابية أو النظرية الاحتسابية (بالإنجليزية: Theory of Computation) في علم الحاسوب يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب ويدرس ما يمكن للحاسوب أن يقوم باحتسابة حاليا وإمكانية تطوره في المستقبل.[1][2][3] لذلك يمكن تقسيمها إلى : نظرية الحاسوبية ونظرية نظرية التعقيد الحسابي. و كلاهما يتعاملان مع النماذج الرياضية للتحسيب.

لإنجاز دراسة منهجية للتحسيب، يشكل علماء الحاسوب نماذج رياضية مجردة من الحواسيب تدعى نموذج التحسيب model of computation. توجد عدة أنماط من هذه النماذج قيد الاستعمال، لكن أهمها وأكثرها شيوعا هو آلة تورنغ. يمكن أن نتصور آلة تورنغ على أنها حاسوب منزلي مع سعة ذاكرة محدودة، ولايمكن الوصول إلا إلى قطاعات صغيرة متفرقة من هذه الذاكرة. تعتبر آلات تورنغ سهلة التصور والتصميم ومن الممكن تحليلها ودراستها للبرهنة عن النتائج المتوقعة بالتالي تمثل نموذجا معقولا لعملية التحسيب.

شرط محدودية الذاكرة ضروري جدا لأن هذا ما يجعل آلة تورنغ واقعية، ويجعل تنبؤات آلة تورنغ مقبولة فأي مسألة يمكن حلها بوساطة آلو تورنغ يمكن حلها أيضا بوساطة أي حاسوب شخصي ذو ذاكرة كافية.

اقرأ أيضاً[عدل]

مراجع[عدل]

  1. ^ Rabin، Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. 
  2. ^ Donald Monk (1976). Mathematical Logic. Springer-Verlag. ISBN 9780387901701. 
  3. ^ Henry Gordon Rice (1953). "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society. American Mathematical Society. 74 (2): 358–366. JSTOR 1990888. doi:10.2307/1990888. 
Computer.svg
هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال بحاجة للتوسيع. شارك في تحريرها.