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

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

Гісторыя стварэньня

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

Апісаньне машыны

Інтуітыўнае

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

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

Фармалізаванае

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

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

дзе:

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

$\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}$

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

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