Здравствуйте, Wotan, Вы писали:

W>Как лучше всего записать набор правил для машины Тьюринга (т.е. количество правил должно быть минимальным), например, для такой задачи: каретка находится на ячейке с символом '*', записать после него 600 символов 'a'. Можете идею подкинуть?

Понятно, что напрямую писать 600 символов -- это надо иметь 600 переходов и соответствующие состояния. Для минимизации количества состояний и переходов можно использовать тот факт, что число 600 -- составное и равно 2*2*2*5*5*3. Соответственно, надо сначала записать два символа a, затем два раза помножить эту запись на два, затем два раза помножить результат на 5, и затем помножить результат на три. Лучше конечно делать это в порядке возрастания множителей, т.е. сначала 2, потом 3, а уже потом 5. Левую звездочку можно использовать как начала записи влево количества на что умножаем.