אם יוסר זוג מספר 2, לא ניתן יהיה למצוא התאמה. זאת מכיוון שאם סדרת ההתאמות מכילה את זוג מספר 1, אז formula_9 יוסף את האות ל' למילה הנבנית, וזו לא ניתנת ליצירה מה-formula_2 (לאחר שהורדנו את זוג מספר 2), אם היא מכילה את 3 אז formula_11 יוסיף את האות י' למילה הנבנית, וזו לא קיימת עבור ה-formula_3; מכאן עולה שהיא חייבת להיות מורכבת מ-4 בלבד, אבל אורך formula_13 שונה מאורך formula_14 ולכן שתי המילים שהם בונים בו זמנית יהיו בעלות אורך שונה, ובפרט לא אותה מילה.
בדוגמה זו ניתן להיווכח בקיום/אי קיום התאמה על ידי שיקולים פשוטים יחסית; בדוגמאות מורכבות יותר השיקולים הללו לא יעבדו יותר, ומכאן המוטיבציה לניסיון למציאת אלגוריתם כללי לפתרון הבעיה - אלגוריתם שכאמור, אינו יכול להתקיים.
הוכחת אי כריעות.
ההוכחה המקובלת לאי כריעות בעיית ההתאמה מבוססת על אי כריעותה של בעיית העצירה. הרעיון הבסיסי של ההוכחה הוא להראות כי ניתן לבצע מעין סימולציה של ריצת מכונת טיורינג באמצעות מופע של בעיית ההתאמה, כך שהמכונה מסיימת את ריצתה אם ורק אם קיימת התאמה במופע זה. אם בעיית ההתאמה הייתה ניתנת לפתרון, אז בהינתן מכונת טיורינג וקלט ניתן היה לתרגם אותן למופע המתאים של בעיית ההתאמה, לפתור את המופע הזה (כלומר, לגלות האם קיימת בו התאמה או לא) ולהכריע בשאלת עצירתה של מכונת הטיורינג המקורית. מכיוון שבעיית העצירה אינה כריעה, נובע מכך שגם בעיית ההתאמה חייבת להיות אי כריעה.
ההמרה מבוצעת בשני שלבים. ראשית, במקום לעסוק ישירות בבעיית ההתאמה של פוסט עוסקים בווריאנט שלה, הזהה לה כמעט לחלוטין פרט לכך שזוג המחרוזות הראשונות שייבחר נתון מראש, ולא ניתן לבחירה מתוך כלל המחרוזות. הבדל זה מאפשר ליצור מחרוזת מיוחדת שמתארת את "המצב ההתחלתי" של מכונת טיורינג, ובאמצעותה לבצע סימולציה בו זמנית של ריצת המכונה הן באיברים השמאליים בכל זוג שמתווסף למילה אותה מרכיבים, והן באיברים הימניים, כשהריצה שבאגף שמאל תמיד מקדימה בצעד אחד את הריצה שבאגף ימין, כך שהדרך היחידה שבה תושג התאמה (כלומר, המילה שנבנתה על ידי אגף שמאל תשתווה למילה שנבנתה על ידי אגף ימין) היא אם ריצת המכונה תסתיים ובכך אגף ימין יוכל "להשיג" את אגף שמאל.
שלב א' - מעבר לבעיית התאמה עם מחרוזת ראשונה נתונה.
הווריאנט על בעיית פוסט שבו משתמשים בהוכחת אי הכריעות הוא כדלהלן: נתון אוסף של זוגות של מחרוזות, formula_1, ובנוסף נתון עוד זוג אחד מיוחד, formula_16. השאלה היא האם קיימת סדרת אינדקסים formula_4, כולם בתחום formula_5 כך ש-formula_19.
בחלק הבא של ההוכחה מוכיחים כי בעיה זו אינה כריעה. מכאן שכדי להראות כי בעיית פוסט המקורית היא בלתי כריעה, יש להראות כי ניתן "לתרגם" כל מופע של הבעיה החדשה למופע של הבעיה המקורית בצורה כזו שהמופע של הבעיה החדשה פתיר אם ורק אם המופע של הבעיה הישנה פתיר (דבר שכזה מכונה רדוקציה חישובית).
אם כן, נניח כי נתון אוסף זוגות formula_1 וכמו כן נתון הזוג המיוחד formula_16. הרעיון הבסיסי בהמרת בעיה זו לבעיית פוסט המקורית היא לקחת סימן שאינו באלפבית הנוכחי של המחרוזות (למשל, formula_22) ו"להשתיל" אותו בתוך כל הזוגות formula_23 באופן כזה שבאיבר הימני של כל זוג הכוכביות מופיעות לפני כל אות, ואילו באיבר השמאלי הכוכביות מופיעות אחרי כל אות. מכאן שלא ניתן להתחיל את בניית המילה המשותפת עם אף אחד מהזוגות formula_23 ש"טופלו" באופן שכזה, כי האיבר הימני בזוג מתחיל בכוכבית, ואילו השמאלי לא. כדי שעדיין יהיה ניתן ליצור מילה משותפת, יש לתקן את הזוג formula_16 בהתאם, וכמו כן להוסיף זוג אחד נוסף, ש"יסיים" את בניית המחרוזת וישווה את מספר הכוכביות שבכל אחד מהעותקים.
כדי לתאר בצורה פורמלית את הבנייה נוח להגדיר שתי פונקציות על מילים, formula_26, שעבור המילה formula_27 "משתילות" כוכביות באופן הבא:
formula_28
formula_29
כעת, אם formula_30 הוא אוסף הכללים של הבעיה שאותה מתרגמים, אז אוסף הכללים החדש יהיה formula_31
כאשר גם formula_32 הוא סימן שאינו שייך לאלפבית של הבעיה המקורית.
שלב ב' - סימולציה של מכונת טיורינג באמצעות בעיית ההתאמה.
חלקה השני של ההוכחה מסתמך על כך שהמודל החישובי של מכונת טיורינג הוא פשוט מאוד לתיאור, ועל כן ניתן לבצע מעין "סימולציה" שלו באמצעות בעיית ההתאמה. הרעיון הבסיסי הוא לתאר חישוב של מכונת טיורינג בתור סדרה של תצורות (קונפיגורציות) שכל אחת מהן מתארת את מצבו הנוכחי של סרט הקלט, מיקום הראש הקורא והמצב הפנימי הנוכחי של המכונה. קונפיגורציה שכזו נוח לתאר באמצעות סדרת תווים מהאלפבית של המכונה, המציינת את תוכן סרט הקלט הנוכחי (עם סימן מיוחד המצביע על הנקודה שבה מסתיים החלק של הסרט שבו נעשה שימוש עד כה), אשר בתוכה "מושתל" סימן המתאים למצב הפנימי הנוכחי של המכונה, והוא נמצא משמאל לתא בסרט שהמכונה קוראת. כך למשל הסדרה הבאה:
formula_33
מייצגת את הקונפיגורציה שבה החלק של הסרט שבשימוש מכיל את המחרוזת "01001010", המכונה נמצאת במצב הפנימי מס' 3, והראש הקורא מצביע על ה-"0" הלפני אחרון.
ניתן כעת לחשוב על חישוב שלם של המכונה כסדרה עוקבת של קונפיגורציות שמופרדות על ידי סימן מיוחד (למשל, כוכבית) כך שכל אחת מהן מתקבלת מקודמתה באמצעות פונקציית המעברים של מכונת הטיורינג. דוגמה לסדרה שכזו:
formula_34
מחרוזת זו מייצגת את הריצה שבה המכונה התחילה במצב 0 ועם שני אפסים כתובים על הסרט, שינתה את הראשון מביניהם ל-1 עברה למצב 1 ונעה עם הראש הקורא ימינה, שינתה את השני ל-1, עברה למצב 2 ונעה שוב ימינה, כתבה 0 על הסרט, עברה למצב הפנימי 3 ונשארה באותו מקום על הסרט, ולבסוף נעה צעד אחד שמאלה ועברה למצב הפנימי 0.
הסימולציה של מכונת הטיורינג מתבצעת כך: ראשית, הזוג ההתחלתי של מילים בבעיית ההתאמה יהיה הזוג formula_35, כאשר formula_36 היא המילה שעבורה נבדקת עצירת המכונה. כלומר - האיבר השמאלי בזוג מתאר את הקונפיגורציה ההתחלתית של המכונה, ואילו האיבר הימני הוא "ריק". מכאן שכדי שהזוגות ירכיבו את אותה המילה, בחירת האיברים הבאים צריכה להיות כזו ש"תעתיק" את הקונפיגורציה שקיימת באגף שמאל לאגף ימין. הרעיון הוא שתוך כדי ביצוע ההעתקה הזו לאגף ימין, תיווצר (על ידי האיברים השמאליים בזוגות שיתווספו) קונפיגורציה חדשה באגף שמאל - כזו שנובעת מיידית מהקונפיגורציה הקודמת. כך למשל לכל תו formula_37, הזוג formula_38 מבטיח העתקה של תוכן הסרט מהקונפיגורציה הקודמת לנוכחית, וזוגות כמו formula_39 (שמתאים למעבר formula_40) מבטיחים את שינוי הקונפיגורציה החדשה על פי פעולה אפשרית עבור מכונת הטיורינג המסמלצת.
כל עוד המכונה לא הגיע למצב מקבל, אגף ימין לא יכול להדביק את אגף שמאל; על כן, מוסיפים זוגות שמאפשרים, בהינתן שאגף שמאל מייצג קונפיגורציה שהגיעה למצב מקבל, "למחוק" חלקים מהקונפיגורציה בכל העתקה שלה, עד שלבסוף אגף ימין מדביק את אגף שמאל. בצורה זו מובטח שקיים פתרון לבעיית ההתאמה אם ורק אם המכונה המסומלצת מגיעה למצב מקבל.
עמוס הדר
עמוס הדר (7 בספטמבר 1923 – 13 בינואר 2014) היה חבר הכנסת ומזכ"ל תנועת המושבים.
הדר נולד בנהלל בשם עמוס הורביץ, אחיו של יגאל הורביץ ובן דודם של משה, זוהר ואביבה דיין (גפן). הדר היה בוגר תנועת הנוער העובד והלומד, התגייס להגנה, שירת בבריגדה בתקופת מלחמת העולם השנייה. במלחמת העצמאות לחם בקרבות עמק הירדן ובקרבות משמר העמק. הדר שימש מזכיר מושב נהלל ומרכז ועדת המשק של תנועת המושבים. בשנת 1954 החל לפעול בנגב בהתנדבות מטעם תנועת בני המושבים. באותה שנה הצטרף הדר לרפ"י, ממנה התפלג ב-1968 והתאחד אל מפלגת העבודה. בשנת 1974 הוא החל לכהן כחבר הכנסת במקומו של עוזי פיינרמן. כהונתו של הדר בכנסת נמשכה לאורך הכנסות השמינית והתשיעית. בתום כהונתו הוא כיהן כמזכ"ל תנועת המושבים (1982–1985).
ילדותו.
עמוס הדר נולד בשם עמוס הורביץ בשנת 1923 במושב נהלל. היה הרביעי מבין חמישה ילדיהם של יונה הורביץ ובלה דיין. כילד עבד במשק המשפחתי ולמד בבית הספר בנהלל.
שירותו בהגנה.
כנער צעיר התגייס לארגון ההגנה. נשלח לקורס מ"כים בביתן אהרון ושימש כמדריך בהגנה, אך רצה להתנדב לצבא הבריטי. לאחר שנאסר עליו להתגייס, הפך לנוטר.
השירות בבריגדה.
ב-1944 כשהוכרז על הקמת הבריגדה היהודית, מתוך כוונה שתיטול חלק אמיתי בחזית מול הגרמנים, החליט להתגייס, וניתנה לו הסכמה לכך. ב-1.11.1944 התגייס ביחד עם עוד שישה חברי נהלל לצבא הבריטי.
הוא התחיל את שירותו בהכשרה בסרפנד (צריפין), ולאחר מכן עברו למצרים לאימוני נשק ושדה.
ב-5 במאי 1945, נחתו באיטליה, חנו בטרוויזיו והצטרפו לבריגדה. התחילו לפגוש בפליטים, והתארגנו יחידות ואנשים שטיפלו בפליטים. הוא המשיך להעלות בסולם הדרגות והיה לקורפורל.
במאי 1946 הצבא הבריטי עמד לשחרר את הבריגדה. מכיוון שהבריגדה עסקה רבות בפעילות עם הפליטים, כולל הבריחה, הגיעו למסקנה שצריך להשאיר חיילים מהבריגדה באירופה למען שלוש מטרות:
1.     טיפול קהילתי טכני במחנות הפליטים
2.     הבריחה – הברחת האנשים לארץ ישראל באוניות המעפילים
3.     הכנת עתודה לצבא בארץ
הדר יועד לעסוק בהדרכה בנשק. המדריכים עסקו גם בחינוך הציוני וגם בהדרכה צבאית. הוא ישב בפולונה, איטליה, למרגלות האלפים, ואימן את הפליטים. שם נתקל לראשונה בארגון הג'וינט (JDC) שכלכל את המחנות, ובכללם את המדריכים.
במחנה פולונה הכיר את בתיה ברקוביץ, בת טרנסילבניה, רומניה, ניצולת אושוויץ, שהייתה חיילת במחנה הפליטים ונשארה כאחראית המטבח במחנה, והם הפכו לזוג.
החזרה לארץ ישראל.