Турингов строј

Турингови стројеви су изнимно једноставни апстрактни уређаји за манипулацију знаковима (симболима) који - унаточ једноставности дизајна - могу бити прилагођени да симулирају логику било којег рачуналног алгоритма (уз садашње поимање алгоритма). Описао их је 1936. Алан Туринг. Турингови стројеви не користе се у практичне сврхе, већ у мисаоним експериментима, гдје најважнију примјену налазе у истраживању граница могућности израчунавања рачуналним алгоритмима. Проучавање њихових својстава пружа далекосежне увиде у питања рачунарске знаности и теорије сложености.

Турингов строј који може симулирати било који други Турингов строј се зове Универзални Турингов строј (УТС или једноставно универзални строј). Више математички оријентирану дефиницију са сличном "универзалном" природом је увео Алонзо Цхурцх, чији се рад на ламбда рачуну испреплео са Туринговим у формалној теорији израчунљивости познатој као Цхурцх-Турингова хипотеза. Хипотеза повезује строгу формалну дефиницију Туринговог строја и интуитивне идеје израчунљивости, те на тај начин пружа прецизну дефиницију алгоритма или 'механичког поступка'.

Сажети формални опис Туринговог строја:

"Турингов строј је коначни аутомат повезан са вањским медијем за похрану или меморирање" (Минскy (1967) п. 117)

"Турингов строј је есенцијално коначни секвенцијални строј који има могућност комуницирања са вањским спремиштем информација" (Боотх (1967), п. 354)

Коначни аутомат је представљен таблицом стања и својим регистром стања. "Вањски медиј за похрану" јест трака. Улаз строја је прочитани знак са траке. Излаз строја јест знак који се пише на траку или наредба за брисање знака те наредба за помицање траке улијево или удесно.

Хопцрофт и Уллман (1979, п. 148) формално дефинирају (једнотрачни) Турингов строј као уређену седморку ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$ гдје

• ${\displaystyle Q}$ је коначан скуп стања
• ${\displaystyle \Gamma }$ је коначан скуп знакова траке (абецеда траке)
• ${\displaystyle b\in \Gamma }$ је истакнути знак којим се означава празна ћелија (једини знак којем је дозвољено да буде исписан на траци бесконачно много пута у сваком кораку израчуна)
• ${\displaystyle \Sigma }$, подскуп скупа ${\displaystyle \Gamma }$ не укључујући б је скуп улазних знакова (или улазна абецеда)
• ${\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}}$ је парцијална функција (није дефинирана на цијелој домени) звана функција пријелаза, гдје је L помак улијево, Р помак удесно.
• ${\displaystyle q_{0}\in Q}$ је почетно или иницијално стање
• ${\displaystyle F\subseteq Q}$ је скуп прихватљивих или финалних стања

Турингов строј на Wикимедијиној остави

• Таyлор L. Боотх (1967), Сеqуентиал Мацхинес анд Аутомата Тхеорy, Јохн Wилеy анд Сонс, Инц., Неw Yорк.
• Јохн Хопцрофт анд Јеффреy Уллман (1979). Интродуцтион то Аутомата Тхеорy, Лангуагес анд Цомпутатион (1ст едитион изд.). Аддисон-Wеслеy, Реадинг Масс. ИСБН 0-201-02988-X.. 
• Алан Туринг (1936), "Он Цомпутабле Нумберс, Wитх ан Апплицатион то тхе Ентсцхеидунгспроблем", Процеедингс оф тхе Лондон Матхематицал Социетy, Сериес 2, Волуме 42 (1936). Епринт.
• Марвин Минскy, Цомпутатион: Фините анд Инфините Мацхинес, Прентице-Халл, Инц., Н.Ј., 1967.
• Синиша Србљић (2003). Језични процесори 1. Елемент. ИСБН 953-197-129-3.