Машына Т'юрынга
Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі.
Машына Т'юрынга - мадэль матэматычнай машыны, створаная для вызначэння паняцця алгарытму.
Зьмест |
[рэдагаваць] Гісторыя стварэння
Машына была створана Аланам Т'юрынгам у 1936 годзе.
[рэдагаваць] Апісанне машыны
[рэдагаваць] Інтуітыўнае
Машына складаецца з наступных частак:
- Бясконцая лента, падзеленая на ячэйкі. Кожная ячэйка ўтрымлівае пэўнае значэнне ці сімвал, які абазначае, што яна з'яўляецца пустой.
- Галоўка - паказвае на пэўную ячэйку, з якой вядзецца праца ў дадзены момант. Галоўка можа змяняць значэнне ячэйкі і перамяшчацца ўправа ці ўлева.
- Рэгістр стану - захоўвае інфармацыю пра стан машыны. Стан вызначае наступны крок і можа змяняцца падчас працы.
- Табліца дзеянняў - апісанне магчымых дзеянняў у залежнасці ад стану машыны і значэння ячэйкі, на якую паказвае галоўка.
[рэдагаваць] Фармалізаванае
Машыну можна апісаць наступным чынам:
Failed to parse (Can't write to or create math output directory): M=(Q, \Gamma, \Sigma, s, b, F, \delta)\,
дзе:
Failed to parse (Can't write to or create math output directory): Q\,
aбазначае канечнае мноства станаў.
Failed to parse (Can't write to or create math output directory): \Gamma\,
- канечны алфавіт ленты.
Failed to parse (Can't write to or create math output directory): \Sigma \subset \Gamma
- канечны пачатковы алфавіт.
Failed to parse (Can't write to or create math output directory): s \in Q
- пачатковы стан машыны.
Failed to parse (Can't write to or create math output directory): b = \Gamma \backslash \Sigma
- сімвал, які абазначае пустую ячэйку.
Failed to parse (Can't write to or create math output directory): F \subseteq Q
- мноства канечных станаў (станаў, пры якіх машына скончвае працу).
Failed to parse (Can't write to or create math output directory): \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, N, R\}
[рэдагаваць] Разнавіднасці
Дэтэрмінаванай машынай Т'юрынга называецца машына, у якой для кожнай Failed to parse (Can't write to or create math output directory): \delta
апісанае толькі адно дзеянне. У іншым выпадку машына называецца недэтэрмінаванай.
[рэдагаваць] Шматлентачная машына Т'юрынга
Шматлентачная машына Т'юрынга адрозневаецца тым, што складаецца з некалькіх лентаў і, адпаведна, з некалькіх галовак. У такім разе апісанне функцыі выглядае наступным чынам:
Failed to parse (Can't write to or create math output directory): \delta: Q \times \Gamma^k \rightarrow Q \times (\Gamma \times \{K,D,S\})^k
Звярніце увагу, што стан апісваецца для ўсёй машыны, а не для кожнай галоўкі асобна.
У шматлентачнай машыне першая лента звычайна называецца лентай увядзення, апошняя - вывядзення, а сярэднія - працоўнымі.
