כל מה שרצית לדעת על בעיית העצירה:
בעיית העצירה היא בעיה מרכזית בתחום החישוביות, שהוא אחד מעמודי התווך של מדעי המחשב התאורטיים.
בעיית העצירה מנוסחת כבעיית ההכרעה הבאה: בהינתן תוכנית מחשב וקלט, האם התוכנית תסיים את פעולתה בשלב כלשהו עבור קלט זה.
אלן טיורינג הוכיח ב-1936 כי בעיית העצירה על מכונות טיורינג (מודל תאורטי של מחשב בעל זיכרון אינסופי) אינה ניתנת לחישוב, כלומר אין אלגוריתם שמכריע עבור כל תוכנית מחשב וקלט האם התוכנית עוצרת כאשר מופעלת על (בקיצור: האם עוצרת על ).
חשוב להבחין שמבחינה לוגית, בהינתן תוכנית מסוימת וקלט עבורה, התשובה לשאלה "האם היא עוצרת?" מוגדרת היטב והינה חד משמעית.
עם זאת לא קיים אלגוריתם כללי שיודע להבחין האם תוכנית נתונה עוצרת או לא על קלט נתון, ומצליח לעשות זאת לכל תוכנית שתינתן לו ולכל קלט אפשרי עבור תוכנית זו.
עם זאת, כשמדובר במחשב בעל זיכרון סופי – כל תוכנית מחשב שרצה על מחשב זה תעצור בזמן שהוא לכל היותר 2 בחזקת מספר הביטים בזיכרון המחשב של צעדים, או תיכנס ללולאה אינסופית.
מספר צעדים זה הוא אקספוננציאלי, אבל סופי.
לכן ניתן לפתור את בעיית העצירה על מחשב בעל זיכרון סופי.
(לדוגמה: אם זיכרון המחשב הוא 8 סיביות (בית אחד), כל תוכנית מחשב תעצור לכל היותר אחרי 256 צעדים, או תיכנס ללולאה אינסופית.
אם זיכרון המחשב הוא 1 KB (8192 ביטים או 1024 בתים), כל תוכנית מחשב תעצור לכל היותר אחרי 28192 צעדים, או תיכנס ללולאה אינסופית).
בזיכרון המחשב יש לכלול גם את זיכרון המעבד, כגון אוגרים וכו', וכן את תוכנית המחשב עצמה.
כמו כן לא ניתן עקרונית לממש זיכרון אינסופי, ולו בגלל הצורך בחומר לשם זיכרון וכמות החומר ביקום סופית.