Задачи по матлогике (теория алгоритмов)

1. Написать программу МТ, которая к произвольному слову в алфавите {a, b} приписывает слева слово aba.
2. Используя теоремы сочетания, построить МТ, которая проверяет делимость на 3 конструктивного натурального числа.
это задачи на машину тьюринга