دانش‌اموزان پس از مطالعه‌ي اين زنگ تفريح به امور ذيل قادر خواهند شد:

يكي از روش‌هاي قدرتمند اثبات در رياضيات و كامپيوتر «استقرا» است. «استقراي رياضي» (Mathematical Induction) مي‌گويد: فرض كنيد مجموعه‌اي از اعداد طبيعي و عدد «صفر» را دراختيار داريد. فرض كنيد هرگاه عدد ، عضو مجموعه باشد عدد  نيز عضوي از آن مجموعه باشد. بنابراين همه‌ي اعداد طبيعي عضو اين مجموعه هستند.

اگر بخواهيم غيررسمي‌تر مطلب را توضيح دهيم مي‌گوييم: فرض كنيد مجموعه‌اي از اعداد را گردهم آورده‌ايد و در اين مجموعه «صفر» نيز قرار دارد. اما متوجه مي‌شويد به‌ازاي هر  كه در اين مجموعه قرار دارد عدد  موجود است. بدين‌ترتيب شما مجموعه‌اي بزرگ از «اعداد طبيعي» را در اختيار داريد.

اساساً «استقراي رياضي» بر اين روش استوار است كه از عدد «صفر» آغاز كنيد و هر بار يك عدد 1 به آن اضافه كنيد. سرانجام براي همه‌ي اعداد به‌دست خواهيد آورد.

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

موارد ذيل در «استقراي رياضي» نشان داده مي‌شود:

	- جمله به‌ازاي  صحيح است
	- اگر جمله براي عدد  صادق باشد براي عدد بعدي  نيز صدق خواهد كرد: (رابطه‌‌ي 1)

اگر بتوانيم دو گزاره‌ي بالا را ثابت كنيم براساس «استقراي رياضي»، جمله براي تمام اعداد طبيعي نيز صادق خواهد بود زيرا گزاره‌ي اول مي‌گويد: مجموعه‌ي  براي عضو «صفر» از مجموعه صادق است. گزاره‌ي دوم نيز مي‌گويد وقتي جمله براي عدد  صادق است  نيز در آن مجموعه جاي خواهد داشت؛ بنابراين مجموعه‌ي مذكور شامل همه‌ي اعداد طبيعي و صفر است.

مطابق «استقراي قوي» اگر بدانيم عدد  در مجموعه‌ي مذكور است هرگاه  در آن مجموعه باشد هر عددي نيز در آن مجموعه خواهد بود.

ياداوري – چون هيچ عددي كوچك‌تر از «صفر» در مجموعه نيست «صفر» بايد در مجموعه وجود داشته باشد.

(رابطه‌‌ي 2)

براي اثبات «استقراي قوي» (Strong Induction) چنين گفته‌اند: اگر زيرمجموعه‌اي از مجموعه‌ي مذكور را به‌گونه‌اي تعريف كنيم كه شامل اعدادي باشد كه براي هر عدد، عدد بعدي نيز وجود داشته باشد، «صفر» قطعاً عضو اين زيرمجموعه خواهد بود. اگر  را به‌عنوان عضوي از اين مجموعه فرض كنيم همه‌ي اعداد بعد از آن نيز در مجموعه‌‌ي اصلي وجود دارد؛ از طرفي طبق فرض، نيز در اين زيرمجموعه وجود دارد. بنابراين زيرمجموعه شامل تمام اعدادي خواهد بود كه مجموعه‌ي اصلي شامل آن است!

الف – «استقراي قوي» بيان مي‌دارد براي همه‌ي اعداد ، گزاره‌ي  صادق است:

اين مثالي از اثبات به‌طريق «استقراي قوي» است؛ به‌عبارت ديگر در اين روش از وضعيت جزو، وضعيت كل نتيجه مي‌شود. اما به هر حال نسبت به نتيجه مطمئن نيستيم مگر آن‌كه احتمال ديگر رنگ‌ها را از كلاغ منتفي كنيم. بنابراين نتيجه ممكن است عملاً غلط باشد.

به‌عنوان مثال: شخصي ممكن است با مطالعه بر روي ژنوم پرنده، پرنده‌اي بدون جهش يا تغيير طولاني‌مدت در نتيجه‌ي توليد نسل با رنگ غيرسياه توليد كند. حتي ممكن است كلاغ‌هاي بي‌رنگ يافته و بدين‌ترتيب بتوانيم كلاغ‌هايي با رنگ روشن توليد كنيم.

حتي اگر تعريف «كلاغ» براي سياهي رنگ تغيير دهيم ممكن است بي‌رنگي و در نتيجه كلاغ با رنگ روشن را بيابيم.

ب – در «استقراي رياضي» براي اعداد ، صدق گزاره‌ي  ثابت مي‌شود.

