Компьютер архитектурасы

Әрбір команданың өз нөмірі бар: і. Жебеше қозғалыс бағытын көрсетеді. Команданың соңында  тұрған екінші j саны жөнелткіш деп  аталады. Басқаруды беру командасында екі жөнелткіш болуы мүмкін. Сондықтан  да абстракты автомат програмасының  екі бірдей қасиеті болуға тиіс:

1) бірінші орында тізімде әрқашан  1-нөмірлі команда тұрады, 

    екінші орында 2-нөмірлі және т.б;                 

2) кез келген команданы жөнелткіш  әрқашан бағдарлама командаларының  тізімінде орналасқан.

Таспаны солға немесе оңға қозғағаннан кейін  түбіртек секцияның (бос немесе ен жазылған) күй-жайын оқиды. 

Қай секциялар бос, қайсысы белгіленгендігі  туралы ақпарат таспа күйін немесе автомат күйін бейнелейді. Автомат  программасы деп командалардың  ақырлы бос емес тізімін айтады.

Абстракты автомат жұмысы үшін бағдарламаны және бастапқы күй-жайды, яғни түбіртектің  орнын және таспа ұяшықтарының күй-жайын  беру керек.

Әрбір қадам сайын бір команда орындалады, сонан соң нөмірі жөнелткіште  көрсетілген команда орындала бастайды. Егер бұл команданың екі жөнелткіші болса, және түбіртек астында бос  ұяшық болса, онда жоғарғы жөнелткіш  нөмірі бар команда орындалады. Егер түбіртек астында ені бар ұяшық  болса, онда төменгі жөнелткіш нөмірі бар команда орындалады. Басқаруды  беру командасының орындалуы автомат  күйін (ендердің ешбірі жойылмайды да қойылмайды, және таспа қозғалыссыз  қалады). Автоматты іске қосқанда мына жағдайдың бірі орын алуы мүмкін:

автомат орындалмайтын команданы (енді бос  емес ұяшыққа жазу, бос ұяшықта  енді өшіру) орындауға дейін жетті, программаның орындалуы тоқталады, автомат тоқтайды, нәтижесіз тоқтау болады;

автомат стоп командасына дейін жетті, программа  орындалды деп есептелінеді, нәтижелі тоқтау болады;

автомат нәтижелі де, нәтижесіз де тоқтауға жетпейді, жұмыс толассыз жүре береді (автомат ілініп қалды).

Пост  машинасының типті программаларының орындалу барысындағы автомат жұмысын  қарастырып көрейік. Түбіртектің бастапқы күйі берілсін және бос таспада екі  ен салу керек болсын.

Бастапқы күйі
	M 2
	M 4
	Стоп 4

Циклдық үрдісті ұйымдастыру үшін шартты өту командасын қалай пайдалануға  болатынын көрсетейік. Таспада қатарынан  бірнеше еннен тұратын жазба  бар және түбіртек ең шеткі оң жақ  еннің үстінде тұрсын. Түбіртекті солға бірінші бос орынға дейін  жылжыту қажет.

Бастапқы күйі	1	2	3
			стоп 3
1-жол		п. 1
2-жол		п. 1
3-жол		п. 1
4-жол		п. 3	стоп

Шартты  өту командасы циклдық үрдістерді ұйымдастырудың негізгі құралдарының бірі болып табылады, мысалы бос  шаршыдан жоғары орналасқан түбіртектен  оң жақ (немесе сол жақ) бірінші енді табу үшін; түбіртектің солынан ( немесе оңынан ) бос шаршы табу, егер ол еннен  жоғары орналасқан болса, және т. б.

Осындай, Пост машинасы сияқты қарапайым автоматтарда сандарға әртүрлі амалдар қолдануға  болады. Ол үшін абстракты автоматта  сандарды көрсету қажет.   

Санды автоматты бейнелеу ен салынған секциялар (ұяшықтар) тізбегі арқылы жүзеге асырылады. Бұл тізбек массив деп аталады, ал ондағы секциялар саны- массивтің  ұзындығы.

 

n санын таспада ұзындығы n+1 массиві арқылы беру мақұлданған. Мысалы, 6,3 және 2  сандары автоматтық бейнелері арқылы суретте былай берілген:

Пост  машинасында пайдаланылатын сандарды жазу жүйесі позициялық емес екендігіне  көңіл аударайық.

