Машына Т'юрынга

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

Машына Т'юрынга - мадэль матэматычнай машыны, створаная для вызначэння паняцця алгарытму.


Гісторыя стварэння[правіць | правіць зыходнік]

Машына была створана Аланам Т'юрынгам у 1936 годзе.

Апісанне машыны[правіць | правіць зыходнік]

Інтуітыўнае[правіць | правіць зыходнік]

Машына складаецца з наступных частак:

  • Бясконцая лента, падзеленая на ячэйкі. Кожная ячэйка ўтрымлівае пэўнае значэнне ці сімвал, які абазначае, што яна з'яўляецца пустой.
  • Галоўка - паказвае на пэўную ячэйку, з якой вядзецца праца ў дадзены момант. Галоўка можа змяняць значэнне ячэйкі і перамяшчацца ўправа ці ўлева.
  • Рэгістр стану - захоўвае інфармацыю пра стан машыны. Стан вызначае наступны крок і можа змяняцца падчас працы.
  • Табліца дзеянняў - апісанне магчымых дзеянняў у залежнасці ад стану машыны і значэння ячэйкі, на якую паказвае галоўка.

Фармалізаванае[правіць | правіць зыходнік]

Машыну можна апісаць наступным чынам:

M=(Q, \Gamma, \Sigma, s, b, F, \delta)\,

дзе:

Q\, aбазначае канечнае мноства станаў.

\Gamma\, - канечны алфавіт ленты.

\Sigma \subset \Gamma - канечны пачатковы алфавіт.

s \in Q - пачатковы стан машыны.

b = \Gamma \backslash \Sigma - сімвал, які абазначае пустую ячэйку.

F \subseteq Q - мноства канечных станаў (станаў, пры якіх машына скончвае працу).

\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, N, R\}

Разнавіднасці[правіць | правіць зыходнік]

Дэтэрмінаванай машынай Т'юрынга называецца машына, у якой для кожнай \delta апісанае толькі адно дзеянне. У іншым выпадку машына называецца недэтэрмінаванай.

Шматлентачная машына Т'юрынга[правіць | правіць зыходнік]

Шматлентачная машына Т'юрынга адрозневаецца тым, што складаецца з некалькіх лентаў і, адпаведна, з некалькіх галовак. У такім разе апісанне функцыі выглядае наступным чынам:

\delta: Q \times \Gamma^k \rightarrow Q \times (\Gamma \times \{K,D,S\})^k

Звярніце увагу, што стан апісваецца для ўсёй машыны, а не для кожнай галоўкі асобна.

У шматлентачнай машыне першая лента звычайна называецца лентай увядзення, апошняя - вывядзення, а сярэднія - працоўнымі.