«Информатиканың теориялық негіздері» Қазақстан республикасы білім және ғылым министрлігі

1. Рекурсивті функцияларды қолдана отырып құр:

   
   

А) қосудың үшорынды функциясын;

2. Рекурсивті функцияларды қолдана отырып құр:

   
   

А) көбейтудің екіорынды функциясын;

3. Бөлудің бөлікті екіорынды функциясын құрастыр.

   
   

4. Лентада бөлінегн екі санды қосатын Пост машинасының программасын құрып, өзбетіңмен орында;

   
   

А) бір бос орынмен;

5. Лентада бөлінегн екі санды азайтатын Пост машинасының программасын құрып, өзбетіңмен орында

   
   

А) бір бос орынмен;

6. Лентада бөлінегн екі санды көбейтетін Пост машинасының программасын құрып, өзбетіңмен орында

   
   

А) бір бос орынмен;

7. Қарапайым арифметикалық амалдарды орындайтын Тьюринг машинасын құрастыр.

   
   

8. g және h функциясын есептейтін Тьюринг машиналары бар. Келесі есептеуді орындайтын машина құрастыр:

   
   

А) осы функциялардың суперпозициясын;

9. Кері функцияны тудыратын Тьюринг машинасын құрастыр.

   
   

10. Келесілерді есептейтін Тьюринг машинасын құрастыр:

    
    

А) екі санның қосындысын;

11. 1 символдарымен көрсетілген екі бүтін сандарды азайтуды орындайтын Марковтың қалыпты алгоритмін құрастыр. Алгоритмнің жұмысын мысалдармен тексер.

    
    

12. 1 символдарымен көрсетілген екі бүтін сандарды көбейтуді орындайтын Марковтың қалыпты алгоритмін құрастыр.