Машына Цьюрынга
Машына Цьюрынга — мадэль матэматычнай машыны, створаная для вызначэння паняцця алгарытму.
Гісторыя стварэння
[правіць | правіць зыходнік]Машына створана Аланам Цьюрынгам у 1936 годзе.
Апісанне машыны
[правіць | правіць зыходнік]Інтуітыўнае
[правіць | правіць зыходнік]Машына складаецца з наступных частак:
- Бясконцая стужка, падзеленая на ячэйкі. Кожная ячэйка ўтрымлівае пэўнае значэнне ці сімвал, які абазначае, што яна з’яўляецца пустой.
- Галоўка — паказвае на пэўную ячэйку, з якой вядзецца праца ў дадзены момант. Галоўка можа змяняць значэнне ячэйкі і перамяшчацца ўправа ці ўлева.
- Рэгістр стану — захоўвае інфармацыю пра стан машыны. Стан вызначае наступны крок і можа змяняцца падчас працы.
- Табліца дзеянняў — апісанне магчымых дзеянняў у залежнасці ад стану машыны і значэння ячэйкі, на якую паказвае галоўка.
Фармалізаванае
[правіць | правіць зыходнік]Машыну можна апісаць наступным чынам:
дзе:
азначае канечнае мноства станаў.
— канечны алфавіт стужкі.
— канечны пачатковы алфавіт.
— пачатковы стан машыны.
— сімвал, які абазначае пустую ячэйку.
— мноства канечных станаў (станаў, пры якіх машына скончвае працу).
Разнавіднасці
[правіць | правіць зыходнік]Дэтэрмінаванай машынай Цьюрынга называецца машына, у якой для кожнай апісанае толькі адно дзеянне. У іншым выпадку машына называецца недэтэрмінаванай.
Шматстужкавая машына Цьюрынга
[правіць | правіць зыходнік]Шматстужкавая машына Цьюрынга адрозніваецца тым, што складаецца з некалькіх стужак і, адпаведна, з некалькіх галовак. У такім разе апісанне функцыі выглядае наступным чынам:
Звярніце увагу, што стан апісваецца для ўсёй машыны, а не для кожнай галоўкі асобна.
У шматстужкавай машыне першая стужка звычайна называецца стужкай увядзення, апошняя — вывядзення, а сярэднія — працоўнымі.
Слоўнікі і энцыклапедыі | ||||
---|---|---|---|---|
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.