سلام رفقا.
برای اینکه اینجا بحث استارت بخوره با یه سوال کوتاه شروع میکنم.
اولین سوال من ایه:
###### (سوال۱)
آیا تابع بازگشتی جزئی همون تابع بازگشتی اولیه هست؟!
Partially recursive ?= primitive recursive
طبق تعریف کتاب دیویس بازگشتی اولیه به تابعی میگویند که با تعداد متناهی عملیات ترکیب و بازگشت روی توابع آغازین بشه به اون رسید!
اما نمیدونم بازگشتی جزئی هم همینه؟!
جواب سوال رو پیدا کردم.
کتاب Davis صفحه ی ۳۰ دقیقا توضیح داده که:
Partially computable functions are also called partial recursive
که یعنی بازگشتی جزئی دقیقا همون محاسبه پذیر جزئی و به هیچ وجه برابر بازگشتی اولیه نیست.
چرا که بازگشتی اولیه ها همیشه محاسبه پذیر هستند. ولی بازگشتی جزئی(محاسبه پذیر جزئی) فقط وقتی محاسبه پذیره که تابع معادلش کامل باشه.