Вылічальная функцыя ў кантэксце тэорыі складанасці вылічэнняў адносіцца да функцыі, якую можна эфектыўна вылічыць з дапамогай алгарытму. Гэта фундаментальная канцэпцыя ў галіне інфарматыкі і гуляе важную ролю ў разуменні межаў вылічэнняў.
Каб вызначыць вылічальную функцыю, нам трэба стварыць фармальную аснову, якая дазваляе разважаць аб магчымасцях і абмежаваннях вылічальных мадэляў. Адной з такіх структур з'яўляецца машына Цьюрынга, якая была прадстаўлена Аланам Ц'юрынгам у 1936 годзе. Машына Ц'юрынга - гэта абстрактная матэматычная мадэль, якая складаецца з стужкі, падзеленай на ячэйкі, галоўкі для чытання-запісу і набору станаў. Машына працуе, счытваючы сімвал у бягучай ячэйцы, пераходзячы ў новы стан на аснове бягучага стану і сімвала і змяняючы сімвал у бягучай ячэйцы. Ён таксама можа перамяшчаць галоўку для чытання і запісу на адну ячэйку ўлева або ўправа.
У кантэксце машын Цьюрынга вылічальная функцыя вызначаецца як функцыя, для якой існуе машына Цьюрынга, якая пры любым уваходзе спыняецца і выдае правільны вынік для гэтага уваходу. Іншымі словамі, функцыя вылічальная, калі існуе алгарытм, які можа вылічыць яе значэнне для любога зададзенага ўваходу. Гэта паняцце цесна звязана з паняццем вырашальнасці, якое адносіцца да здольнасці вызначаць, ці задавальняе дадзены ўвод пэўнай уласцівасці.
Паняцце вылічальных функцый можа быць дадаткова фармалізавана з дапамогай канцэпцыі часовай складанасці. Часовая складанасць вымярае колькасць часу, неабходнага алгарытму для вырашэння задачы ў залежнасці ад памеру ўваходных дадзеных. Функцыя называецца вылічальнай за палінаміяльны час, калі існуе машына Цьюрынга, якая можа вылічыць функцыю за некалькі крокаў, якія з'яўляюцца палінамінальнымі па памеры ўваходных дадзеных. Функцыі, якія можна вылічыць з паліномным часам, лічацца эфектыўнымі, паколькі час іх працы расце не больш чым паліномна з павелічэннем памеру ўваходных дадзеных.
Каб праілюстраваць канцэпцыю вылічальных функцый, давайце разгледзім функцыю, якая вызначае, ці з'яўляецца дадзены лік простым. Гэтая функцыя прымае ўвод n і вяртае ісціну, калі n простае, і ілжыва ў адваротным выпадку. Функцыя праверкі простасці вылічальная, бо існуе алгарытм, напрыклад, рэшата Эратасфена, які можа вызначыць першаснасць любога зададзенага ліку.
Наадварот, разгледзім функцыю, якая вызначае, ці спыняецца дадзеная праграма на пэўным уводзе. Гэтая функцыя, вядомая як праблема прыпынку, не вылічальная. Гэта было даказана Аланам Цьюрынгам у 1936 годзе з дапамогай метаду, вядомага як дыяганалізацыя. Доказ Цьюрынга паказаў, што не можа быць алгарытму, які можа вырашыць для любой зададзенай праграмы і ўводу, спыніцца праграма ці будзе працаваць вечна.
Вылічальная функцыя ў кантэксце тэорыі складанасці вылічэнняў адносіцца да функцыі, якую можна эфектыўна вылічыць з дапамогай алгарытму. Гэта фундаментальнае паняцце ў інфарматыцы і цесна звязана з паняццем вырашальнасці. Паняцце вылічальных функцый фармалізавана з дапамогай машын Цьюрынга і часовай складанасці. У той час як многія функцыі вылічальныя, ёсць таксама функцыі, такія як праблема прыпынку, якія даказальна невылічальныя.
Іншыя апошнія пытанні і адказы адносна Вылічаныя функцыі:
- Што гэта значыць для розных варыянтаў машын Цьюрынга быць эквівалентнымі па вылічальных магчымасцях?
- Растлумачце сувязь паміж вылічальнай функцыяй і існаваннем машыны Цьюрынга, якая можа яе вылічыць.
- Якое значэнне заўсёды спыняецца машына Цьюрынга пры вылічэнні вылічальнай функцыі?
- Ці можна мадыфікаваць машыну Цьюрынга, каб заўсёды прымаць функцыю? Растлумачце, чаму ці не.
- Як машына Цьюрынга вылічвае функцыю і якая роля ўваходных і выходных стужак?