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

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

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

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

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

Апісаньне машыны[рэдагаваць | рэдагаваць крыніцу]

Інтуітыўнае[рэдагаваць | рэдагаваць крыніцу]

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

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

Фармалізаванае[рэдагаваць | рэдагаваць крыніцу]

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

дзе:

aбазначае канцоўнае мноства станаў.

 — канцоўны альфабэт стужкі.

 — канцоўны пачатковы альфабэт.

 — пачатковы стан машыны.

 — сымбаль, які абазначае пустую ячэю.

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

Разнавіднасьці[рэдагаваць | рэдагаваць крыніцу]

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

Шматстужкавая машына Т’юрынга[рэдагаваць | рэдагаваць крыніцу]

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

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

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

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

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