Все сервисы Хабра
Сообщество IT-специалистов
Ответы на любые вопросы об IT
Профессиональное развитие в IT
Закрыть
Задать вопрос
Berthellar
@Berthellar
Алгоритмы
Как вычислить значение x mod 2 на машине Тьюринга?
Необходимо написать алгоритм для вычисления на машине Тьюринга значение (x mod 2), где x - натуральное число в унарном коде
Вопрос задан
более двух лет назад
213 просмотров
1
комментарий
Подписаться
1
Простой
1
комментарий
Facebook
Вконтакте
Twitter
Berthellar
@Berthellar
Автор вопроса
Спасибо за ответы, но уже решил. Решение следующее:
1) Просматриваются 3 близлежащих числа
2) Если все три числа это 1, тогда первые два обнуляются и процедура повторяется, начиная с оставшейся единицы, пока не получится либо 1, либо 11
Написано
более двух лет назад
Решения вопроса
0
Пригласить эксперта
Ответы на вопрос
1
mayton2019
@mayton2019
Bigdata Engineer
В унарном виде - это как цепочка единичек. Например число 5 будет.
_11111_
Справа и слева должен стоять blank sysmbol. Типа признак конца ленты чтоб было что проверять.
Тогда (5 mod 2) = 1
И мы должны получить на ленточке просто единичку.
_1_
Это можно сделать поглощая пары соседних единичек. А для четного числа будет пустая лента. Тоесть остаток от деления равен нулю.
Ну вот такой алгоритм. Дальше надо делать конечный автомат который ищет пары единичек.
Ответ написан
более двух лет назад
Комментировать
Нравится
2
Комментировать
Facebook
Вконтакте
Twitter
Ваш ответ на вопрос
Войдите, чтобы написать ответ
Войти через центр авторизации
Похожие вопросы
Алгоритмы
+1 ещё
Средний
Как можно предиктить дату регистрации при массиве данных?
1 подписчик
03 июл.
123 просмотра
1
ответ
Программирование
+1 ещё
Простой
Как работает регистрация и аутентификация с помощью ЭЦП?
1 подписчик
26 июн.
254 просмотра
3
ответа
Компьютерные сети
+1 ещё
Простой
Как построить топологию сетей (данные в FDB таблице) когда связи замкнуты в кольцо?
2 подписчика
25 июн.
462 просмотра
2
ответа
Алгоритмы
Средний
Какие переходы для ДП у «Гелифиш и незабудка» codeforce?
1 подписчик
12 июн.
86 просмотров
1
ответ
C#
+1 ещё
Простой
Почему неправильно работает Keeloq?
1 подписчик
05 июн.
113 просмотров
1
ответ
Алгоритмы
Простой
Какие переходы для ДП Codeforces Петя и пауки?
1 подписчик
27 мая
162 просмотра
1
ответ
Алгоритмы
Простой
Какую букву в игре поле чудес в этом случае лучше всего открыть? правильное ли это решение?
1 подписчик
20 мая
245 просмотров
3
ответа
Python
+3 ещё
Простой
Как повысить точность классификации по табличным документам?
2 подписчика
19 мая
268 просмотров
1
ответ
C#
+1 ещё
Простой
Почему моя реализация Shaker Sort-а такая медленная?
2 подписчика
17 мая
618 просмотров
1
ответ
Алгоритмы
Простой
Какую букву в игре поле чудес в этом случае лучше всего открыть?
1 подписчик
17 мая
249 просмотров
1
ответ
Показать ещё
Загружается…
Вакансии с Хабр Карьеры
Software Engineer (Humanoid Robots)
Яндекс
•
Москва
Техлид в Yandex Network Blockstore (C++)
Яндекс
•
Москва
Principal software engineer (Python/Go) в команду DCIM
Яндекс
•
Москва
Минуточку внимания
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
Войти через центр авторизации
Закрыть
Реклама