تابع Ackermann

در مبحث محاسبه پذیری و توابع Primitive Recursive یا به اختصار PR، ثابت میشه که تمامی توابع PR محاسبه پذیرند، در صورتی که برعکس آن برای تمامی توابع صادق نیست. یعنی حداقل یک تابع وجود دارد که محاسبه پذیر است اما PR نیست. یکی از این توابع، تابع Ackermann است. اثبات PR نبودن این تابع را در فایل زیر نوشته‌ام*.

دانلود

---

* منبع اصلی این اثبات این لینک است که من اثبات‌های تمامی لم‌های آن را در فایل خودم آورده‌ام.