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

از ویکی‌پدیا، دانشنامهٔ آزاد

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

تعریف[ویرایش]

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

نمونه‌ها[ویرایش]

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

  • توابع بازگشتی محدود کننده و توابع بازگشتی بخشی محدود کننده
  • استنادهای آزمون و خطا * ماشین‌های تورینگ استدلالی، که محاسباتی شبیه به محاسبات ماشین‌های تورینگ را انجام می‌دهند و نتایج آن‌ها را پس از تعداد قدم‌های محدودی تولید می‌کنند.
  • ماشین‌های تورینگ محدود، که محاسباتی شبیه به محاسبات ماشین‌های تورینگ انجام می‌دهند اما نتایج آن‌ها حدود نتایج میانی آن‌ها می‌باشد.
  • ماشین‌های آزمون و خطا
  • ماشین‌های تورینگ عمومی
  • ماشین‌های اینترنتی
  • رایانه‌های تکاملی، که از DNA برای تولید مقدار توابع استفاده می‌کنند.
  • محاسبات تاری
  • ماشین‌های تورینگ تکاملی

مثال‌هایی از قالب‌های الگوریتمی شامل موارد زیر می‌شود:

  • ماشین‌های تورینگ با خرد خودسرانه
  • عمل گرهای فرا بازگشتی
  • ماشین‌هایی که با اعداد حقیقی محاسبه می‌کنند
  • شبکه‌های عصبی بر پایهٔ اعداد حقیقی.

برای دیگر مثال‌های عملی الگوریتم‌های مافوق بازگشتی به کتاب بورگین مراجعه نمایید.

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

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

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

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

پی‌نوشت‌ها[ویرایش]

  1. ↑ Mark Burgin
  2. ↑ Super-recursive algorithms
  3. ↑ Selim Akl
  4. ↑ Eugene Eberbach
  5. ↑ Peter Kugel
  6. ↑ Jan van Leeuwen
  7. ↑ Hava Siegelmann
  8. ↑ Peter Wegner
  9. ↑ Jiří Wiedermann
  10. ↑ Hypercomputation

