Википедија

Тјурингова машина: Разлика помеѓу преработките

Интерактивен преглед на историјата
[непроверена преработка][непроверена преработка]
← Постаро уредувањеПоново уредување →
Избришана содржина Додадена содржина
НагледноВикитекст
Нема опис на уредувањето
сНема опис на уредувањето
Ред 1:
{{внимание}}
[[Тјуринговите машини | Тјурингови машини |Tjuringova masina |Tjuringova mashina | Tjuringovi mashini | Tjuringovi masini | турингова машина | турингови машини | turingova masina | turingova mashina | Турингова машина]]
'''Тјуринговите машини''' се апстрактни машини кои покрај нивната едноставност можат да бидат приспособени да ја симулираат логичката улога на секој можен [[Слика:tjuring.jpg|десно|Википедија Енциклопедија]]
компјутер. Тјуринговите машини се опишани во 1936 од Alanстрана Turingна [[Алан Тјуринг]]. Иако биле наменети за технички изводлива работа, Тјуринговите машини немале улога во практичната компјутерска технологија , но со истражување за границите на механичкото пресметување; тие всушност никогаш не биле направени (конструирани).
 
Тјурингова машина која истовремено е способна да симулира и било која друга Тјурингова машина се нарекува Универзална Тјурингова машина (УТМ, или едноставно универзална машина). Поконкретна математичка дефиниција со слична универзална природа беше претставена од Alonzo Church, чија работа на lambda calculus се спои со Тјуринговата во формалната теорија на пресметување позната како теза на Church–Turing. Тезата дека Тјуринговите машини навистина ги опфаќаат информациите за ефективните методи од логиката и математиката, и овозможуваат презцизна дефиниција на алгоритам или механичка процедура.
Неформален опис
Концептот на Тјуринговата машина е базиран на идејата, некој да извршува добро дефинирана процедура со тоа што ќе ја менува содржината на неограничена хартиена лента, која е поделена на поделци кои на себе имаат еден од множеството симболи за конкретната азбука. Извршувачот треба да запамети една од можните состојби и процедурата е формулирана во многу едноставни чекори во вид "Ако моменталната состојба е 42 и симболот што е на таа позиција е '0' тогаш замени го со '1', помести еден симбол на десно, и земи ја 17-та состојба за наредна состојба."
 
[[Слика:tjuring3.jpg]]
 
 
За некои видови лентата се движи ,а неискористениот простор е навистна празен. Инструкцијата што треба да се изврши е прикажана над означениот поделок (q4). (Приказ според Клини ( Kleene) (1952) p.375).
[[Слика:tjuring4.jpg]]
 
Ред 18 ⟶ 17:
Попрецизно , Тјуринговата машина се состои од:
 
1. *'''ЛЕНТА''' која е поделена не ќелии, поставени една до друга. Секоја ќелија содржи симбол од некоја конечна азбука. Азбуката содржи и специјални бленк (blank) симболи (тука означени со 'B') и еден или повеќе други симболи. Лентата се претпоставува дека е неограничена од лево и од десно,т.е., Тјуринговата машина секогаш има доволно лента за потребните пресметки односно функции кои треба да бидат извршени. Ќелиите на кои не е ништо испишано се сметаат за празни односно пополнети со бленк симболот “B”. Во некои видови лентата има лев крај исполнет со специјален симбол; лентата завршува или е неограничена на десно.
 
2. *'''ГЛАВА''' која може да чита и запишува симболи на лентата и ја поместува лентата налево или надесно за еднаш (и само една) една ќелија во тој момент. Во некои модели главата се мрда,а лентата е стационарна.
 
3. *'''ТАБЕЛА''' ("табела на премини”) од функции која, дадента состојба кај моделите со 5 елемнти во која моментално машината се наоѓа и симболот кој го чита од лентата и кажува на машината да ја изведе следнта секвенца :
:(i) или избриши или напиши симбол на лентата, и
:(ii) помести ја главата ('L' еден чекор на лево или 'R' еден чекор на десно), и ▼
 
:(iii) остани во истата состојба или премини во нова во зависност од дадените правила (зададени инструкции). Кај моделите со 4 елементи табелата и кажува на машината (ia) избриши или напиши симбол или (ib) помести ја глава налево или надесно, и (ii) остани во истата состојба или премини во нова како што е кажано, но не двете акции (ia) и (ib) во истата инструкција. Во некои модели, ако нема внес во табелата за моменталната позиција на симболот и состојбата тогаш машината ќе го сопре процесот; други видови на модели на Тјурингова машина бараат сите места во табелата да бидат пополнети. ▼
▲(ii) помести ја главата ('L' еден чекор на лево или 'R' еден чекор на десно), и
 
▲(iii) остани во истата состојба или премини во нова во зависност од дадените правила (зададени инструкции). Кај моделите со 4 елементи табелата и кажува на машината (ia) избриши или напиши симбол или (ib) помести ја глава налево или надесно, и (ii) остани во истата состојба или премини во нова како што е кажано, но не двете акции (ia) и (ib) во истата инструкција. Во некои модели, ако нема внес во табелата за моменталната позиција на симболот и состојбата тогаш машината ќе го сопре процесот; други видови на модели на Тјурингова машина бараат сите места во табелата да бидат пополнети.
 
4. БЕЛЕЖНИК НА СОСТОЈБИ кој ги регистрира состојбите од Тјуринговата табела. Бројот на различни состојби е секогаш во конечен број и постои една специјална почетна состојба со која бележникот на состојби е иницијализиран . Тјуринг ова го дефинирал како "правила" кои ќе овозможат правилна работа на "компјутерот" (нештото) што работи со "недефинирани особини": ▼
"Овие правила соодветствуваат на “состојбите на мозокот” ▼
 
▲4. *'''БЕЛЕЖНИК НА СОСТОЈБИ''' кој ги регистрира состојбите од Тјуринговата табела. Бројот на различни состојби е секогаш во конечен број и постои една специјална почетна состојба со која бележникот на состојби е иницијализиран . Тјуринг ова го дефинирал како "правила" кои ќе овозможат правилна работа на "компјутерот" (нештото) што работи со "недефинирани особини":
▲"Овие правила соодветствуваат на “состојбите на мозокот” .
 
Се забележува дека секој дел од машината – неговата состојба- симболите-колекциите – неговите акции – запишувањето,бришењето и позицијата на лентата – е конечно, дискретно и ефикасно; тоа се должи на неограничената должина на лентата која всушност и овозможува голем простор за складирање.
 
 
== Формална дефиниција за Тјурингова машина со една лента ==
Преземено од „https://mk.wikipedia.org/wiki/Тјурингова_машина“