ראשי > מכונת טיורינג > מכונת טיורינג > עמוד 8 מתוך 9

   

 

אבל שימו לב : התוספת הזו מחייבת שכל פרטיה של השיטה יהיו ידועים ומודעים, בעוד שטיעון "המצב המנטלי" חל גם על אדם שיכול לבצע תהליך באופן אמין מבלי להיות מסוגל לתאר אותו בצורה מפורשת.

המספרים הניתנים לחישוב מוגדרים, אם כן, כאותם שברים עשרוניים אינסופיים שניתנים להדפסה על ידי מכונת טיורינג המתחילה לעבוד עם סרט חלק. טיורינג התווה בקווים כלליים הוכחה לכך ש- πהוא מספר הניתן לחישוב, כמו מספרים ממשיים אחרים המוגדרים על ידי השיטות הרגילות המתמטיקה, הנעזרות במשוואות או בניתוחי גבולות. אולם עכשיו, באמצעות ההגדרה החדשה, קל לראות שקיימים מספרים ש אינם ניתנים לחישוב. ההוכחה מושתתת על העיקרון שטבלת ההתנהגות של כל מכונת טיורינג היא טבלה סופית. ניתן, אם כן, לסדר את כל טבלאות ההתנהגות האפשריות לפי סדר אלפביתי, ואפשרות זו מוכיחה שהמספרים הניתנים לחישוב ניתנים למנייה (כלומר, גם אם הסדרה של ספרותיהם היא אינסופית, היא ניתנת למנייה על ידי הסדרה האינסופית של טבלאות ההתנהגות הסופיות המאפשרות לחשב אותם). מאחר שסדרת המספרים הממשיים אינה ניתנת למנייה, יוצא שכמעט כולם אינם ניתנים לחישוב. אפשר לחדד את הדברים על ידי ההצגה של מקרה פרטי של מספר שאינו ניתן לחישוב. אולם לפני שנתחיל בבנייה, חשוב להדגיש את העניין הבא : טבלת ההתנהגות יכולה להיות טבלה שנתקעת בלולאה ואינה מייצרת לעולם יותר ממספר סופי של ספרות.

ובכן, נציב שוב את כל מכונות טיורינג בסדר האלפביתי של טבלאות ההתנהגות שלהן, אך נביא בחשבון את האפשרות שהוזכרה זה עתה. נפסול את הטבלאות שאינן מייצרות סדרות אינסופיות של ספרות, ונשאיר רק מכונות טיורינג שמייצרות מחרוזות של ספרות – המספרים הניתנים לחישוב. נניח שהמספרים נכתבים בשיטה הבינרית, כך שהספרות הן 0 או 1. נגדיר עכשיו מספר חדש כך שספרתו ה- n שונה מהספרה ה- n שנוצרה על ידי המכונה ה- n בסדרת המכונות. המספר החדש הזה שונה לפחות במקום אחד מכל מספר הניתן לחישוב; לכן, איננו יכול להיות מספר הניתן לחישוב.

 

                                                              

©  כל הזכויות שמורות למערכת איתן