موضوع مقاله: نظریه محاسبات | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نظریه محاسبات | مقدمه: این نظریه را به دو شاخهٔ عمده به‌صورت زیر تقسیم می‌کنند: نظریهٔ محاسبه‌پذیری یا قابلیت محاسبه نظریهٔ پیچیدگی هر دو شاخهٔ فوق با مدل‌های صوری محاسبات سر وکار دارد. | ## بخش 1: نظریه محاسبات | تاریخچه در علم رایانه نظری و ریاضیات نظریهٔ رایانش شاخه‌ای است که با توجه به مشکلات می‌توان به آن به عنوان یک مدل محاسبه با استفاده از یک الگوریتم پرداخت. این نظریه را به دو شاخهٔ عمده به صورت زیر تقسیم می‌کنند: نظریهٔ محاسبه‌پذیری یا قابلیت محاسبه نظریهٔ پیچیدگی هر دو شاخهٔ یادشده در بالا با مدل‌های صوری محاسبات سروکار دارد. به منظور انجام یک مطالعه دقیق از محاسبات دانشمندان رایانه با انتزاع ریاضی رایانه به عنوان یک مدل محاسبه کار می‌کنند. مدل‌های بسیاری در این زمینه وجود دارد ولی معمولاً مدل مورد بررسی ماشین تورینگ است. از نظر دانشمندان رایانه مطالعه ماشین تورینگ به این دلیل ساده است که می‌توان با آن به تدوین، فرموله، تجزیه و تحلیل و اثبات نتایج پرداخت. در نظر آن‌ها ماشین تورینگ قدرتمندترین مدل یعنی مدل معقول از محاسبه را ممکن می‌سازد. ظرفیت حافظه به‌طور بالقوه بی‌نهایت یک ویژگی غیرمیسر است؛ در حالی که تصمیم‌های ماشین تورینگ نیاز به تنها مقدار محدودی از حافظه دارد. تصمیم یک ماشین تورینگ را می‌توان با یک رایانه که دارای یک مقدار محدود از حافظه است، حل کرد. | ## بخش 2: نظریه محاسبات | شاخه‌ها نظریهٔ ماشین‌ها نظریهٔ ماشین‌ها عبارت است از مطالعه ماشین آلات انتزاعی (یا ماشین آلات ریاضی یا سیستم) و مسائل محاسباتی است که می‌تواند با استفاده از این دستگاه حل شود. این ماشین آلات از کلمه یونانی می‌آید و به این معنی است که چیزی در حال انجام چیزی خود به خود است. اتوماتیک اغلب به عنوان کلاس از زبان رسمی شناخته می‌شود که قادر به تشخیص طبقه‌بندی است. دستگاه می‌تواند یک نمایندگی محدود، از یک زبان رسمی که ممکن است یک مجموعه نامحدود باشد، باشد. نظریهٔ زبان رسمی نظریهٔ زبان، شاخه‌ای از ریاضیات در رابطه با توصیف زبان به عنوان مجموعه‌ای از عملیات بیش از یک الفبا است. این نظریه با نظریهٔ ماشین‌ها مرتبط است؛ به‌طوری‌که به‌طور اتوماتیک برای تولید و تشخیص زبان رسمی استفاده می‌شود. کلاس زبان‌های رسمی، خصوصیات زبان رسمی که از پیش وجود دارد و مربوط به یک کلاس اتوماتیک است در آن به رسمیت می‌شناسد. نظریهٔ رایانش معادلات نظریهٔ محاسبات در درجه اول با سؤال از میزان یک هم‌شکل قابل حل در یک رایانه است شروع می‌شود. | ## بخش 3: نظریه محاسبات | یکی از نتایج مهم در نظریهٔ محاسبات این است که توقف، توسط یک ماشین تورینگ قابل حل نمی‌باشد. این مشکل یک نمونه از مشکلاتی است که تدوین و فرموله کردن آن با استفاده از یک ماشین تورینگ غیرممکن است. نظریه محاسبات مربوط به شاخه‌ای از منطق ریاضی به نام نظریهٔ بازگشت است که به عنوان مدل محاسبه تقلیل به مدل تورینگ است. نظریهٔ پیچیدگی رایانشی نظریهٔ پیچیدگی عبارت است از این که آیا مشکل روی یک رایانه قابل حل است و این که چگونه این مشکل می‌تواند حل شود. برای این منظور دو جنبه عمده، پیچیدگی زمانی و پیچیدگی فضایی در نظر گرفته می‌شود که به ترتیب یعنی زمان مراحل انجام محاسبات و این که چه مقدار حافظه برای انجام محاسبات مورد نیاز است. برای تجزیه و تحلیل اینکه چقدر زمان و مکان لازم است که به یک الگوریتم داده شود دانشمندان رایانه زمان و فضای مورد نیاز برای حل مشکل را به عنوان یک تابع از اندازه مشکل ورودی بیان می‌کنند. مهم‌ترین مشکل در علوم رایانه این سؤال است که آیا یک کلاس گسترده از برخی مشکلات نشان داده قابل حل است. مدل‌های رایانش محاسبه بازگشتی یعنی دنباله تعریف آن، هر مقدار ورودی و دنباله‌هایی از توابع بازگشتی یعنی ظاهر شدن در دنبالهٔ تعریف با ورودی و خروجی. | ## جمع‌بندی | یک راه برای اندازه‌گیری قدرت یک مدل محاسباتی، مطالعه کلاس زبان رسمی که مدل می‌تواند تولید کند است.