Enumerability · Decidability Computability: An Introduction to the Theory of Recursive Functions

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

Once we have accepted a precise replacement of the concept of algo­ rithm, it becomes possible to attempt the problem whether there exist well-defined collections of problems which cannot be handled by algo­ rithms, and if that is the case, to give concrete cases of this kind. Many such investigations were carried out during the last few decades. The undecidability of arithmetic and other mathematical theories was shown, further the unsolvability of the word problem of group theory. Many mathematicians consider these results and the theory on which they are based to be the most characteristic achievements of mathe­ matics in the first half of the twentieth century. If we grant the legitimacy of the suggested precise replacements of the concept of algorithm and related concepts, then we can say that the mathematicians have shown by strictly mathematical methods that there exist mathematical problems which cannot be dealt with by the methods of calculating mathematics. In view of the important role which mathematics plays today in our conception of the world this fact is of great philosophical interest. Post speaks of a natural law about the "limitations of the mathematicizing power of Homo Sapiens". Here we also find a starting point for the discussion of the question, what the actual creative activity of the mathematician consists in. In this book we shall give an introduction to the theory of algorithms.