نظریه رایانشپذیری
From Wikipedia, the free encyclopedia
نظریه رایانشپذیری از مباحث پایه در علوم رایانه است که به بررسی محاسبهپذیر و محاسبهناپذیر بودن عملیات با استفاده از ابزارهای کلاسیک نظیر ماشین ثبات، ماشین تورینگ و توابع بازگشتی میپردازد. بدون شک یکی از علل پیشرفت این نظریه تلاش محققان برای اثبات پاسخ منفی به مسئله دهم هیلبرت بودهاست.
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
دانشمندان کامپیوتر، برای مطالعهٔ جدی نظریه رایانش (شمارش پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترها که مدل رایانش گفته میشود، سر و کار دارند. قاعده سازیهای متعددی، برای استفاده وجود دارد، اما ماشین تورینگ(Turing) در این میان بیشترین کاربرد را دارد. یک ماشین تورینگ را میتوان هم ارز یک کامپیوتر شخصی رومیزی، در نظر گرفت، با حافظهٔ بینهایت که به این حافظه از طریق تعداد زیادی تکههای کوچک گسسته، دسترسی دارد. دانشمندان کامپیوتر به دلیل قابلیت سادگی قاعده سازی، تحلیل و آنالیز و قابل استفاده برای اثبات نتایج از این ماشین استفاده میکنند. چون حافظهٔ بینهایت یک نسبت غیر مادی در نظر گرفته میشود، برای هر مسئله که با استفاده از ماشین تورینگ حل میشود، حافظهٔ مورد استفاده همواره محدود است. در نتیجه هر مسئله را میتوان با استفاده از یک کامپیوتر شخصی که حافظهٔ مورد نیاز بر روی آن نصب شده، از طریق یک ماشین تورینگ حل کرد.