תורת החישוביות/מבוא

תורת החישוביות עוסקת ביכולות החישוב ובמודלי החישוב השונים. בפרט, התורה מתמקדת בשאלות של מה יכול המחשב לחשב ומה לא יכול המחשב לחשב.

מוטיבציה

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

Infinite():
	...
	while True:
		# Some commands with no break sentence
	...

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

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

נניח על דרך השלילה שהיינו כותבים פונקציה שפותרת את הבעיה הנ״ל,

Halts(P, s)

Halts מקבלת תיאור של פונקציה $P$ ומחרוזת $s$, ומחזירה האם הפונקציה עוצרת בהנתן המחרוזת. (נגדיר שאם $P$ איננה מתארת פונקציה בשפה, אז התשובה תהיה חיובית.) למשל, עבור הדוגמא לעיל Halts(Infinite,Null)‎ תענה שהפונקציה Infinite (על המחרוזת הריקה, כלומר, ללא קלט), נכנסת ללולאה אינסופית ואינה מסתיימת. נניח שהמחרוזת P מתארת את הפונקציה בשפת תכנות מסויימת, אפשר לחשוב על P בתור קובץ המקור שמתאר את הפונקציה (למשל, התוכן של P.c או P.perl, וכו')

נשים לב שלפונקציה יש גוף המורכב מביטויים פרימיטיביים של השפה (לולאות, תנאים, וכו'):

Halts(P, s)
	if ...
	...
	while ...
	...

לפי ההנחה, פונקציה זו עובדת כיאות: היא מחזירה את התשובה הנכונה, ואיננה נכנסת ללולאות אינסופיות בעצמה, לדוגמה.

כעת נבנה את הפונקציה הבאה, שמטרתה תהיה לבלבל את הפונקציה המכריעה:

Confounds(s)
	if Halts(s, s):  
		while True:
			# Some commands with no break sentence

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

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

Confounds(s)
	h = # Code from Halts():
		if ...
		...
		while ...
		...
	if h:
		while True:
			# Some commands with no break sentence

כעת יש לנו קוד הפונקציה המבלבלת, מוגדר כולו בעזרת פרימיטיבים של השפה בלבד. נקרא למחרוזת המתארת קוד זה $s'$.

מה תהיה התשובה המתקבלת מהקריאה:

Halts(s', s')

1. אם התשובה תהיה חיובית, סימן שהפונקציה המבלבלת עוצרת. אך אם נתבונן בגוף הפונקציה המבלבלת, נראה שאם התשובה חיובית, היא נכנסת ללולאה אינסופית.
2. אם התשובה תהיה שלילית, סימן שהפונקציה המבלבלת איננה עוצרת. אך אם נתבונן בגוף הפונקציה המבלבלת, נראה שאם התשובה שלילית, היא אכן מסתיימת.

מבנה הספר

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

ידע קודם נדרש

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

1. ידע, אפילו בסיסי מאד, בשפת תכנות כלשהי (נניח, שפת C או פייתון)
2. הכרה מועטה של אוטומטים ושפות פורמליות
3. מעט ידע באלגוריתמים

-

מבוא

הפרק הבא: מכונת טיורינג