علم الحاسوب النظري: الفرق بين النسختين

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

'''نظرية التحسيبالحاسوب''' '''theory of computation''' هي فرع من المعلوماتية يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة [[حاسوب]]. لذلك يمكن تقسيمها إلى : [[نظرية الحاسوبية]] و[[نظرية التعقيد الحسابي]].و كلاهما يتعاملان مع [[نموذج التحسيب|النماذج الشكلية للتحسيب]].

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

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