Бақылау тест тапсырмалары

1 Тьюринг машинасын қандай түрде көрсетуге болады?

1. 
   ақырлы автомат
   
2. 
   КБ-тіл
   
3. 
   грамматика
   

4. 
   жүйе
   
5. 
   алгоритмдік тіл
   

2 Жүйе түрінде қандай машинаны көрсетуге болады?

1. 
   ақырлы автомат
   

2. 
   Пост машинасы
   
3. 
   автомат
   
4. 
   Тьюринг машинасы
   
5. 
   Пост-Тьюринг машинасы
   

3 m командасын орындағаннан кейін Пост машинасының лентасының күйі қандай болады?

5 M m командасын орындағаннан кейін Пост машинасының лентасының күйі қандай болады?

6 C m командасын орындағаннан кейін Пост машинасының лентасының күйі қандай болады?

7 Тоқта n командасын орындағаннан кейін Пост машинасының лентасының күйі қандай болады?

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

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

3. 
   автомат нәтижелі де, нәтижесіз де тоқтатуға жетпеді, шексіз жұмыс істеу болады (автомат «тұрып қалады»)
   

4. 
   автомат лента аяғына дейін жетті; программа жұмысы тоқтайды, автомат тоқтайды, нәтижесіз тоқтау болады
   

5. 
   автомат лентада белгіні жазуды жүзеге асырды және келесі команданы орындауға көшеді
   

9 Тьюринг машинасының қай жерінде жазу орындалады?

1. 
   жады;
   

2. 
   лента;
   
3. 
   процессор
   
4. 
   қатар.
   
5. 
   бастиекте
   

10 Тьюринг машинасының жұмыс істеу процесінде не байқалады?

1. 
   жұмысты басынан бастау;
   
2. 
   жұмысты тоқтату;
   
3. 
   кіріс жолын сырғыту;
   
4. 
   жолдан шығу.
   
5. 
   жұмысты екінші жолдан сырғыту
   

11 Тьюринг машинасының келтірілген функционалды схемасы қандай есепті шешеді

1. 
   бестік санау жүйесіндегі екі санды қосу
   
2. 
   бестік санау жүйесіндегі екі санды азайту
   
3. 
   бестік санау жүйесіндегі санға бірді қосу
   
4. 
   бестік санау жүйесіндегі саннан бірді азайту
   
5. 
   ондық санау жүйесіндегі санды бестік санау жүйесіне ауыстыру
   

12 Тьюринг машинасының келтірілген функционалды схемасы қандай есепті шешеді

A	q
	z  S
a	qbR
b	qaR

1. 
   бірінші таңбаны сөз соңына ауыстыру
   

2. 
   соңғы таңбаны сөз басына ауыстыру
   
3. 
   a символын b символымен ауыстыру
   
4. 
   b символын a символымен ауыстыру
   

5. 
   a символын b символымен ауыстыру және b символын a символымен ауыстыру
   

13 Пост машинасы үшін келтірілген программа көмегімен қандай есеп шешіледі

1. 
   М 2
   
2. 
    3
   

3. 
   М 4
   
4. 
   тоқта
   

1. 
   бос лентаға екі белгі жазу
   
2. 
   бастиекті солға бірінші бос позицияға дейін қозғалту
   

3. 
   бірнеше санның біреуіне бірді қосу
   

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

5. 
   лентада кез келген ара қашықтықта жазылған a және b екі санын қосу