منابع[ویرایش]

  • Akl, S.G. , Three counterexamples to dispel the myth of the universal computer, Parallel Processing Letters, Vol. 16, No. 3, September 2006, pp. 381 - 403.
  • Akl, S.G. , The myth of universal computation, in: Parallel Numerics, Trobec, R. , Zinterhof, P. , Vajtersic, M. , and Uhl, A. , Eds. , Part 2, Systems and Simulation, University of Salzburg, Salzburg, Austria and Jozef Stefan Institute, Ljubljana, Slovenia, 2005, pp. 211 - 236
  • Angluin, D. , and Smith, C. H. (1983) Inductive Inference: Theory and Methods, Comput. Surveys, v. 15, no. 3, pp. 237—۲۶۹
  • Apsïtis, K, Arikawa, S, Freivalds, R. , Hirowatari, E. , and Smith, C. H. (1999) On the inductive inference of recursive real-valued functions, Theoret. Computer Science, 219(1-2): 3—۱۷
  • Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, Transactions of the American Mathematical Society, v. 92, pp. 85-105
  • Blum, L. , and Blum, M. (1975) Toward a mathematical theory of inductive inference. Information and Control vol. 28, pp. 125-155
  • Blum, L. , F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer 1998
  • Boddy, M, Dean, T. 1989. "Solving Time-Dependent Planning Problems". Technical Report: CS-89-03, Brown University
  • Borodyanskii, Yu. M. and Burgin, M.S. (1994) Operations with Transrecursive Operators, Cybernetics and System Analysis, No. 4, pp. 3-11
  • Burgin, Mark (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
  • Burgin, M. How We Know What Technology Can Do, Communications of the ACM, v. 44, No. 11, 2001, pp. 82-88
  • Burgin M. , Universal limit Turing machines, Notices of the Russian Academy of Sciences, 325, No. 4, (1992), 654-658
  • Burgin, M. and Klinger, A. Three Aspects of Super-recursive Algorithms and Hypercomputation or Finding Black Swans, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 1-11
  • Burgin, M. Algorithmic Complexity of Recursive and Inductive Algorithms, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 31-60
  • Burgin, M. and Klinger, A. Experience, Generations, and Limits in Machine Learning, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 71-91
  • Campagnolo, M.L. , Moore, C. , and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91-109
  • Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461-502
  • Davis, Martin (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
  • Eberbach, E. (2005) Toward a theory of evolutionary computation, BioSystems 82, 1-19
  • Eberbach, E. , and Wegner, P. , Beyond Turing Machines, Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304
  • کورت گودل، ۱۹۳۱, "Über formal unentscheidbare Sätze der مبادی ریاضیات und verwandter Systeme," Monatshefte für Mathematik und Physik 38: 173-98.
  • Gold, E.M. Limiting recursion. J. Symb. Logic 10 (1965), 28-48.
  • Gold, E.M. (1967) Language Identification in the Limit, Information and Control, v. 10, pp. 447-474
  • Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation – Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
  • Hintikka, Ja. and Mutanen, A. An Alternative Concept of Computability, in “Language, Truth, and Logic in Mathematics”, Dordrecht, pp. 174-188, 1998
  • E.J. Horvitz. Reasoning about inference tradeoffs in a world of bounded resources. Technical Report KSL-86-55, Medical Computer Science Group, Section on Medical Informatics, Stanford University, Stanford, CA, مارس ۱۹۸۶
  • Juraj Hromkovič, Design and Analysis of Randomized Algorithms, Springer, 2005
  • Kleene, Stephen C. (First Edition 1952), Introduction to Metamathematics, Amsterdam: North-Holland {{citation}}: Check date values in: |year= (help).
  • Kosovsky, N. K. (1981) Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ. , Leningrad
  • Peter Kugel, It's time to think outside the computational box, Communications of the ACM, Volume 48, Issue 11, نوامبر ۲۰۰۵
  • Petrus H.Potgieter, Zeno machines and hypercomputation, Theoretical Computer Science, Volume 358, Issue 1 (ژوئیه ۲۰۰۶) pp. 23 - 33
  • Hilary Putnam, Trial and Error Predicates and the Solution to a Problem of Mostowski. J. Symbolic Logic, Volume 30, Issue 1 (1965), 49-57
  • Darko Roglic, "The universal evolutionary computer based on super-recursive algorithms of evolvability"
  • J. Schmidhuber (2000): Algorithmic Theories of Everything http://arxiv.org/abs/quant-ph/0011122
  • J. Schmidhuber (2002): Hierarchies of generalized آندره کولموگروف complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612 http://www.idsia.ch/~juergen/kolmogorov.html
  • Hava Siegelmann, Neural Networks and Analog Computation: Beyond the Turing Limit, Birkhauser, 1999
  • Turing, A. (1939) Systems of Logic Based on Ordinals, Proc. Lond. Math. Soc., Ser.2, v. 45: 161-228
  • van Leeuwen, J. and Wiedermann, J. (2000a) Breaking the Turing Barrier: The case of the Internet, Techn. Report, Inst. of Computer Science, Academy of Sciences of the Czech. Rep. , Prague
  • Jiří Wiedermann, Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, Theoretical Computer Science, Volume 317, Issue 1-3, ژوئن ۲۰۰۴
  • Jiří Wiedermann and Jan van Leeuwen, The emergent computational potential of evolving artificial living systems, AI Communications, v. 15, No. 4, 2002
  • Hector Zenil and Francisco Hernandez-Quiroz, On the possible computational power of the human mind, Worldviews, Science and Us, edited by Carlos Gershenson, Diederik Aerts and Bruce Edmonds, World Scientific, 2007, (arXiv:cs.NE/0605065v3)
  • S. Zilberstein, Using Anytime Algorithms in Intelligent Systems, "AI Magazine", 17(3):73-83, 1996

مطالعهٔ بیشتر[ویرایش]

برگرفته از «https://fa.wikipedia.org/w/index.php?title=الگوریتم‌های_مافوق_بازگشتی&oldid=36007864»