Решение задачи: Двоичное представление 135 и машина Тьюринга

Ниже представлено подробное решение задач, оформленное для переписывания в тетрадь. Задание №1 1. Переведем число 135 в двоичную систему счисления: \[ 135_{10} = 128 + 4 + 2 + 1 = 2^7 + 2^2 + 2^1 + 2^0 = 10000111_2 \] На ленте: \( 10000111 \). Головка на \( \lambda \) справа, состояние \( q_0 \). 2. Выполним алгоритм: - \( (q_0, \lambda) \rightarrow (\lambda, L, q_1) \): Головка сдвигается влево на последнюю цифру, состояние \( q_1 \). - В состоянии \( q_1 \) согласно таблице: если видим 1, пишем 0; если видим 0, пишем 1. Головка всегда идет влево (\( L \)). - Это означает полную инверсию всех разрядов числа. Было: \( 10000111 \) Стало: \( 01111000 \) 3. Переведем результат в десятичную систему: \[ 01111000_2 = 0 \cdot 2^7 + 1 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 \] \[ 64 + 32 + 16 + 8 = 120 \] Ответ: 120 Задание №2 1. Переведем число 2028 в двоичную систему: \[ 2028_{10} = 11111101100_2 \] Головка на \( \lambda \) слева, состояние \( q_0 \). 2. Выполним алгоритм: - \( (q_0, \lambda) \rightarrow (\lambda, R, q_1) \): Сдвиг вправо на первую цифру. - В состоянии \( q_1 \) головка идет вправо (\( R \)), не меняя цифры, пока не встретит первый 0. - В числе \( 11111101100 \) первый 0 стоит на 7-й позиции. - Встретив 0: \( (q_1, 0) \rightarrow (0, R, q_2) \). Головка переходит на 8-ю позицию (там цифра 1), состояние \( q_2 \). - В состоянии \( q_2 \) любая цифра (в данном случае 1) меняется на 0: \( (q_2, 1) \rightarrow (0, R, q_3) \). - В состоянии \( q_3 \) программа доходит до \( \lambda \) и останавливается (\( S \)). Результат: \( 11111100100 \) (единица на 8-й позиции заменилась на 0). 3. Переведем в десятичную систему: \[ 11111100100_2 = 1024 + 512 + 256 + 128 + 64 + 32 + 4 = 2020 \] Ответ: 2020 Задание №3 1. На ленте 57 единиц. Головка справа на \( \lambda \), состояние \( q_0 \). 2. Ход программы: - \( (q_0, \lambda) \rightarrow (\lambda, L, q_1) \): Переход на 57-ю единицу. - \( (q_1, 1) \rightarrow (1, L, q_2) \): 57-я единица остается 1, переход на 56-ю, состояние \( q_2 \). - \( (q_2, 1) \rightarrow (0, L, q_3) \): 56-я единица становится 0, переход на 55-ю, состояние \( q_3 \). - \( (q_3, 1) \rightarrow (1, L, q_2) \): 55-я единица остается 1, переход на 54-ю, состояние \( q_2 \). 3. Закономерность: Начиная с 56-й ячейки, включается цикл \( q_2 \leftrightarrow q_3 \). Каждая вторая ячейка (четные позиции с конца, кроме самой первой обработанной) превращается в 0. Всего ячеек для этого цикла: \( 57 - 1 = 56 \). Количество нулей: \[ 56 / 2 = 28 \] Ответ: 28