Машына Цьюрынга

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

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

Машына была створана Аланам Цьюрынгам у 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}$

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

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