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

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

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

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

 Інтуітыўнае 

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

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

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

дзе:

 азначае канечнае мноства станаў.

 — канечны алфавіт стужкі.

 — канечны пачатковы алфавіт.

 — пачатковы стан машыны.

 — сімвал, які абазначае пустую ячэйку.

 — мноства канечных станаў (станаў, пры якіх машына скончвае працу).

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

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

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

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

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

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