Уикипедия

Halting проблем: Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
Редакция без резюме
Етикети: Визуален редактор етикет: премахнати източници/бележки
Редакция без резюме
Ред 18:
Тюринг доказва, че не съществува алгоритъм, който да дава правилен отговор за всяка всяка програма при произволни входни данни. Основната идея в доказателството на Тюринг е, че ако такъв алгоритъм бъде построен, той ще противоречи на себе си, следователно той ще е неправилен.
 
== ВажностЗначение и следствия ==
Задачата за спирането има историческо значение: тя е първата задача, за която е доказано, че е [[Нерешим проблем|нерешима]]. Доказателството на Тюринг е публикувано през май 1936 г., а доказателството на [[Алонсо Чърч]] за нерешимостта на съответната задача в [[ламбда смятане|ламбда-смятане]]то е от април 1936 г. Двамата работят независимо един от друг над този въпрос. По-късно са открити и множество други нерешими задачи. Типичен метод за доказване на нерешимостта на една или друга задача е свеждането ѝ до вече известна нерешима задача. <ref>Jeremy Booher, [http://math.stanford.edu/~jbooher/expos/computability_promys.pdf Computability: Turing Machines and the Halting Problem]</ref>
 
Така например, не е възможно да се определи за ''всяко'' твърдение относно [[Естествено число|естествени числа]] дали е вярно. Тоест не съществува сигурен метод за съставяне на доказателства в аритметиката. Това е така, понеже задачата за спирането може да се преформулира в еквивалентна задача за естествени числа.
Взето от „https://bg.wikipedia.org/wiki/Halting_проблем“.