اين مثالي از اثبات به‌طريق «استقراي رياضي» است. فرض كنيد گزاره‌ي اول صحيح باشد در اين مثال گزاره‌ي «من هميشه تصاوير را بر روي ميخ نصب مي‌كنم» به «همه‌ي تصاوير بر روي ميخ نصب مي‌شوند» تعميم يافته است. اما به هر حال رابطه‌ي بين «شرط استقرا» با «نتيجه» ضعيف است. هيچ دليلي وجود ندارد اعتقاد داشته باشيم چون يك نفر تصاوير را بر روي ميخ آويزان مي‌كند راه‌هاي ديگري براي آويزان كردن تصاوير وجود نداشته باشد يا اين‌كه افراد نمي‌توانند كارهاي ديگري با تصاوير انجام دهند.

به‌علاوه همه‌ي تصاوير از ميخ آويزان نمي‌شوند. هم‌چنين همه‌ي تصاوير آويزان نمي‌گردند. «نتيجه» نمي‌تواند با قوت از «شرط» استقرا به‌دست آيد.

اين در حالي است كه با جستجوي اطلاعات ديگر به‌راحتي مي‌بينيم كه اين مثال استقرا ما را به نتيجه‌اي به‌وضوح نادرست هدايت كرده است. نتايج به‌دست آمده از «استقراي رياضي» معمولاً افراطي است.

به مثال ذيل توجه فرماييد:

در اين مثال، «شرط استقرا» برپايه‌ي يقين به‌دست آمده است. اما به هر حال، نتيجه از اين فرض به‌دست نمي‌آيد. مشاهده شده است كه همه‌ي نوجوانان خوش‌شانس هستند. به‌عبارت ديگر، برعكس جمله‌ي «خورشيد هر صبح بالا مي‌آيد»، مثال‌هاي بي‌شماري از نوجوانان وجود دارد كه موفق به برنده شدن در قرعه‌كشي نشده‌اند.

در هر دو مثال اخير، ارتباط منطقي بين «شرط» و «نتيجه» (با كلمه‌ي «بنابراين») ناقص است و براي ما حكمي منطقي و در عين حال استقرايي قوي فراهم نمي‌كند.

اگر بتوانيم مسأله‌اي را به بخش‌هاي كوچك‌تر تقسيم كنيم و بخش‌هاي كوچك‌تر حل‌شدني باشند روشي براي حل آن مسأله يافته‌ايم و فرقي ندارد كه مسأله چقدر بزرگ باشد. اين امر را به‌وسيله‌ي «استقرا» انجام مي‌دهند. بنابراين بحث «استقرا» در علوم كامپيوتر در مبحث «بازگشت» (Recursion) مطرح مي‌شود.

به‌عنوان مثال، فرض كنيم مختصات رؤوس يك چندضلعي داده شده است (همان‌طور كه بديهي است چندضلعي از چند رأس متمايز تشكيل شده كه اضلاع آن يكديگر را قطع نمي‌كنند)؛ مي‌خواهيد چندضلعي را به چند مثلث تقسيم كنيم. اگر بتوانيم برنامه‌اي بنويسيم كه يك چندضلعي بزرگ را به دو چندضلعي كوچك‌تر تقسيم كند خواهيم فهميد كه مي‌توانيم همه‌ي چندضلعي‌ها را به مثلث‌هايي تقسيم كند. بدين‌ترتيب چندضلعي بزرگ‌تر را به دو چندضلعي كوچك‌تر تقسيم كرده و سپس اين فرايند را تكرار مي‌كنيم تا چندضلعي‌هاي كوچك‌تري به‌دست آيد.

