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