Пытанне аб тым, ці вырашальная праблема прыпынку машыны Цьюрынга, з'яўляецца фундаментальным пытаннем у галіне тэарэтычнай інфарматыкі, асабліва ў галіне тэорыі вылічальнай складанасці і вырашальнасці. Праблема прыпынку - гэта праблема прыняцця рашэння, якую можна неафіцыйна сфармуляваць наступным чынам: улічваючы апісанне машыны Цьюрынга і ўвод, вызначце, ці спыніцца машына Цьюрынга ў канчатковым выніку пры працы з гэтым уводам, ці яна будзе працаваць вечна.
Для разгляду вырашальнасці праблемы спынення важна разумець саму канцэпцыю вырашальнасці. Праблема называецца вырашальнай, калі існуе алгарытм, які можа даць правільны адказ «так» ці «не» для кожнага асобніка задачы за канечны прамежак часу. І наадварот, праблема невырашальная, калі такога алгарытму не існуе.
Праблема прыпынку была ўпершыню ўведзена і даказана, што яна невырашальная Аланам Цьюрынгам у 1936 годзе. Доказ Цьюрынга з'яўляецца класічным прыкладам аргументу дыяганізацыі і ўключае ў сябе разумнае выкарыстанне спасылкі на сябе і супярэчнасці. Доказ можна акрэсліць наступным чынам:
1. Дапушчэнне вырашальнасці: Дзеля супярэчнасці выкажам здагадку, што існуе машына Цьюрынга ( H ), якая можа вырашыць праблему прыпынку. Гэта значыць, (H) прымае ў якасці ўваходных дадзеных пару ((M, w)), дзе (M) з'яўляецца апісаннем машыны Цьюрынга, (w) з'яўляецца ўваходным радком, а (H(M, w)) вяртае " так", калі (M) спыняецца на (w), і "не", калі (M) не спыняецца на (w).
2. Пабудова парадаксальнай машыны: Выкарыстоўваючы (H), пабудуйце новую машыну Цьюрынга (D), якая прымае адзін увод (M) (апісанне машыны Цьюрынга) і паводзіць сябе наступным чынам:
– ( D(M) ) працуе ( H(M, M) ).
– Калі ( H(M, M) ) вяртае "не", то ( D(M) ) спыняецца.
– Калі ( H(M, M) ) вяртае "так", то ( D(M) ) уваходзіць у бясконцы цыкл.
3. Самаспасылка і супярэчнасць: Разгледзім паводзіны (D), калі яму даецца ўласнае апісанне ў якасці ўваходных дадзеных. Няхай (d) будзе апісаннем (D). Тады мы маем два выпадкі:
– Калі ( D(d) ) спыняецца, то паводле вызначэння ( D ), ( H(d, d) ) павінен вяртаць «не», што азначае ( D(d) ) не павінен спыняцца — супярэчнасць.
– Калі ( D(d) ) не спыняецца, то паводле вызначэння ( D ), ( H(d, d) ) павінен вярнуць «так», што азначае ( D(d) ) павінен спыніцца — зноў супярэчнасць .
Паколькі абодва выпадкі прыводзяць да супярэчнасці, першапачатковае дапушчэнне, што ( H ) існуе, павінна быць ілжывым. Такім чынам, праблема прыпынку невырашальная.
Гэта доказ дэманструе, што не існуе агульнага алгарытму, які можа вырашыць праблему прыпынку для ўсіх магчымых машын Цьюрынга і ўваходных дадзеных. Невырашальнасць праблемы прыпынку мае глыбокія наступствы для межаў вылічэнняў і таго, што можа быць алгарытмічна вызначана. Гэта паказвае, што існуюць неад'емныя абмежаванні на тое, што можна вылічыць, і некаторыя праблемы па-за межамі любога алгарытму.
Каб дадаткова праілюстраваць наступствы праблемы прыпынку, разгледзім наступныя прыклады:
- Праграма верыфікацыі: Можна было б пажадаць пераканацца, што дадзеная праграма завяршаецца для ўсіх магчымых уваходаў. З-за невырашальнасці праблемы прыпынку немагчыма стварыць верыфікатар праграмы агульнага прызначэння, які можа вызначыць для кожнай магчымай праграмы і ўводу, ці спыніцца праграма.
- аналіз бяспекі: У сферы кібербяспекі можна прааналізаваць, ці спыніцца ў канчатковым выніку частка шкоднаснага ПЗ. Невырашальнасць праблемы спынення азначае, што не існуе агульнага алгарытму, які можа вызначыць, ці спыніцца якое-небудзь дадзенае шкоднаснае ПЗ.
- Матэматычныя доказы: Праблема прыпынку звязана з тэарэмамі Гёдэля аб няпоўнасці, якія сцвярджаюць, што ў любой досыць магутнай фармальнай сістэме ёсць праўдзівыя сцверджанні, якія не могуць быць даказаны ў сістэме. Невырашальнасць праблемы прыпынку паказвае, што існуюць пытанні аб паводзінах алгарытмаў, на якія нельга адказаць у рамках алгарытмічных вылічэнняў.
Невырашальнасць праблемы прыпынку таксама прыводзіць да канцэпцыі скарачальнасць у тэорыі складанасці вылічэнняў. Праблема (A) называецца зводнай да задачы (B), калі рашэнне (B) можа быць выкарыстана для рашэння (A). Калі б праблема прыпынку была вырашальнай, то многія іншыя невырашальныя праблемы таксама можна было б вырашыць звядзеннем да праблемы прыпынку. Аднак, паколькі праблема прыпынку невырашальная, любая праблема, якую можна звесці да праблемы прыпынку, таксама невырашальная.
Праблема прыпынку машыны Цьюрынга невырашальная. Гэты вынік з'яўляецца краевугольным каменем тэарэтычнай інфарматыкі і мае далёка ідучыя наступствы для нашага разумення вылічэнняў, алгарытмічных абмежаванняў і прыроды матэматычнай ісціны.
Іншыя апошнія пытанні і адказы адносна Рашучасць:
- Ці можа стужка быць абмежавана памерам уваходу (што эквівалентна таму, што галоўка машыны Цьюрынга абмежавана рухацца за межы уваходу TM стужкі)?
- Што гэта значыць для розных варыянтаў машын Цьюрынга быць эквівалентнымі па вылічальных магчымасцях?
- Ці можа распазнавальная па Цьюрынгу мова ўтвараць падмноства вырашальнай мовы?
- Калі ў нас ёсць дзве TM, якія апісваюць вырашальную мову, пытанне эквівалентнасці ўсё яшчэ невырашальнае?
- Чым праблема прыняцця для лінейных абмежаваных аўтаматаў адрозніваецца ад праблемы машын Цьюрынга?
- Прывядзіце прыклад задачы, якую можна вырашыць з дапамогай лінейнага абмежаванага аўтамата.
- Растлумачце паняцце вырашальнасці ў кантэксце лінейных абмежаваных аўтаматаў.
- Як памер стужкі ў лінейных абмежаваных аўтаматах уплывае на колькасць розных канфігурацый?
- У чым галоўнае адрозненне паміж лінейнымі абмежаванымі аўтаматамі і машынамі Цьюрынга?
- Апішыце працэс пераўтварэння машыны Цьюрынга ў набор плітак для PCP і тое, як гэтыя пліткі прадстаўляюць гісторыю вылічэнняў.
Глядзіце дадатковыя пытанні і адказы ў раздзеле "Вырашальнасць".