wd wp Пошук: ⬜

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

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

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

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

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

Інтуітыўнае

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

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

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

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

M

( Q , Γ , Σ , s , b , F , δ )

{\displaystyle M=(Q,\Gamma ,\Sigma ,s,b,F,\delta ),}

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

дзе:

{\displaystyle Q,}

$\{\displaystyle Q\,\}$ азначае канечнае мноства станаў.

{\displaystyle \Gamma ,}

$\{\displaystyle \Gamma \,\}$ — канечны алфавіт стужкі.

Σ ⊂ Γ

{\displaystyle \Sigma \subset \Gamma }

$\{\displaystyle \Sigma \subset \Gamma \}$ — канечны пачатковы алфавіт.

s ∈ Q

{\displaystyle s\in Q}

$\{\displaystyle s\in Q\}$ — пачатковы стан машыны.

b

Γ ∖ Σ

{\displaystyle b=\Gamma \backslash \Sigma }

$\{\displaystyle b=\Gamma \backslash \Sigma \}$ — сімвал, які абазначае пустую ячэйку.

F ⊆ Q

{\displaystyle F\subseteq Q}

$\{\displaystyle F\subseteq Q\}$ — мноства канечных станаў (станаў, пры якіх машына скончвае працу).

δ : Q × Γ → Q × Γ × { L , N , R }

{\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{L,N,R\}}

$\{\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \\{L,N,R\\}\}$

Разнавіднасці

Дэтэрмінаванай машынай Цьюрынга называецца машына, у якой для кожнай

{\displaystyle \delta }

$\{\displaystyle \delta \}$ апісанае толькі адно дзеянне. У іншым выпадку машына называецца недэтэрмінаванай.

Шматстужкавая машына Цьюрынга

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

δ : Q ×

→ Q × ( Γ × { K , D , S }

)

{\displaystyle \delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{K,D,S\})^{k}}

$\{\displaystyle \delta :Q\times \Gamma ^\{k\}\rightarrow Q\times (\Gamma \times \\{K,D,S\\})^\{k\}\}$

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

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

Тэмы гэтай старонкі (4):
Катэгорыя·Тэорыя алгарытмаў
Катэгорыя·Інфармацыйныя машыны
Катэгорыя·Фармальныя метады
Катэгорыя·Тэорыя складанасці вылічэнняў