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

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

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

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

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

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

дзе:

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

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

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

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

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

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

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

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

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

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

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

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

Слоўнікі і энцыклапедыі	Вялікая кітайская · Вялікая расійская (старая версія) · Вялікая расійская (навукова-адукацыйны партал) · Britannica (онлайн) · Universalis
Нарматыўны кантроль BNE: XX550362 · BNF: 11978871z · GND: 4203525-9 · LCCN: sh85138778 · Microsoft: 29248071 · NDL: 00573533 · SUDOC: 027831655