تابع Ackermann
سه شنبه, ۱۳ اسفند ۱۳۹۲، ۱۱:۴۹ ب.ظ
در مبحث محاسبه پذیری و توابع Primitive Recursive یا به اختصار PR، ثابت میشه که تمامی توابع PR محاسبه پذیرند، در صورتی که برعکس آن برای تمامی توابع صادق نیست. یعنی حداقل یک تابع وجود دارد که محاسبه پذیر است اما PR نیست. یکی از این توابع، تابع Ackermann است. اثبات PR نبودن این تابع را در فایل زیر نوشته‌ام*.
فاطمه