نظریه رایانش‌پذیری: تفاوت میان نسخه‌ها

بدون شكشک يكيیکی از علل پيشرفتپیشرفت ايناین نظريهنظریه تلاش محققينمحققین برايبرای اثبات پاسخ منفيمنفی به مساله دهم هيلبرتهیلبرت بوده استبوده‌است.

دانشمندان کامپیوتر، برای مطالعه یمطالعهٔ جدی نظریه رایانش( شماره پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترها که مدل رایانش گفته می شود،می‌شود، سر و کار دارند. قاعده سازی هایسازی‌های متعددی، برای استفاده وجود دارد، اما ماشین تورینگ( Turing ) در این میان بیش ترین کاربرد را دارد. یک ماشین تورینگ را می توانمی‌توان هم ارز یک کامپیتر شخصی رومیزی، در نظر گرفت، با حافظه یحافظهٔ بی نهایت که به این حافظه از طریق تعداد زیادی تکه هایتکه‌های کوچک گسسته، دسترسی دارد. دانشمندان کامپیوتر به دلیل قابلیت سادگی قاعده سازی، تحلیل و آنالیز و قابل استفاده برای اثبات نتایج از این ماشین استفاده می کنندمی‌کنند.

چون حافظه یحافظهٔ بی نهایت یک نسبت غیر مادی در نظر گرفته می شود،می‌شود، برای هر مسئله که با استفاده از ماشین ترینگ حل میمی‌شود، شود، حافظه یحافظهٔ مورد استفاده همواره محدود است. در نتیجه هر مسئله را می توانمی‌توان با استفاده از یک کامپیوتر شخصی که حافظه یحافظهٔ مورد نیاز بر روی آن نصب شده، از طریق یک ماشین تورینگ حل کرد.

[[نظریه شماره پذیری،پذیری]]، با این سوال که آیا یک مسئله قابل حل بر روی یک کامپیوتر هست یا نه، سر و کار دارد. مسئله یمسئلهٔ halting یکی از مهم ترین نتایج در نظریه ینظریهٔ شماره پذیری است. این مسئله به آسانی قابل قاعده سازی و به سختی با استفاده از ماشین ترینگ قابل حل است! بخش عمده ایعمده‌ای از نظریه ینظریهٔ شماره پذیری، بر نتیجه ی مسئلهنتیجهٔ یمسئلهٔ halting، استوار است.

نظریه ینظریهٔ شماره پذیری، با یک شاخه از منطق ریاضی به نام نظریه ینظریهٔ بازگشت، در ارتباط تنگاتنگ است. بسیاری از ریاضی دانان و نظریه پردازان شمارش پذیری، که دربارهدربارهٔ ی نظریه ینظریهٔ بازگشت به مطالعه می پردازند،می‌پردازند، این نظریه را در آخر به نظریه ینظریهٔ شماره پذیری ارجاع می دهندمی‌دهند.

[[نظریه ی پیچیدگی،پیچیدگی]]، نه تنها با این موضوع که آیا مسئله یمسئلهٔ مطرح شده بر روی کامپیوتر قابل حل هست یا نه؛ بلکه با این موضوع که چقدر مسئله می تواندمی‌تواند به صورت کارآمد حل شود، در ارتباط است. دو جنبه یجنبهٔ مهم در این نظریه مطرح است: پیچیدگی زمان و پیچیدگی فضا. یعنی برای حل مسئله چند پله باید طی شود و به چقدر حافظه نیاز است.

برای تحلیل این که یک الگوریتم به چقدر زمان و حافظه نیاز دارد، دانشمندان کامپیوتر زمان و حافظه ایحافظه‌ای را که برای حل یک مسئله مورد نیاز است، به عنوان یک تابع از سایز ورودی مسئله بیان می کنندمی‌کنند. برای مثال پیدا کردن یک عدد خاص در یک لیست بلند از اعداد دشوارتر می شودمی‌شود هنگامی که تعداد اعداد افزایش می یابدمی‌یابد.. اگر n عدد در لیست وجود داشته باشد که مرتب نشده باشند و یا اندیس گذاری نشده باشند در هر صورت ما باید همه یهمهٔ اعداد را برای پیدا کردن عدد خاص، چک کنیم. بنابراین در این مثال برای حل مسئله یمسئلهٔ مطرح شده، کامپیوتر باید مراحلی را طی کند که تعداد آن هاآن‌ها به صورت خطی تغییر می کندمی‌کند.

;==[[حساب لامبدا]]==

یک سیستم رشته ایرشته‌ای با قابلیت دوباره نویسی، که از قوانین گرامری شکلی برای به کار انداختن رشته هارشته‌ها استفاده می کندمی‌کند.

;ماشین رجیستر( Register Machine)

یک کامپیوتر ایده آل تئوریک است! متغیرهای بیشتری وجود دارد. در بسیاری از آن ها،آن‌ها، هر رجیستر می تواندمی‌تواند یک عدد طبیعی با سایز نامحدود، را نگهداری کند، دستور العمل هاالعمل‌ها ساده هستند؛ برای مثال فقط کاستن پله ایپله‌ای و نمو وجود دارد. کمبود ذخیره یذخیرهٔ خارجی که در ماشین هایماشین‌های تورینگ دیده می شود، میمی‌شود، تواندمی‌تواند با جایگذاری نقشش با استفاده از روش هایروش‌های عددی Godel درک شود. این حقیقت که هر رجیستر قابلیت نگهداری یک عدد طبیعی را دارد، امکان نمایش یک چیز پیچیده تر ( مثلاً یک دنباله یا یک ماتریس )، را فراهم می سازدمی‌سازد.

همانند ماشین هایماشین‌های تورینگ، این روش نیز از نشان هاینشان‌های بی نهایت ( بدون دسترسی تصادفی ) استفاده می کندمی‌کند. هم چنین تعداد دستورالعمل هادستورالعمل‌ها کمتر است. اما این دستورالعل هادستورالعل‌ها بسیار متفاوت هستند، بنابراین بر خلاف ماشین تورینگ، P" نیازی به نگه داشتن یک حالت مشخص نیست، چرا که تمام عملیات حافظه گونه فقط با استفاده از نوار تامین می شودمی‌شود. به جای دوباره نویسی نشان جاری، می تواندمی‌تواند یک نمو حسابی پیمانه ایپیمانه‌ای را انجام دهد.

Introductory Theory of Computer Science, E. V. Krishnamurthy, East-West Press, 1983۱۹۸۳