ՀՍՀ/«ԹՅՈՒՐԻՆԳԻ ՄԵՔԵՆԱ»

«ԹՅՈՒՐԻՆԳԻ ՄԵՔԵՆԱ», մեքենայի վերացական հասկացություն, ալգորիթմի (ընթացակարգի) գաղափարի մաթեմատիկական ճշգրտումներից է: Առաջարկել է U. Թյուրինգը, 1937-ին: «Թ. մ.» աշխատում է քայլ առ քայլ, ժամանակի ընդհատ պահերին և որոշվում է. ա) հաջորդական բջիջների բաժանված անվերջ ժապավենով, որի յուրաքանչյուր բշիջը տվյալ պահին կարող է լինել դատարկ կամ պարունակել նախօրոք որոշված a 1, …, an նիշերից մեկը, բ) կառավարող սարքով, որը յուրաքանչյուր պահին գտնվում է նախօրոք որոշված q 0, q 1 …, qk «ներքին» վիճակներից մեկում (որոնցից գ 0-ն և qk-ն համարվում են սկզբնական և եզրափակիչ) և կցված է ժապավենի որևէ բջջին, գ) ծրագրով, որը, ելնելով դիտարկվող պահին կառավարող սարքի վիճակից և այն բջջի պարունակությունից, որին կցված է, միարժեքորեն որոշում է, թե որ նիշը պետք է զետեղվի այդ բջջի մեջ, որ ներքին վիճակին պետք է անցնի կառավարող սարքը և որ բջջին վերակցվի՝ նույնին, թե` նրա անմիջական հարևաններին: «Թ. մ.» աշխատում է այսպես, ժապավենի վերջավոր հատվածում զետեղվում է նիշերի մի շարան, կառավարող սարքը գտնվում է սկզբնական վիճակում՝ կցված շարանի ձախ կողմից առաջին բջջին: Այնուհետև, ըստ իր ծրագրի, սկսում է գործել կառավարող սարքը: Երբ այն հասնում է եզրափակիչ վիճակին, «Թ. մ»ի աշխատանքը համարվում է ավարտված: Ժապավենի վրա առաջացած նիշերի շարանն էլ համարվում է սկզբնական շարանի վերամշակման արդյունքը: Առ այսօր հայտնի չէ և ոչ մի ընթացակարգ, որը իրացնելի չլինի «Թ. մ.»ով:

Գրկ. Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965.

Հ. Մարանջյան