Ці з'яўляецца алгарытмічна вылічальная задача праблемай, вылічальнай машынай Цьюрынга ў адпаведнасці з тэзісам Чэрча-Цьюрынга?
Тэзіс Чэрча-Цьюрынга з'яўляецца асноватворным прынцыпам у тэорыі вылічэнняў і іх складанасці. Ён сцвярджае, што любая функцыя, якая можа быць вылічана з дапамогай алгарытму, таксама можа быць вылічана з дапамогай машыны Цьюрынга.
Гэты тэзіс не з'яўляецца фармальнай тэарэмай, якую можна даказаць; хутчэй, гэта гіпотэза аб прыродзе вылічальных функцый. Гэта сведчыць аб тым, што канцэпцыя "алгарытмічнай вылічальнасці" адэкватна ахоплена машынамі Цьюрынга.
Машына Цьюрынга - гэта абстрактная матэматычная мадэль вылічэнняў, якая вызначае ідэалізаваную машыну, здольную выконваць любыя вылічэнні, якія могуць быць алгарытмічна вызначаны. Ён складаецца з бясконцай стужкі, падзеленай на вочкі, галоўкі стужкі, якая можа чытаць і запісваць сімвалы на стужцы, і канчатковага набору станаў, якія вызначаюць дзеянні машыны на аснове бягучага стану і сімвала, які чытаецца. Машына працуе ў адпаведнасці з наборам правілаў або функцыяй пераходу, якая вызначае, як яна перамяшчаецца паміж станамі, чытае і запісвае сімвалы і рухае галоўку стужкі.
Тэзіс Чэрча-Цьюрынга сцвярджае, што калі праблема можа быць вырашана любымі вылічальнымі сродкамі, то існуе машына Цьюрынга, якая можа вырашыць гэтую праблему. Гэты тэзіс мае глыбокія наступствы для вобласці інфарматыкі, паколькі забяспечвае фармальную аснову для разумення межаў таго, што можна вылічыць.
Каб праілюстраваць канцэпцыю, разгледзім праблему вызначэння таго, ці з'яўляецца дадзены радок паліндромам. Паліндром - гэта радок, які чытаецца аднолькава наперад і назад. Алгарытм вырашэння гэтай задачы можа ўключаць у сябе параўнанне першага і апошняга сімвалаў радка, затым другога і перадапошняга сімвалаў і гэтак далей, пакуль не будуць параўнаны ўсе сімвалы. Калі ўсе адпаведныя сімвалы супадаюць, радок з'яўляецца паліндромам; у адваротным выпадку гэта не так.
Для вырашэння гэтай праблемы можна пабудаваць машыну Цьюрынга. Машына пачынала са счытвання першага сімвала радка і пазначэння яго нейкім чынам (напрыклад, напісаннем над ім спецыяльнага сімвала). Затым ён перамесціцца ў канец радка, прачытае апошні сімвал і параўнае яго з першым сімвалам. Калі яны супадаюць, машына адзначае апошні сімвал і вяртаецца да наступнага неадзначанага сімвала з пачатку, паўтараючы працэс, пакуль усе сімвалы не будуць параўнаны. Калі ў нейкі момант сімвалы не супадаюць, машына спыняецца і адхіляе ўвод. Калі ўсе сімвалы супадаюць, машына спыніцца і прыме ўвод.
Гэты прыклад дэманструе, як праблему, якую можна апісаць алгарытмічна, можна таксама вырашыць з дапамогай машыны Цьюрынга, што пацвярджае тэзіс Чэрча-Цьюрынга. Тэзіс мае на ўвазе, што любая вылічальная задача, якая можа быць вырашана з дапамогай алгарытму, у прынцыпе можа быць вырашана з дапамогай машыны Цьюрынга.
У кантэксце кібербяспекі і тэорыі складанасці вылічэнняў тэзіс Чэрча-Цьюрынга мае значныя наступствы для разумення межаў таго, што можна вылічыць, і рэсурсаў, неабходных для гэтага. Тэорыя складанасці вылічэнняў займаецца класіфікацыяй вылічальных задач на аснове іх уласцівай складанасці і рэсурсаў (такіх як час і прастора), неабходных для іх рашэння. Тэзіс забяспечвае аснову для гэтай класіфікацыі шляхам стварэння агульнай асновы для вызначэння і параўнання вылічальнай магутнасці розных мадэляў вылічэнняў.
Адной з важных канцэпцый тэорыі складанасці вылічэнняў з'яўляецца адрозненне паміж вырашальнымі і невырашальнымі праблемамі. Праблема вырашальная, калі існуе машына Цьюрынга, якая можа вырашыць яе для ўсіх магчымых уваходаў за канечны прамежак часу. З іншага боку, невырашальная праблема - гэта праблема, для якой не існуе такой машыны Цьюрынга. Праблема прыпынку, якая пытаецца, ці спыніцца дадзеная машына Цьюрынга на зададзеным уводзе, з'яўляецца класічным прыкладам невырашальнай праблемы. Алан Цьюрынг даказаў, што не існуе агульнага алгарытму, які можа вырашыць праблему прыпынку для ўсіх магчымых машын Цьюрынга і ўваходных дадзеных, прадэманстраваўшы існаванне па сваёй сутнасці невылічальных праблем.
Тэзіс Чэрча-Цьюрынга таксама звязаны з канцэпцыяй рэкурсіі, якая з'яўляецца фундаментальным метадам у інфарматыцы і матэматыцы для вызначэння функцый і рашэння задач. Рэкурсіўныя функцыі - гэта тыя функцыі, якія вызначаны ў тэрмінах саміх сябе, часта з базавым выпадкам для завяршэння рэкурсіі. Клас прымітыўна-рэкурсіўных функцый, якія вызначаюцца з дапамогай асноўных функцый і кампазіцыі і прымітыўнай рэкурсіі, з'яўляецца падмноствам класа агульных рэкурсіўных функцый, які ўключае ўсе функцыі, якія могуць быць вылічаны машынай Цьюрынга.
Машына Цьюрынга, якая запісвае апісанне сама сябе, з'яўляецца прыкладам самарэферэнцыяльнай або самарэплікацыйнай сістэмы, што звязана з канцэпцыяй рэкурсіі. Такая машына, якую часта называюць quine, уяўляе сабой праграму, якая стварае копію ўласнага зыходнага кода ў якасці выхаду. Квайны цікавыя з тэарэтычнага пункту гледжання, таму што яны дэманструюць здольнасць машыны Цьюрынга выконваць самарэферэнцыйныя вылічэнні, што можа мець наступствы для разумення абмежаванняў вылічэнняў і прыроды самарэплікацыйных сістэм.
Тэзіс Чэрча-Тьюрынга забяспечвае фундаментальную аснову для разумення прыроды алгарытмічнай вылічальнасці і межаў вылічэнняў. Ён сцвярджае, што любая праблема, якую можна вырашыць з дапамогай алгарытму, таксама можа быць вырашана з дапамогай машыны Цьюрынга, усталёўваючы агульную структуру для параўнання розных мадэляў вылічэнняў. Тэзіс мае глыбокія наступствы для тэорыі вылічальнай складанасці, паколькі забяспечвае аснову для класіфікацыі вылічальных праблем і разумення рэсурсаў, неабходных для іх вырашэння. Канцэпцыя машыны Цьюрынга, якая піша апісанне самой сябе, ілюструе магутнасць самарэферэнцыяльных вылічэнняў і здольнасць машын Цьюрынга выконваць складаныя рэкурсіўныя вылічэнні.
Іншыя апошнія пытанні і адказы адносна Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF:
- Якія асноўныя матэматычныя азначэнні, абазначэнні і ўводзіны неабходныя для разумення фармалізму тэорыі вылічальнай складанасці?
- Чаму тэорыя вылічальнай складанасці важная для разумення асноў крыптаграфіі і кібербяспекі?
- Якая роля рэкурсійнай тэарэмы ў дэманстрацыі невырашальнасці ATM?
- Разглядаючы КПК, які можа чытаць паліндромы, не маглі б вы падрабязна апісаць эвалюцыю стэка, калі ўвод з'яўляецца, па-першае, паліндромам, а па-другое, не паліндромам?
- Разглядаючы недэтэрмінаваныя КПК, суперпазіцыя станаў магчымая па азначэнні. Аднак недэтэрмінаваныя КПК маюць толькі адзін стэк, які не можа знаходзіцца ў некалькіх станах адначасова. Як такое магчыма?
- Што з'яўляецца прыкладам КПК, якія выкарыстоўваюцца для аналізу сеткавага трафіку і ідэнтыфікацыі шаблонаў, якія паказваюць на магчымыя парушэнні бяспекі?
- Што значыць, што адна мова больш магутная за іншую?
- Ці пазнаюцца кантэкстна-залежныя мовы машынай Цьюрынга?
- Чаму мова U = 0^n1^n (n>=0) нерэгулярная?
- Як вызначыць FSM, які распазнае двайковыя радкі з цотнай колькасцю сімвалаў «1», і паказаць, што з ім адбываецца пры апрацоўцы ўваходнага радка 1011?
Больш пытанняў і адказаў глядзіце ў раздзеле "Асновы тэорыі вылічальнай складанасці" EITC/IS/CCTF