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