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

Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі
Перайсьці да: навігацыі, пошуку

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

Гісторыя стварэньня[рэдагаваць | рэдагаваць крыніцу]

Машына была створана Эланам Т’юрынгам у 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

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

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

Вонкавыя спасылкі[рэдагаваць | рэдагаваць крыніцу]

Commons-logo.svg  Машына Т’юрынгасховішча мультымэдыйных матэрыялаў