نظریه رایانش‌پذیری: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۳:
بدون شك يكي از علل پيشرفت اين نظريه تلاش محققين براي اثبات پاسخ منفي به مساله دهم هيلبرت بوده است.
دانشمندان کامپیوتر، برای مطالعه ی جدی نظریه رایانش( شماره پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترها که مدل رایانش گفته می شود، سر و کار دارند. قاعده سازی های متعددی، برای استفاده وجود دارد، اما ماشین
چون حافظه ی بی نهایت یک نسبت غیر مادی در نظر گرفته می شود، برای هر مسئله که با استفاده از ماشین ترینگ حل می شود، حافظه ی مورد استفاده همواره محدود است. در نتیجه هر مسئله را می توان با استفاده از یک کامپیوتر شخصی که حافظه ی مورد نیاز بر روی آن نصب شده، از طریق یک ماشین
==نظریه شماره پذیری==
خط ۳۰:
;ماشین رجیستر( Register Machine)
یک کامپیوتر ایده آل تئوریک است! متغیرهای بیشتری وجود دارد. در بسیاری از آن ها، هر رجیستر می تواند یک عدد طبیعی با سایز نامحدود، را نگهداری کند، دستور العمل ها ساده هستند؛ برای مثال فقط کاستن پله ای و نمو وجود دارد. کمبود ذخیره ی خارجی که در ماشین های تورینگ دیده می شود، می تواند با جایگذاری نقشش با استفاده از روش های عددی Godel درک شود. این حقیقت که هر رجیستر قابلیت نگهداری یک عدد طبیعی را دارد، امکان نمایش یک چیز پیچیده تر ( مثلاً یک دنباله یا یک ماتریس )، را فراهم می سازد.
همانند ماشین های تورینگ، این روش نیز از نشان های بی نهایت ( بدون دسترسی تصادفی ) استفاده می کند. هم چنین تعداد دستورالعمل ها کمتر است. اما این دستورالعل ها بسیار متفاوت هستند، بنابراین بر خلاف ماشین تورینگ، P" نیازی به نگه داشتن یک حالت مشخص نیست، چرا که تمام عملیات حافظه گونه فقط با استفاده از نوار تامین می شود. به جای دوباره نویسی نشان جاری، می تواند یک نمو حسابی پیمانه ای را انجام دهد.
خط ۳۷:
==منبع==
http://en.wikipedia.org/wiki/Theory_of_computation
Introductory Theory of Computer Science, E. V. Krishnamurthy, East-West Press, 1983
http://www-groups.dcs.st-and.ac.uk/
| |||