|
Необходимо составить программу для машины Тьюринга, вычисляющую функцию $%2^{N} $%, где $%N$% задано в троичной системе счисления. Смущает очень троичная система. Подскажите, пожалуйста, какой будет алгоритм. задан 21 Май '17 3:08 
katkainite |
|
В деталях это всё описывать сложно, но общая идея следующая. Нужна "подпрограмма" умножения троичного числа на 2 (все действия -- в троичной системе). Тогда заводится счётчик N, из которого на каждом шаге цикла вычитается по единице, пока он не обнулится. Это делается на правой части ленты, а левее у нас будет число 1, которое будет каждый раз удваиваться. Делается это по обычному алгоритму, когда мы умножаем "столбиком". Мы идём по записи числа справа налево, и что-то "пишем", а что-то находится "в уме". Последнее запоминается в виде состояния. Например, у нас "в уме" 1, и удвоить надо цифру 2. Это даст 4, и ещё плюс один, то есть 5. В троичной системе мы пишем 2, и далее 1 получаем "в уме". Если бы первоначально "в уме" было 6, то мы бы написали цифру 0, и 2 перешло бы в следующий разряд. То есть это обычный алгоритм умножения, а специфика системы счисления тут роли не играет (троичная система даже проще десятичной). Вычитание единицы из троичного числа основано на том же принципе, а помнить надо то, сколько единиц из следующего разряда мы "занимаем". отвечен 21 Май '17 14:07 
falcao |
Нужно уточнить, в каком формате машина должна давать ответ. Скажем, пусть мы задали запись 12 на ленте. В троичной системе это будет число N=5. Тогда 2^N=32. В какой системе выдаётся ответ? Тоже в троичной, или как-то иначе?
В троичной, отсюда и непонятно, как это сделать..