Машына Цьюрынга
Машына Цьюрынга — мадэль матэматычнай машыны, створаная для вызначэння паняцця алгарытму.
Гісторыя стварэння[правіць | правіць зыходнік]
Машына была створана Аланам Цьюрынгам у 1936 годзе.
Апісанне машыны[правіць | правіць зыходнік]
Інтуітыўнае[правіць | правіць зыходнік]
Машына складаецца з наступных частак:
- Бясконцая стужка, падзеленая на ячэйкі. Кожная ячэйка ўтрымлівае пэўнае значэнне ці сімвал, які абазначае, што яна з'яўляецца пустой.
- Галоўка — паказвае на пэўную ячэйку, з якой вядзецца праца ў дадзены момант. Галоўка можа змяняць значэнне ячэйкі і перамяшчацца ўправа ці ўлева.
- Рэгістр стану — захоўвае інфармацыю пра стан машыны. Стан вызначае наступны крок і можа змяняцца падчас працы.
- Табліца дзеянняў — апісанне магчымых дзеянняў у залежнасці ад стану машыны і значэння ячэйкі, на якую паказвае галоўка.
Фармалізаванае[правіць | правіць зыходнік]
Машыну можна апісаць наступным чынам:
дзе:
aбазначае канечнае мноства станаў.
- канечны алфавіт ленты.
- канечны пачатковы алфавіт.
- пачатковы стан машыны.
- сімвал, які абазначае пустую ячэйку.
- мноства канечных станаў (станаў, пры якіх машына скончвае працу).
Разнавіднасці[правіць | правіць зыходнік]
Дэтэрмінаванай машынай Цьюрынга называецца машына, у якой для кожнай апісанае толькі адно дзеянне. У іншым выпадку машына называецца недэтэрмінаванай.
Шматлентачная машына Цьюрынга[правіць | правіць зыходнік]
Шматлентачная машына Цьюрынга адрозневаецца тым, што складаецца з некалькіх лентаў і, адпаведна, з некалькіх галовак. У такім разе апісанне функцыі выглядае наступным чынам:
Звярніце увагу, што стан апісваецца для ўсёй машыны, а не для кожнай галоўкі асобна.
У шматлентачнай машыне першая лента звычайна называецца лентай увядзення, апошняя — вывядзення, а сярэднія — працоўнымі.