مسئله توقف

مسئله توقف (به انگلیسی: halting problem) در نظریه محاسبه‌پذیری، یک مسئله در مورد جواب‌دادن به این سوال است که: آیا از «توصیف یک برنامه رایانه‌ای اختیاری» و یک «ورودی»، مسئله اجرایش را «تمام(متوقف)» می‌کند، یا نه (یعنی برای همیشه اجرا خواهد شد). آلن تورینگ در سال ۱۹۳۶ اثبات کرد که یک الگوریتم همگانی برای حل مسئله توقف (یعنی برای همه جفت‌های «ورودی-برنامه» ممکن) وجود ندارد. یعنی مسئله توقف بر روی ماشین تورینگ تصمیم‌پذیر نیست.

مسئله توقف از دسته مسائل تصمیم‌گیری است که دربارهٔ صفات یک برنامه کامپیوتری با استفاده از یک ماشین تورینگ تعریف شده (ماشینی برنامه‌پذیر که قابلیت انجام هر محاسبه‌ای را دارد) بحث می‌کند. می‌توان به شکل زیر آن را بیان کرد:

اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا می‌توان تشخیص داد که این برنامه متوقف می‌شود یا تا ابد ادامه می‌یابد.

در این مسئله هیچ شرطی بر روی زمانی که طول می‌کشد تا برنامه تمام شود یا حافظه‌ای که اشغال می‌کند وجود ندارد، یعنی ممکن است اجرای برنامه زمان زیادی طول بکشد، یا حافظه زیادی اشغال شود تا برنامه تمام شود؛ یعنی سؤال این است که آیا بالاخره این برنامه تمام می‌شود یا تا ابد ادامه پیدا می‌کند.

آلن تورینگ از پیش‌گامان کار بر مسئله توقف بود.

مثال

برای مثال به برنامه زیر که به زبان سی نوشته توجه کنید:

int main(void)

{ while (1); }

این برنامه هیچ‌گاه متوقف نمی‌شود و در این حلقه گیر می‌کند. از طرف دیگر در برنامه زیر داریم:

int main(void) { printf("Hello, world");

return 0; }

که در این برنامه بدون توجه به ورودی متوقف می‌شود.

اهمیت و نتایج مسئله توقف

در کل مسئله توقف از این جنبه مشهور است که از اولین دسته مسائلی بود که تصمیم ناپذیر بود، بدین صورت که هیچ برنامه کامپیوتری با قابلیت جواب دادن به این سؤال به ازای جمیع ورودی‌ها پیدا نشد و اثبات شد که وجود ندارد. در نتیجه آن تعدادی زیادی مسائلی از این دست بیان شدند. راه حل رایج برای اثبات کردن اینکه یک مسئله تصمیم ناپذیر است استفاده از روش کاهیدن (reduction) است.

یکی از نتایج تصمیم ناپذیر بودن مسئله توقف این است که الگوریتمی عمومی برای پیدا کردن درستی یا نادرستی یک حکم دربارهٔ اعداد طبیعی وجود ندارد. چون می‌توان گزاره‌ای که نشان می‌دهد آیا یک الگوریتم با ورودی‌های مربوط به آن متوقف می‌شود یا نه را متناظر با یک حکم دربارهٔ اعداد طبیعی در نظر گرفت. چون می‌دانیم که این همان مسئله توقف است پس چنین الگوریتمی برای اعداد طبیعی پیدا نمی‌شود.

یکی دیگر از نتایج تصمیم ناپذیری مسئله توقف تئوری Rice's theorem است که می‌گوید به‌طور کلی نمی‌توان دربارهٔ درستی هرعبارت نا بدیهی (non-trival) مربوط به تابعی که توسط یک الگوریتم تعریف شده نظر داد. برای مثال نمی‌توان به سؤال «آیا این الگوریتم با ورودی 0 متوقف می‌شود یا نه» پاسخ قطعی داد. توجه کنید که این تئوری دربارهٔ تابعی که توسط الگوریتم تعریف شده نظر می‌دهد و نه دربارهٔ خود الگوریتم. برای مثال تشخیص اینکه یک الگوریتم در 100 مرحله متوقف می‌شود یا نه کار آسانی است و این یک گزاره دربارهٔ خود الگوریتم است و نه دربارهٔ تابع آن الگوریتم.

