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

 

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

 

== نظریه شماره پذیری ==

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

 

== نظریه پیچیدگی ==

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

 

== حساب لامبدا ==

؛ الگوریتم مارکف

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

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

;P