![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png&w=640&q=50)
Тјурингова машина
From Wikipedia, the free encyclopedia
Тјуринговите машини се апстрактни машини кои покрај нивната едноставност можат да бидат приспособени да ја симулираат логичката улога на секој можен компјутер. Тјуринговите машини се опишани во 1936 од страна на Алан Тјуринг. Иако биле наменети за технички изводлива работа, Тјуринговите машини немале улога во практичната компјутерска технологија, но со истражување за границите на механичкото пресметување; тие всушност никогаш не биле направени (конструирани).
![]() | Оваа статија можеби бара дополнително внимание за да ги исполни стандардите за квалитет на Википедија. Ве молиме подобрете ја оваа статија ако можете. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png)
![Тјурингова машина со една лента](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Turingmaschine_mk.svg/250px-Turingmaschine_mk.svg.png)
Тјурингова машина која истовремено е способна да симулира и било која друга Тјурингова машина се нарекува Универзална Тјурингова машина (УТМ, или едноставно универзална машина). Поконкретна математичка дефиниција со слична универзална природа беше претставена од Alonzo Church, чија работа на lambda calculus се спои со Тјуринговата во формалната теорија на пресметување позната како теза на Church–Turing. Тезата дека Тјуринговите машини навистина ги опфаќаат информациите за делотворните методи од логиката и математиката, и овозможуваат прецизна дефиниција на алгоритам или механичка процедура. Неформален опис Концептот на Тјуринговата машина е заснован на идејата, некој да извршува добро дефинирана процедура со тоа што ќе ја менува содржината на неограничена хартиена лента, која е поделена на поделци кои на себе имаат еден од множеството симболи за конкретната азбука. Извршувачот треба да запамети една од можните состојби и процедурата е формулирана во многу едноставни чекори во вид "Ако моменталната состојба е 42 и симболот што е на таа позиција е '0' тогаш замени го со '1', помести еден симбол на десно, и земи ја 17-та состојба за наредна состојба."
За некои видови лентата се движи, а неискористениот простор е навистна празен. Инструкцијата што треба да се изврши е прикажана над означениот поделок (q4). (Приказ според Клини ( Kleene) (1952) p. 375).
Во некои видови главата е таа што се движи, а лентата е стационарна.
Инструкцијата што треба да се изврши (q1) се наоѓа во главата.
Во овој вид на модел "празниот поделок" од лентата е означен со 0.
Сивите поделци, заедно со се празниот поделок 0 кога се скенираат во главата на Тјуринговата машина, и поделците означени со 1, 1, B, и главниот симбол, ја означуваат состојбата на ситемот.
(Приказ според Мински (Minsky) (1967)).
Попрецизно, Тјуринговата машина се состои од:
- ЛЕНТА која е поделена не ќелии, поставени една до друга.
Секоја ќелија содржи симбол од некоја конечна азбука. Азбуката содржи и специјални бленк (blank) симболи (тука означени со 'B') и еден или повеќе други симболи. Лентата се претпоставува дека е неограничена од лево и од десно, т.е. Тјуринговата машина секогаш има доволно лента за потребните пресметки односно функции кои треба да бидат извршени. Ќелиите на кои не е ништо испишано се сметаат за празни односно пополнети со бленк симболот “B”. Во некои видови лентата има лев крај исполнет со специјален симбол; лентата завршува или е неограничена на десно.
- ГЛАВА која може да чита и запишува симболи на лентата и ја поместува лентата налево или надесно за една (и само една) ќелија во тој момент.
Во некои модели главата се мрда, а лентата е стационарна.
- ТАБЕЛА ("табела на премини”) од функции која, дадента состојба кај моделите со 5 елемнти во која моментално машината се наоѓа и симболот кој го чита од лентата и кажува на машината да ја изведе следната низа:
- (i) или избриши или напиши симбол на лентата, и
- (ii) помести ја главата ('L' еден чекор на лево или 'R' еден чекор на десно), и
- (iii) остани во истата состојба или премини во нова во зависност од дадените правила (зададени инструкции).
Кај моделите со 4 елементи табелата и кажува на машината (ia) избриши или напиши симбол или (ib) помести ја глава налево или надесно, и (ii) остани во истата состојба или премини во нова како што е кажано, но не двете акции (ia) и (ib) во истата инструкција. Во некои модели, ако нема внес во табелата за моменталната позиција на симболот и состојбата тогаш машината ќе го сопре процесот; други видови на модели на Тјурингова машина бараат сите места во табелата да бидат пополнети.
- БЕЛЕЖНИК НА СОСТОЈБИ кој ги регистрира состојбите од Тјуринговата табела.
Бројот на различни состојби е секогаш во конечен број и постои една специјална почетна состојба со која бележникот на состојби е иницијализиран. Тјуринг ова го дефинирал како "правила" кои ќе овозможат правилна работа на "компјутерот" (нештото) што работи со "недефинирани особини": "Овие правила соодветствуваат на “состојбите на мозокот”.
Се забележува дека секој дел од машината – неговата состојба - симболите - колекциите – неговите акции – запишувањето, бришењето и позицијата на лентата – е конечно, дискретно и ефикасно; тоа се должи на неограничената должина на лентата која всушност и овозможува голем простор за складирање.