אנטליה הוקמה בשנת 159 לפנה"ס על ידי אטלוס השלישי מלך פרגמון שקרא לה "אטאליה" על שמו. אטלוס השלישי הקים את העיר בהסכמת הרומאים ובמטרה להרחיב את שלטונו לעבר פמפיליה. במהלך המחצית הראשונה של המאה ה-1 לפנה"ס הייתה העיר נתונה לשליטתם של שודדי הים של פמפיליה, ובשנת 67 לפנה"ס הפך אותה גנאיוס פומפיוס מגנוס לאחד ממעוזיו במלחמתו בשודדים. העיר שגשגה בתקופה הרומית וכבר במאה ה-1 ביקר בה השליח פאולוס הקדוש, ביקור שתואר במעשי השליחים בברית החדשה:
אנטליה הייתה למרכז נוצרי במאה ה-2 והקיסר אדריאנוס ביקר בה בשנת 130 ובנה בה את שער אדריאנוס שלו שלושה פתחים, ומכאן שמו בטורקית "Üçkapılar" - "שלושה שערים". העיר המשיכה לשגשג גם בתקופת הביזנטית אף כי הייתה נתונה להתקפות הערבים, דבר שחייב את הקיסר ליאו השישי לבצרה ולהקים חומה סביבה. בראשית המאה ה-12 הוקפה העיר בנסיכויות בייליקיות והייתה נגישה רק מהים, אך ב-1118 חידש יוחנן השני את הגישה היבשתית אל העיר. הוונציאנים עשו שימוש בעיר לקשריהם המסחריים במזרח הים התיכון, והיא נכבשה לראשונה בידי הסלג'וקים ב-1207. ב-1426 נכבשה העיר בידי הסולטאן העות'מאני מורט השני. במאה ה-19 ועם שקיעתה של האימפריה ואובדן שטחיה, החלה הגירה של טורקים מהבלקן ומהקווקז אל העיר. ב-1911 מנתה אוכלוסייתה של העיר כ-25,000 איש, רובם טורקים, אך גם יוונים, ארמנים ויהודים. ב-29 באפריל 1919 נכבשה העיר בידי האיטלקים אשר נסוגו ממנה ב-1 ביוני 1921, והעיר הייתה לחלק מטורקיה עם הקמתה ב-1923. בשנות השבעים של המאה ה-20 החלה תנופת הפיתוח של ענף התיירות בריביירה הטורקית, והעיר גדלה בקצב מהיר והפכה לעיר החשובה באזור. הטרמינל הראשון בנמל התעופה נחנך ב-1 באפריל 1998 וכבר ב-2002 הגיע נפח תנועת הנוסעים בעיר ל-10 מיליון בשנה. טרמינל שני הוקם ונחנך בשנת 2006 ובשנה זו חלפו 14,642,043 נוסעים דרך השדה.
גאוגרפיה ואקלים.
העיר ממוקמת על מצוק בגובה של 35 מטר במרכזו של מישור פמפיליה ולאורכו של מפרץ אנטליה. המישור מוקף בהרי הטאורוס מכל עבריו. ההרים מגינים על המישור מפני השפעותיו של האקלים היבשתי השורר ברמת אנטוליה, והאקלים באנטליה הוא ים תיכוני אופייני. בעיר כ-60 ימים גשומים בשנה והטמפרטורה הממוצעת בחודש ינואר היא 10.6 מ"צ ובחודש יולי 28.3 מ"צ. טמפרטורת מי הים נעה בין 17 מ"צ ל-28 מ"צ.
כלכלה ותחבורה.
עיקר הכנסותיה של העיר מענף התיירות, אך גם מחקלאות, מסחר ובמידה פחותה מכך גם מתעשייה. החקלאות כוללת גידול הדרים, ירקות, כותנה, פרחים ואפילו בננות. ההתפתחות המהירה בענף התיירות החל בשנות השבעים של המאה ה-20 הביאה להגירת תושבים אל העיר בהיקף ניכר, ויצרה תנופת בנייה של בתי מלון ואתרי נופש, ופרויקטים רחבי היקף כמו הקמת שדה התעופה ותחנת האוטובוסים המרכזית החדשה בצפונה של העיר. בעיר פועלת "אוניברסיטת הים התיכון" (Akdeniz Üniversitesi) שהוקמה בשנת 1982.
מנמל התעופה הבינלאומי של אנטליה יוצאות טיסות סדירות לרחבי טורקיה וטיסות סדירות ושכר לאירופה ולישראל. העיר מקושרת בקווי אוטובוס לכל חלקי המדינה, ובקו מעבורת לוונציה. התחבורה הפנימית נסמכת על שירותי אוטובוס, דולמוש ועל קו חשמלית בן 8 ק"מ לאורך החוף.
הבונה העסוק
הבונה העסוק (Busy beaver) הוא שמה של בעיה לא כריעה במדעי המחשב, העוסקת בשאלה: "כמה עבודה ניתן לעשות באמצעות מכונת טיורינג עם מספר נתון של מצבים אפשריים, שפועלת על סרט ריק ועוצרת?".
שתי השאלות העיקריות בתחום זה הן: מהו המספר המרבי של צעדים שמכונת טיורינג עם formula_1 מצבים יכולה לבצע לפני שהיא עוצרת? (מספר זה מסומן ב-formula_2), ומהי הכמות המרבית של סימנים שהיא יכולה להדפיס לפני שהיא עוצרת? (מספר זה מסומן ב-formula_3). שתי הפונקציות האלו, formula_2 ו-formula_3, אינן ניתנות לחישוב רקורסיבי, כי ניתן להכריע באמצעותן את בעיית העצירה. יתרה מזו, הן גדלות אסימפטוטית מהר יותר מכל פונקציה רקורסיבית.
הקדמה.
מכונת טיורינג.
אחת הדרכים לתאר באופן ריגורוזי פעולת אלגוריתם היא על ידי מכונת טיורינג. קיימות מספר הגדרות שקולות למושג "מכונת טיורינג". אחת הדרכים הפשוטות לראות את מכונת טיורינג היא על ידי המחשתה כמעין מחשב מכני בסיסי, שמורכב מארבעה חלקים:
טבלת ההוראות היא בעצם התוכנה של המכונה. בטבלה זו כתוב למכונה מה לעשות אם היא נמצאת במצב מסוים, בהתאם לתוכן הסרט שהיא מסוגלת לראות באמצעות הראש. לדוגמה, עבור המכונה שבה יש שני מצבים, A ו-B, הטבלה הבאה היא אפשרות לטבלת הוראות עבור המכונה:
בתחילת החישוב, המכונה נמצאת בתחילת הסרט, ולכן יכולה לנוע רק ימינה. נפעיל את המכונה המוצגת על ידי הטבלה על סרט שעליו כתובים רק אפסים, כאשר המצב ההתחלתי של המכונה הוא A:
פלט המכונה הוא כל התאים שמשמאל לראש הקורא – במקרה זה הראש נמצא בתא השמאלי ביותר, ולכן הפלט יהיה המילה הריקה.
מראש, נראה שהאפשרויות של מכונה כזו יהיו מאוד מוגבלות, כיוון שההוראות האפשריות בטבלה הן מאוד מעטות, אך ניתן להוכיח כי המכונה שקולה בכוחה למודלים חישוביים נוספים רבים, ומסוגלת לבצע כל מה שמחשב מסוגל לבצע. על פי תזת צ'רץ'-טיורינג, כל אלגוריתם סביר ניתן לחישוב בידי מכונה מתאימה. נשים לב, שמכונת טיורינג יכולה גם לא לעצור. לדוגמה, במכונה עם מצב אחד, A, שיש לה הוראה עבור הקלט 0: "כתוב 1, עבור למצב A, לך שמאלה", תמלא סרט שמכיל רק אפסים באחדות ולעולם לא תעצור.
למעשה, השאלה האם מכונה מסוימת עוצרת או לא (בעיית העצירה), לא ניתנת לפתרון באופן כללי על ידי מכונת טיורינג, ובהכרח קיימות מכונות, שלגביהן אין לנו שום דרך אלגוריתמית לדעת אם הן לא עוצרות.
בעיה שניתנת לפתרון בעזרת מכונת טיורינג נקראת "רקורסיבית" או "ניתנת לחישוב".
הגדרת פונקציות הבונה העסוק.
לכל מספר טבעי formula_1, יש רק מספר סופי של מכונות טיורינג בעלות formula_1 מצבים (לפי התיאור לעיל, formula_8). מכיוון שכך, אפשר לשאול: "כמה צעדים נדרשים מן המכונה העוצרת האחרונה, לפני שהיא עוצרת, ובפלט של איזו מכונה יש הכי הרבה סימני 1?".
בהתאם לכך, מגדירים שתי פונקציות:
פונקציות אלו אינן רקורסיביות, כי כדי לחשב אותן, יש לדעת איזו מכונה נעצרת ואיזו מכונה לא נעצרת – וזו בעיית העצירה. לכן, לא קיימת דרך לחשב אותן באופן כללי, אלא רק במקרים ספציפיים. מסיבה דומה, לא ניתן גם לחסום מלמעלה באופן כללי את התקדמות הפונקציות על ידי פונקציה רקורסיבית, אלא אפשר רק לחשב חסמים תחתונים. עם זאת, ידועים ערכי הפונקציה עבור ערכים קטנים של formula_1:
הוכחה ישירה לאי-הרקורסיביות של בעיית הבונה העסוק.
הרעיון הבסיסי בהוכחה הוא להניח בשלילה שהפונקציות formula_23 ניתנות לחישוב על ידי מכונת טיורינג, ועל ידי יצירת מכונת טיורינג חדשה מאותה מכונה – לקבל סתירה למקסימליות של ערכי הפונקציות; כלומר, המכונה החדשה תבצע יותר צעדים מפונקציית הצעדים או תכתוב יותר אחדות מפונקציית ספירת האחדות.
הוכחה שפונקציית ספירת הצעדים לא רקורסיבית.
נניח בשלילה ש-formula_24 רקורסיבית; כלומר, קיימת מכונת טיורינג, "EvalS", שבהינתן סרט עם formula_1 אחדות עליו מחזירה סרט עם formula_9 אחדות.
הרעיון: נבנה מכונה בעלת formula_9 מצבים פנימיים שמחשבת את formula_28, ולאחר מכן, בהתאם לתוצאת החישוב, מבצעת יותר מ-formula_28 צעדים. לא ניתן לבנות מכונה זו באמצעות "EvalS" לבדה, שכן "EvalS" מקבלת כקלט סדרה של formula_1 אחדות, ועל מכונה אחרת (שגם לה יש מספר כלשהו של מצבים פנימיים שבהם יש להתחשב) להדפיס את אותם האחדות.
על כן, נבנה את המכונה הגדולה שלנו ממספר "מכונות עזר". פרט ל-"EvalS", נשתמש במכונות הבאות:
נסתכל על שרשור המכונות יחד: Double | EvalS | Clean (כלומר, "Double" פועלת ראשונה, ומיד עם סיום פעולתה מתחילה ריצת "EvalS", ומיד עם סיום פעולתה מתחילה ריצת "Clean"). השרשור הוא בעצמו מכונת טיורינג, ונסמן את מספר המצבים השונים שבה בתור formula_35 (זהו סכום מספרי המצבים של Double, EvalS, Clean).
כמו כן, ניתן לבנות מכונה בת formula_35 מצבים, שכותבת פשוט formula_35 אחדות רצופות על הסרט (לדוגמה, בכל שלב המכונה תכתוב 1, תעבור למצב הבא בסדרה ותלך ימינה, ואחרי השלב ה-formula_35 תעצור). נסתכל על המכונה בת formula_39 המצבים, שנוצרת מהשרשור של המכונה שיוצרת formula_35 אחדות עם המכונה "Double|EvalS|Clean", ונסמן את המכונה החדשה ב-formula_41. זוהי המכונה שגורמת לסתירה המבוקשת: מצד אחד, יש בה formula_39 מצבים (formula_39 הוא ה-formula_44 שהזכרנו קודם), ולכן היא יכולה לבצע לכל היותר formula_45 צעדים. מצד שני, בצורת הבנייה שלה הבטחנו שהיא תבצע יותר צעדים מזה:
הוכחה שפונקציית ספירת האחדות לא רקורסיבית.
הוכחה זו מאוד דומה להוכחה הקודמת, כאשר במקום המכונה "Clean" ניקח את המכונה "Increment", שמוסיפה אחד נוסף באפס הראשון על הסרט מימינה.