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