Кез келген санға бір қосудың программасын жасайық. Ол ұшін Пост машинасы үшін мына қасиетке ие болатын программа жазу қажет болады: таспаға жазылған кезкелген  п саны үшін программа  п+1 санын  таспаның кез келген жеріне жазып, нәтижелі тоқтауы керек.

Таспада бір ғана сан жазылған және түбіртек осы санға жататын ен салынған шаршының бірінен жоғары орналасқан болсын. Есепті шешу үшін түбіртекті бірінші  бос шаршыға дейін солға (оңға) орын ауыстыруға, сонан соң ен салуға болады.

Программа келесі түрде болуы мүмкін:

1-нұсқа			2-нұсқа
1.			1.
2.			2.
3.	M 4		3.	M 4
4.	стоп 4		4.	стоп 4

Бастапқы  күй-жай санатында кез келген күйі алынуы  мүмкін. Онда түбіртек таспаның белгіленген ұяшықтарының бірінде орналасады (яғни сандар жиынтығынан  жоғары). Бұл жағдайда программа  күрделілене түседі. Түбіртекті өткен  мысалда қарастырылған күйге  келтіретін, “санды іздеу блогы”- екі  команда пайда болады.

Түбіртек  өзіне бірді қосу керек болатын  санның  сол жағында бірнеше  шаршы қашықтықта орналасқан болсын.

Төменде бірді оңына да солына да қосатын  программалардың толық мәтіні берілген:

1.			1.
2.			2.
3.			3.
4.	M 5		4.
5.	Стоп 5		5.	M 6
6.			6.	Стоп 6

Бірінші жағдайда түбіртекті санның солжақ шеткі  еніне орын ауыстырудың қажеті жоқ. Абстракты автомат көмегімен  сандық ақпаратты басқаша түрлендіруді де іске асыруға болады. Мысалы, екі  санды қосып көрейік. Жалпы қойылымда  бұл есеп былай тұжырымдалады: бір-бірінен  кезкелген қашықтықта таспаға жазылған а мен в сандарын қосу программасын құрастыру керек. Автоматтың бастапқы күйі суретте көрсетілген:

 

 

Программа жазу үшін, мысалы, солжақ массивті оңжақ  массивпен бірігіп кеткенше оңға қарай жылжыта беру қерек. Массивті жылжыту ең солжақ енді ең жақын  оңжақ бос секцияға (төменде көрсетілген  программаның № 1 және №7 командалары) көшіру (өшіру) арқылы жүргізіледі.

Массивтер тұтасқанда (№ 5 және   №6  командалар) нәтиже а+в+2  болады. Яғни бір артық  енді ( №4 команда) өшіру керек. Соңғы  күйінде түбіртек жаңа пайда болған қосындының сол жағында тұр.

1.	C 2		4.	C 5		7.	M 8		10.
2.			5.			8.			11.
3.			6.			9.			12.	стоп

Санның  түбіртектің оңында ма, солында ма жатқандығы белгісіз, бостапқы  шарттардың аса күрделілігі жағдайында санды  іздеудің мынандай принципін қолдануға  болады:

Түбіртекті  оңға, солға қозғай отырып, түбіртектің  бастапқы орыннан қашықтау дәрежесін  ен сала белгілей отырып, санды табамыз  сонан соң белгілі қосу программасын қолданамыз. Бұл жағдайда түбіртектің  сан ендерінің бірінің үстінде  тұрған- тұрмағандығы тексеріледі. Егер тұрған болса, онда есеп шешілді. Басқа  жағдайда түбіртектің оң жағындағы  секцияның және одан кейінгінің бостығы  тексеріледі. Егер екеуі де бос болса, онда түбіртек бір адым кейін шегініп, ен салынады, сонан соң осындай  амал сол жақтан орындалады да түбіртек белгіленген жолмен оңжаққа қайтып оралады және т.б. түбіртек санға жолыққанға дейін жалғаса береді. Сонан соң жоғарыда қарастырылған программаларды қолдануға болады.

Пост  машинасын ЭЕМ-нің қарапайым моделі деп қарауға болады. Шын мәнісінде, ЭЕМ де, Пост машинасында да:

толтырылған немесе толтырылмаған ақпараттың бөлінбейтін  тұғырлары (шаршылар- биттер);

элементар әрекеттердің шектелген жиынтығы - әрқайсысы бір актыда (адымда) орындалатын  командалар-бар.

