Топ-100
Back

ⓘ Машына Цьюрынга. Машыну можна апісаць наступным чынам: M = Q, Γ, Σ, s, b, F, δ {\displaystyle M=Q,\Gamma,\Sigma,s,b,F,\delta\,} дзе: Q {\displaystyle Q\,} aбазн ..




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

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

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

M = Q, Γ, Σ, s, b, F, δ {\displaystyle M=Q,\Gamma,\Sigma,s,b,F,\delta\,}

дзе:

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

Γ {\displaystyle \Gamma \,} - канечны алфавіт ленты.

Σ ⊂ Γ {\displaystyle \Sigma \subset \Gamma } - канечны пачатковы алфавіт.

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

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

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

δ: Q × Γ → Q × Γ × { L, N, R } {\displaystyle \delta:Q\times \Gamma \to Q\times \Gamma \times \{L,N,R\}}

                                     

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

Дэтэрмінаванай машынай Цьюрынга называецца машына, у якой для кожнай δ {\displaystyle \delta } апісанае толькі адно дзеянне. У іншым выпадку машына называецца недэтэрмінаванай.

Шматлентачная машына Цьюрынга

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

δ: Q × Γ k → Q × Γ × { K, D, S } k {\displaystyle \delta:Q\times \Gamma ^{k}\rightarrow Q\times \Gamma \times \{K,D,S\}^{k}}

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

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