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