BpeDuHa писал(а):
...совсем не представляю что такое "сочетания МТ".
Я тоже. Несмотря на то, что каждый год читаю на мехмате лекции про эти самые машины Тьюринга
С машинами Тьюринга ведь в чём сложность?.. Они существуют в куче различных модификаций. В разных университетах на разных курсах разные лекторы определяют их чуть-чуть по разному, и часто каждый привносит что-то своё. Универсального для всех стандарта не существует. Студенты, слушающие какой-то один курс в каком-нибудь одном ВУЗе свято уверены, что понятия, которые им дают на лекциях, универсальны, но... зачастую это не так. Весь мир примерно знает о том, что такое машины Тьюринга, однако когда начинают уточнять определения. то детали у всех вылазят свои.
Машины Тьюринга бывают с одной лентой, с несколькими лентами, с бесконечным числом лент, с прямым и последовательным доступом к ячейкам... Ленты бывают как бесконечными с обоих концов, так и с одного конца, причём для лент, бесконечных с одного конца, граничную ячейку ленты иногда выделяют, а иногда нет. Даже на наиболее распространённой машине с одной лентой и последовательным доступом к ячейкам команды бывают как "пятисимвольные" (допускается одновременный сдвиг и запись в ячейку), так и "четырёхсимвольные" (подобное не допускается)... Числовые данные иногда записывают в двоичном коде, а иногда просто количество единиц обозначает число. Иногда допускается расширение внешнего алфавита, а иногда не допускается. И т. д., и т. п.
Темы "помогите написать программу для машины Тьюринга" время от времени возникают на этом форуме. И рады бы помочь, но... мы ведь тут не телепаты. И не можем угадать, какая именно модификация машины с какой именно системой команд принята в том конкретном ВУЗе и на том конкретном курсе/потоке, где учится спрашивающий. А без этой конкретики никто ведь программу не напишет! В лучшем случае можно будет дать общие указания к алгоритму.
Так что, уважаемый аскер... если хотите конкретной помощи, то давайте нам погружение в свой курс: с формулировками определений, примерами программ и т. д. Что касается каких-то общих указаний по алгоритму, то они уже были высказаны выше: головка машины бегает от одного аргумента к другому, отнимая от каждого по единице до тех пор, пока один из аргументов не обнулится; после обнуления одного из аргументов второй будет равен результату вычислений.
