الگوریتم‌های مافوق بازگشتی

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

تعریف

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

ماشین‌های تورینگ استدلالی

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

ارتباط با قضیه چرچ-تورینگ

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