رسمی کردن مسئله توقف

تورینگ در اثبات خود ایده‌آلگوریتم را با تعریف ماشین تورینگ رسمی‌کرد، گرچه به هیچ وجه نتیجه مخصوص آن‌ها نیست و به‌طور مساوی در مدل‌های دیگر محاسبه که متناظر با توان محاسباتی با ماشین تورینگ هستند به کار بسته می‌شود مانند markov algothims, Lambda calculus یا Post systems

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

اثبات

این اثبات نشان می‌دهد که یک تابع به ازای جمیع حالات که تصمیم بگیرد که برنامهٔ i با ورودی دلخواه x آیا متوقف می‌شود یا نه وجود ندارد؛ یعنی تابع h که با شرایط زیر وجود ندارد :

اگر برنامه متوقف شود

اگر برنامه متوقف نشود

زیرا اگر برنامه K را چنان فرض کنیم که به صورت زیر باشد به تناقض می‌رسیم:

Program K(program A)

{

if(h(A,A)==1)

{

While(true);

}

}

اگر فرض کنیم که خود این برنامه K به عنوان ورودی به خودش داده شود به تناقض خواهیم رسید زیرا اگر h(k,k)=1 در این صورت برنامه متوقف نخواهد شد و در while(true) خواهد ماند اما خود h(k,k)=1 به این معنا است که باید برنامه متوقف شود که تناقض می‌باشد . حالت h(k,k)=0 نیز مشابهاً به تناقض می‌رسد.

پیوند به بیرون

منابع
    • Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230–265. online version This is the epochal paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.
    • Sipser, Michael (2006). "Section 4.2: The Halting Problem", Introduction to the Theory of Computation, Second Edition, PWS Publishing, pp. 173–182. ISBN 0-534-94728-X.
    • Wiki:HaltingProblem
    • B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7.
    • Martin Davis, The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
    • Martin Davis, Computability and Unsolvability, McGraw-Hill, New York, 1958.
    • Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
    • Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines for the non-specialist. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Discusses Chaitin proof. Includes little biographies of Emil Post, Julia Robinson.
    • Marvin Minsky, Computation, Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967. See chapter 8, Section 8.2 "The Unsolvability of the Halting Problem." Excellent, i.e. readable, sometimes fun. A classic.
    • Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An overly-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
    • John Hopcroft and Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass, 1979. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
    • Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
    • Constance Reid, Hilbert, Copernicus: Springer-Verlag, New York, 1996 (first published 1970). Fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
    • Edward Beltrami, What is Random? Chance and order in mathematics and life, Copernicus: Springer-Verlag, New York, 1999. Nice, gentle read for the mathematically-inclined non-specialist, puts tougher stuff at the end. Has a Turing-machine model in it. Discusses the Chaitin contributions.
    • Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958. Wonderful writing about a very difficult subject. For the mathematically-inclined non-specialist. Discusses Gentzen's proof on pages 96–97 and footnotes. Appendices discuss the Peano Axioms briefly, gently introduce readers to formal logic.
    • Taylor Booth, Sequential Machines and Automata Theory, Wiley, New York, 1967. Cf Chapter 9, Turing Machines. Difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. Has a Turing Machine model in it. References at end of Chapter 9 catch most of the older books (i.e. 1952 until 1967 including authors Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado) and various technical papers. See note under Busy-Beaver Programs.
    • Busy Beaver Programs are described in Scientific American, August 1984, also March 1985 p. 23. A reference in Booth attributes them to Rado, T.(1962), On non-computable functions, Bell Systems Tech. J. 41. Booth also defines Rado's Busy Beaver Problem in problems 3, 4, 5, 6 of Chapter 9, p. 396.
    • David Bolter, Turing’s Man: Western Culture in the Computer Age, The University of North Carolina Press, Chapel Hill, 1984. For the general reader. May be dated. Has yet another (very simple) Turing Machine model in it.
    • Stephen Kleene, Introduction to Metamathematics, North-Holland, 1952. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.