Екі машина да программа негізінде жұмыс  істейді. Дегенмен Пост машинасында  ақпарат сызық бойынша орналасады да, бірінен соң бірі оқыла береді, ал ЭЕМ-де ақпаратты адресі бойынша  оқуға болады; ЭЕМ командаларының жиынтығы әлде- қайда кең әрі Пост машинасы командаларына қарағанда  айқын, т.с.с.

Тьюринг машинасы

Пост  машинасына ұқсас, бірақ сәл басқаша  жұмыс істейді. Тьюринг машинасы (ТМ) есепші таспадан (ұяшықтарға бөлінген және солынан шектелген, бірақ оңынан емес), оқып және жазатын түбіртектен, таспатартар механизм мен амал атқарушы құрылғыдан тұрады. Құрылғы кейбір ақырлы жиынға (ішкі күй-жай әріппесіне) жататын  дискретті күйлерінің бірінде болады. Мұндағы - бастапқы күй деп аталады.

Оқитын  да, жазатын түбіртек  жұмысшы әріппесінің әріптерін оқи да, өшіре де, баспаға шығара да алады. Таспаның әрбір ұяшығы әр мезет А жиыны әрпімен толтырылған. -“бос орын” әрпі бәрінен жиі кездеседі. Түбіртек әр мезет таспа ұяшығының бірі-ағымдағы жұмысшы ұяшық үстінде тұрады. Таспатар механизм  түбіртек басының көрші ұяшығының үстінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ шетіне шығу жағдайы болуы мүмкін. Ол жағдай, тоқтау туралы бұйрықты машинаның орындау барысындағы машиналық тоқтау немесе  апатты (болмайтын)тоқтау болып табылады.

ТМ  жұмыс реті ( жұмысшы әріппесі мен күйлері бар). Тьюринг машинасы кестесі арқылы өрнектеледі. Бұл кесте төрт тікжолды және  (s+1) (t+1) жолы бар матрица болып табылады. Әр жол мына түрде болады:

Мұнда арқылы әріппесі мен таспатартар механизм үшін бүйрықтар жиынын біріктіру элементі белгіленген. Бұйрықтар жиыны: l-таспаны солға орналастыру, r-таспаны оңға орналастыру, s-машинаны тоқтату; vіj –a0, a1,...., at әріппесі таңбасын таспа ұяшығына жазудан, не түбіртекті қозғаудан,  не машинаны тоқтатудан тұратын ТМ әрекеті; qіj келесі күй-жай болып табылады.

ТМ  мына ережелер бойынша жұмыс істейді:

Егер  ТМ qі  күйінде болса, түбіртек жұмысшы  ұяшығынан aj таңбасын оқиды. qі aj  таңбаларынан басталатын qі aj vіj qіj  жолы кестеде  бір-ақ рет кездеседі. Егер vіj- жұмысшы  әріппесінің әрпі болса, онда түбіртек жұмысшы ұяшықтағыны өшіріп, оған осы әріпті апарып жазады. Егер vіj-  таспатартар механизм үшін r немесе l командасы болса, онда таспа оңға немесе солға бір ұяшыққа жылжиды (егер таспаның сол жақ шетіне шығып  кетпесе).

Тюринг  машинасы А әріппесінің бір таңбасы  бар таспаның белгілі ұяшығы үстін  оқып-жазатын түбіртектің орны мен  бастапқы күйден (әдетте q0) тұратын  бастапқы конфигурацияның бірінен  жұмысын бастайды.

ТМ  жұмысшы әріппесінде әртүрлі  таңбалардың болуы таспада кезкелген  мәтіндік және сандық ақпаратты көрсетуге  мүмкіндік береді, ал ТМ басқару  орталығының әртүрлі күйге ауысуы Тюринг машинасының жұмыстың аралық нәтижелерін жадында ұстауын модельдейді. ТМ жұмысы ретін анықтайтын кесте тура мағынада программа емес (оның бұйрықтары кезекпен бірінен соң бірі орындалмайды,  таспадағы әлдебір мәтіннің таңбаларын түрлендіруді өрнектейді). ТМ кестесін жиі Тюринг машинасының сүлбесі деп атайды немесе ТМ құрылысы мен жұмыс істеу негізі белгілі болғандықтан Тюринг машинасының өзімен теңдестіре салады. Тюринг машинасының бірнеше сүлбесі мысалдарын қарастырайық.