Тјурингова машина
From Wikipedia, the free encyclopedia
Тјурингова машина је апстрактна "машина" која манипулише симболе на пољу траке према табели правила; тачније, то је математички модел који дефинише такав уређај. Упркос једноставности модела, било који рачунарски алгоритам, Тјурингова машина може бити конструисана тако да је у стању да симулира логику тог алгоритма.
Машина ради на бескрајној траци меморије подељеној у ћелије. Машина позиционира своју главу изнад ћелије и "чита" (скенира) симбол тамо. Затим по симболу и његовом садашњем месту у коначној табели корисничких наведених упутства машина (и) пише симбол (нпр цифре или писмо од коначног алфабета) у ћелији (неки модели омогућавају брисање симбола и / или не писање), затим (ии) или помера једну ћелију траке лево или десно (неки модели омогућавају непокретност, поједини модели померају главу), затим (иии) (како је утврђено у посматраном симболу и месту у табели машине) или наставља с наредним упутством или зауставља рачунање.
Тјурингову машину је изумео 1936. године Алан Тјуринг, коју је назвао А-машина (аутоматска машина). Са овим моделом Тјуринг је био у стању да одговори на два питања у негативном: (1) Да ли постоји машина која може да утврди да ли је било која произвољна машина на свом снимку "кружна" (нпр .замрзне или да не настави свој рачунарски задатак); Слично томе, (2) не постоји машина која може да утврди да ли ће било која произвољна машина на свом снимку икада штампати дати симбол. Тако пружајући математички опис врло једноставног уређаја произвољним израчунавањем, био је у стању да докаже својства рачунања уопште - и посебно, неизрачунљивости Хилбертовог Entscheidungsproblem ("Проблем одлука").
Тако, Тјурингове машине доказују основна ограничења на снази механичког израчунавања. Док они могу изразити произвољне прорачуне, њихов минималистички дизајн их чини неподобним за обрачун у пракси: стварни рачунари су засновани на различитим дизајнима који, за разлику од Тјуринг машине, користе RAM (меморија).
Тјурингова потпуност је способност за систем инструкција да симулирају Тјурингову машину. Програмски језик који је Тјуринг потпун теоретски је у стању да изрази све задатке остварив рачунарима; скоро сви програмски језици су Тјуринг потпуни.