«تابع آكرمن» (Ackermann's Function) نمونه‌اي از توابع «بازگشتي» (Recursive) و شامل زوج‌هاي اعداد طبيعي به‌شكل ذيل است:

(رابطه‌‌ي 4)

براي مقادير كوچك  نظير: 1، 2 يا 3، «تابع آكرمن» با سرعت نسبتاً كمي نسبت به  (حداقل به‌صورت تابع نمايي) رشد مي‌كند. اما به هر حال براي سريع‌تر رشد مي‌يابد به‌طوري كه داريم:

(رابطه‌ي 5)

اين در حالي است كه بسط  برمبناي ده، بسيار بزرگ است.

برخي از بسط‌هاي «تابع آكرمن» (Ackermann's Function) ذيلاً تقديم شده است:

بسط  به‌شكل ذيل است:

بسط  به‌شكل ذيل است:

(رابطه‌ي 7)

از طرفي پس از جستجو، مقدار  قبلاً به‌صورت ذيل محاسبه شده است:

(رابطه‌ي 8)

همان‌طور كه مشاهده مي‌كنيد  عدد بسيار بزرگي است.

در جدول 1 بعضي از مقادير «تابع آكرمن» (Ackermann's Function) ذكر شده است.

همان‌طور كه ملاحظه مي‌كنيد محاسبه‌ي مقادير اين تابع به‌سادگي ميسر نمي‌شود. اگرچه اين نوع بازگشت محدود است به‌خاطر آن‌كه يا  كاهش مي‌يابد يا ثابت باقي مي‌ماند و  نيز كاهش مي‌يابد. هر بار كه  به «صفر» مي‌رسد  نيز سرانجام به «صفر» مي‌رسد. اما به هر حال، زماني كه  كاهش مي‌يابد كران بالايي براي چگونگي افزايش  وجود نداشته اغلب خيلي زياد افزايش مي‌يابد.

اگر تابعي نظير  تعريف كنيم كه در آن هم  و هم  با هم افزايش يابند تابعي يك متغيره خواهيم داشت كه در زمره‌ي «توابع بازگشتي اوليه‌ي» (Primitive Recursive Function) كوتاه محسوب مي‌شوند. از اين جمله مي‌توان به توابع ذيل اشاره كرد:

به‌علت رشد بسيار بزرگ «تابع آكرمن» (Ackermann's Function)، واضح است كه در ماشين‌هاي محاسبه‌اي با حافظه‌اي نامحدود نظير: «ماشين تورينگ» (Turing Machine) محاسبه‌پذير بوده لذا «تابع محاسبه‌اي» (Computable Function) هستند. از طرفي به‌علت رشد بسيار سريعي كه نسبت به «تابع بازگشتي اوليه» (Primitive Recursive Function) دارند «بازگشتي اوليه» (Primitive Recursive) محسوب نمي‌شوند لذا اغلب به‌عنوان مثالي براي كم‌ارزش كردن اين فرضيه به‌كار مي‌رود كه مي‌گويد: «همه‌ي توابع ساده يا مفيد «بازگشتي اوليه» (Primitive Recursive) هستند». در عين حال نبايد «توابع بازگشتي اوليه» (Primitive Recursive Function) را با «بازگشت اوليه» (Primitive Recursion) اشتباه كرد.

لازم به‌ذكر است نظريه‌پردازان زبان‌هاي برنامه‌نويسي علاقه‌مند به برنامه‌هايي هستند كه از ويژگي‌هاي «بازگشت اوليه» (Primitive Recursion) برخوردار باشد يعني انتها داشته باشد.

«ويلهلم آكرمن» (Wilhelm Ackermann)

كمي بعد و به‌طور مستقل «ويلهلم آكرمن» (Wilhelm Ackermann) تابع بازگشتي خود را منتشر كرد كه آن هم «اوليه» (Primitive) نبود. وي ابتدا تابع سه‌متغيره‌ي  را به‌صورت ذيل تعريف كرد:

(رابطه‌ي 9)

«ويلهلم آكرمن» (Wilhelm Ackermann) ثابت كرد تابع  يك «تابع بازگشتي» (Recursive) بوده و يك كامپيوتر با حافظه‌ي نامحدود مي‌تواند آن را محاسبه كند اما يك «تابع بازگشتي اوليه» (Primitive Recursive Function) (نظير: جمع، فاكتوريل و ...)‌ محسوب نمي‌شود.

«ديويد هيلبرت» (David Hilbert)

تابعي كه با نام «تابع آكرمن» (Ackermann's Function) مي‌شناسيم توسط «روزا پيتر» (Rozsa Peter) و «رافائل رابينسون» (Raphael Robinson) تعريف شده است.




 

مفهوم «ماشين تورينگ» (Turing Machine) از آن‌جا ناشي شد كه بايد رويه‌اي كاملاً تعريف‌شده‌‌اي را با تغيير در محتواي يك نوار كاغذي نامحدود اجرا كرد. نوار كاغذي به مربع‌هايي تقسيم شده كه هر مربع شامل مجموعه‌اي از نمادها است. لازم است يكي از مجموعه‌هاي محدود از وضعيت‌ها و رويه‌ها به‌صورت رابطه‌اي از مراحل بسيار پايه‌اي به‌صورتي نظير ذيل به‌ياد آورده شود:

- اگر در وضعيت 42 هستيد نماد مشاهده شده «صفر» است

- سپس اين نماد را با «1» عوض كنيد و يك نماد به‌سمت راست آن اضافه كرده مثلاً: وضعيت 17 را به‌عنوان وضعيت جديد فرض كنيد.

يك «ماشين تورينگ» (Turing Machine) از بخش‌هاي ذيل تشكيل شده است:

«تورينگ» (Turing) به‌عنوان «يادداشت دستورالعمل‌ها» براي نگهداري محاسبه‌ي «كامپيوتر» (يا فردي) تعريف مي‌شود كه در يك «حالت درهم و برهم» (Desultory Manner) كار مي‌كند.

به‌ياد داشته باشيد كه هر بخش از «ماشين تورينگ» [مجموعه‌هاي نمادها و وضعيت‌ها و عملياتي نظير: پرينت، پاك كردن، ضبط حركت و ...] محدود، مجزا و تميزدادني است. بالقوه مقدار نامحدودي از «نوار» (Tape) وجود دارد كه مقادير نامحدودي «فضاي ذخيره‌اي» (Storage Space) دراختيار مي‌گذارد.