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

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

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