Halting проблем
Проблемът за спиране е проблем в областта на информатиката. Проблемът се състои в това да се разгледа компютърна програма и да се установи дали тя ще работи вечно или не. Казваме, че една програма "решава проблема на спирането", ако може да погледне всяка друга програма и да каже дали тази друга програма ще работи вечно, или не.
Например, програма като тази:
while True: продължете;ще зацикли завинаги, но програмата
while False: продължете;спира много бързо.
Има ли програма, която решава проблема със спирането? Оказва се, че няма. Доказваме този факт, като показваме, че ако има програма, която решава проблема с прекъсването, тогава се случва нещо невъзможно. Затова за момента ще се държим така, сякаш наистина има програма, която решава проблема със спирането. Тук P е функция, която ще оценява функцията F (извикана с аргумент I) и ще връща true, ако тя работи вечно, и false в противен случай.
def P(F, I): if F(I) работи вечно: return True; else: return False;P може да разгледа всяка програма и да разбере дали ще работи вечно или не. Използваме P, за да създадем нова програма, която ще наречем Q. Това, което Q прави, е да погледне друга програма и да отговори на следния въпрос: "Ако стартираме тази програма и я накараме да погледне копие на себе си, ще работи ли вечно?". Можем да направим Q, защото имаме P. Всичко, което трябва да направим, е да кажем на Q да създаде нова програма, която е старата програма, гледаща себе си, и след това да използваме P, за да разберем дали новата програма ще работи вечно или не.
def Q(F): return P(F, F);Сега създаваме друга програма R. R разглежда друга програма и пита Q за отговор на тази програма. Ако Q отговори "да, ако стартираме тази програма и я накараме да гледа копие на себе си, тя ще работи вечно", тогава R спира. Ако Q отговори "не, ако стартираме тази програма и я накараме да гледа копие на себе си, тя няма да работи вечно", тогава R влиза в безкраен цикъл и работи вечно.
def R(F): if Q(F): return; //terminate else: while True: continue; //loop foreverСега ще разгледаме какво ще се случи, ако накараме R да погледне копие на себе си. Могат да се случат две неща: или ще спре, или ще работи вечно.
Ако стартирането на R и заставянето му да гледа копие на себе си не работи вечно, тогава Q отговаря "да, ако стартираме тази програма и я накараме да гледа копие на себе си, тя ще работи вечно". Но Q каза това, когато гледаше самия R. Така че това, което Q всъщност е казал, е: "да, ако стартираме R и го накараме да гледа копие на себе си, той ще работи вечно". И така: Ако R, работещо върху копие на самото себе си, не работи вечно, тогава то работи вечно. Това е невъзможно.
Ако стартирането на R и заставянето му да гледа копие на самия себе си продължава вечно, тогава Q отговаря "не, ако стартираме тази програма и я накараме да гледа копие на самата себе си, тя няма да продължи вечно". Но Q каза това, когато гледаше самия R. Така че това, което Q всъщност е казал, е: "не, ако стартираме R и го накараме да гледа копие на себе си, той няма да работи вечно". И така: Ако R, работещо върху копие на самото себе си, работи вечно, тогава то не работи вечно. Това също е невъзможно.
Без значение какво се случва, получаваме невъзможна ситуация. Направили сме нещо нередно и трябва да разберем какво е то. Повечето от нещата, които сме направили, не са били погрешни. Не можем да кажем, че "да накараш една програма да погледне копие на самата себе си е погрешно" или "да погледнеш какво е казала друга програма и след това да влезеш в цикъл, ако тя каже едно нещо, и да спреш, ако каже друго нещо", е погрешно. Няма смисъл да казваме, че не ни е позволено да правим тези неща. Единственото нещо, което направихме и което изглежда, че би могло да е погрешно, е, че се престорихме, че програма като P изобщо съществува. И тъй като това е единственото нещо, което би могло да е погрешно, а нещо трябва да е погрешно, то е именно това. Това е доказателството, че програма като P не съществува. Не съществува програма, която да решава задачата за спиране.
Това доказателство е открито от Алън Тюринг през 1936 г.
Въпроси и отговори
В: Какво представлява проблемът за спирането?
О: Проблемът за спиране е проблем в информатиката, който разглежда компютърна програма и определя дали програмата ще работи вечно или не.
В: Как да разберем дали дадена програма решава проблема на спирането?
О: Казваме, че една програма "решава проблема на спирането", ако може да погледне всяка друга програма и да каже дали тази друга програма ще работи вечно, или не.
В: Има ли начин да се докаже, че не съществува такава програма?
О: Да, като покажем, че ако съществуваше такава програма, щеше да се случи нещо невъзможно. Това доказателство е намерено от Алън Тюринг през 1936 г.
В: Какво прави P?
О: P е функция, която оценява друга функция F (извикана с аргумент I) и връща true, ако тя работи вечно, и false в противен случай.
В: Какво прави Q?
О: Q разглежда друга програма и след това отговаря на въпроса дали стартирането на същата програма върху себе си ще доведе до безкраен цикъл. Тя прави това, като използва P, за да направи оценка на дадената функция F.
В: Какво прави R?
Отговор: R разглежда друга програма и пита Q за отговора й върху тази конкретна програма. Ако Q отговори "да, ако пуснем тази програма и я накараме да гледа копие на себе си, тя ще работи вечно", тогава R спира; ако обаче Q отговори "не, ако пуснем тази програма и я накараме да гледа копие на себе си, тя няма да работи вечно", тогава R влиза в безкраен цикъл и работи вечно.
В: Какво се случва, когато накарате R да погледне себе си?
О: Могат да се случат две неща - или R да спре, или да работи вечно - но и двата резултата са невъзможни според това, което е доказано за несъществуващи програми като P, така че нещо трябва да се е объркало някъде по пътя, водещ до това да накарате R да погледне себе си.
