Дискретная математика.Машина Тьюринга. Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
Дискретная математика.Машина Тьюринга. Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения данной задачи с помощью машины Тьюринга можно использовать следующий алгоритм:
Считать символы Q и R по очереди, начиная с самого левого (старшего) разряда.Если длины Q и R различны, добавить нули к более короткой записи до тех пор, пока их длины не станут равными.Сравнивать последовательно символы Q и R. Если они равны, продолжать переход на следующий символ. Если есть различие, выдать слово 0 и завершить работу машины.Если все символы Q и R были одинаковы, выдать слово 1.Таким образом, при выполнении данного алгоритма машина Тьюринга будет сравнивать двоичные числа Q и R и выдавать ответ в соответствии с условием задачи.