Подтема 3 из 6
Двоичное число на ленте
Как читать строку на ленте как двоичное число: таблица задачи темы вычитает единицу, другие — прибавляют, дописывают и меняют цифры.
Минус один
Что таблица задачи темы делает с числом, если на ленте его двоичная запись?
| Состояние | λ | 0 | 1 |
|---|---|---|---|
q0 | λ, L, q1 | — | — |
q1 | λ, S, q1 | 1, L, q1 | 0, S, q1 |
Если на ленте двоичная запись числа, действие таблицы читают как арифметику: таблица задачи темы вычитает единицу. В подтеме 1 из 10100 = 20 получилось 10011 = 19. Так и вычитают единицу столбиком: нули справа занимают у ближайшей единицы и становятся единицами, сама единица становится нулём.
37 = 100101: справа сразу единица, она становится нулём — 100100 = 36, два такта. 40 = 101000: три нуля хвоста стали единицами, единица — нулём: 100111 = 39, пять тактов.
Проверим вывод на всех числах от 1 до 500: — двоичная запись без приставки 0b, int(result, 2) — число по двоичной записи. Функция run_tm — из подтемы 1.
rules = { ('q0', 'λ'): ('λ', 'L', 'q1'), ('q1', 'λ'): ('λ', 'S', 'q1'), ('q1', '0'): ('1', 'L', 'q1'), ('q1', '1'): ('0', 'S', 'q1'),}bad = 0for n in range(1, 501): word = bin(n)[2:] result, pos, steps = run_tm(word, rules, len(word)) if int(result, 2) != n - 1: bad += 1print('расхождений:', bad)Совпадение на 500 числах — проверка, а не доказательство: доказывает рассуждение о разрядах выше.
Тонкости:строка из нулей
«Минус один» верно только для ненулевого числа. Из 000 таблица сделает 111: единицы не встретится, все нули станут единицами, и машина остановится на пустой ячейке. Запись отрицательного числа таблицей не предусмотрена.
Слово и число
Из 1000 таблица задачи темы делает 0111. Это 7 или четыре символа?
Слово на ленте хранит каждую ячейку, в том числе ведущие нули, а число — только значение. 0111 — четыре символа, один ноль, значение 7. Если вопрос о длине, числе нулей или тактов, работают со словом; если о десятичном результате — с числом.
Веса разрядов от правого края — 1, 2, 4, 8, …; значение — сумма весов там, где стоят единицы: 10101 = 16 + 4 + 1 = 21.
Цифра слева и справа
Таблица ниже проходит число 21 = 10101 и пишет единицу слева. Какое число получится? Головка начинает в ближайшей пустой ячейке справа, в q0.
- Начало: q0, головка в клетке 5. Перед тактом 1: q0 читает λ в клетке 5 → записать λ, влево, q1.
- Перед тактом 2: q1 читает 1 в клетке 4 → записать 1, влево, q1.
- Перед тактом 3: q1 читает 0 в клетке 3 → записать 0, влево, q1.
- Перед тактом 4: q1 читает 1 в клетке 2 → записать 1, влево, q1.
- Перед тактом 5: q1 читает 0 в клетке 1 → записать 0, влево, q1.
- Перед тактом 6: q1 читает 1 в клетке 0 → записать 1, влево, q1.
- Перед тактом 7: q1 читает λ в клетке -1 → записать 1, влево, q2.
- Перед тактом 8: q2 читает λ в клетке -2 → записать λ, стоп, q2.
- Остановка: на ленте 110101, тактов 8, головка на -2.
Единица слева от слова длины k добавляет 2ᵏ: получается N + 2ᵏ. Цифра справа сдвигает прежние на разряд: ноль даёт 2N, единица — 2N + 1. Слово 10101 длины 5: 21 + 32 = 53 = 110101. Тактов k + 3 = 8: вход, пять цифр, запись слева, остановка.
Длину k бери из самой записи: 100 = 1100100 — семь цифр, единица слева даёт 100 + 128 = 228. Справа: 37 = 100101, единица справа — 2 · 37 + 1 = 75, блок 10 справа — 4 · 37 + 2 = 150.
rules = { ('q0', 'λ'): ('λ', 'L', 'q1'), ('q1', '0'): ('0', 'L', 'q1'), ('q1', '1'): ('1', 'L', 'q1'), ('q1', 'λ'): ('1', 'L', 'q2'), ('q2', 'λ'): ('λ', 'S', 'q2'),}bad = 0for n in range(1, 501): word = bin(n)[2:] result, pos, steps = run_tm(word, rules, len(word)) if int(result, 2) != n + 2 ** len(word): bad += 1print(run_tm('10101', rules, 5), 'расхождений:', bad)Тонкости:смена старшего разряда
Пусть таблица, дойдя до левого края, сначала меняет старшую единицу на ноль и только потом пишет единицу левее. Тогда старая единица теряет вес 2ᵏ⁻¹, новая получает 2ᵏ: результат N + 2ᵏ⁻¹. Для 21 — 100101 = 37, а не 53.
Инверсия
Таблица проходит слово и меняет каждую цифру на противоположную. Что станет с числом 21?
| Состояние | λ | 0 | 1 |
|---|---|---|---|
q0 | λ, L, q1 | — | — |
q1 | λ, S, q1 | 1, L, q1 | 0, L, q1 |
Инверсия сохраняет длину слова, а значение становится 2ᵏ − 1 − N. В каждом разряде цифра и её противоположность вместе дают единицу, поэтому N и результат вместе дают k единиц, то есть 2ᵏ − 1. 10101 → 01010: 31 − 21 = 10, а на ленте по-прежнему пять символов.
Плюс один
А если в таблице задачи темы поменять ролями 0 и 1 — что она будет делать с числом 1011?
| Состояние | λ | 0 | 1 |
|---|---|---|---|
q0 | λ, L, q1 | — | — |
q1 | 1, S, q1 | 1, S, q1 | 0, L, q1 |
Такая таблица прибавляет единицу: единицы хвоста становятся нулями, ближайший ноль или пустая ячейка слева — единицей. 1011 = 11 → 1100 = 12, четыре такта. Если единицы везде, слово удлиняется: 111 → 1000.
Итого
- Задача темывычитает единицу: 20 → 19
- Слово и числоведущие нули — тоже ячейки
- 1 слеваN + 2ᵏ, k — длина записи
- Справа0 — 2N, 1 — 2N + 1
- Инверсия2ᵏ − 1 − N, длина та же
- Плюс одинединицы хвоста → 0, ноль → 1
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
101000 → 100111.ОтветСкрыть ответ
101. Какое число получится?ОтветСкрыть ответ
1101.1000. Сколько символов будет на ленте и какое значение?ОтветСкрыть ответ
0111, значение 7 = 2⁴ − 1 − 8.ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Единица справа
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 37 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке слева от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, R, q1 | — | — |
| q1 | 1, S, q1 | 0, R, q1 | 1, R, q1 |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Цифра справа сдвигает прежние цифры на разряд.
Решение
Машина проходит запись вправо без изменений и на пустой ячейке пишет 1. Единица справа даёт 2N + 1: 2 · 37 + 1 = 75.
Ответ: 75
Блок 10 справа
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 45 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке слева от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, R, q1 | — | — |
| q1 | 1, R, q2 | 0, R, q1 | 1, R, q1 |
| q2 | 0, S, q2 | — | — |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Две цифры справа — умножение на 4 и прибавление блока.
Решение
Машина проходит запись вправо и дописывает справа 10. Две новые цифры умножают число на 4, блок 10 добавляет 2: 45 · 4 + 2 = 182.
Ответ: 182
Единица слева к числу 5
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 5 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | 1, L, q2 | 0, L, q1 | 1, L, q1 |
| q2 | λ, S, q2 | — | — |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Единица слева добавляет 2ᵏ, k — число цифр.
Решение
Машина проходит запись влево без изменений и пишет 1 слева. 5 = 101, три цифры: 5 + 2³ = 13, запись 1101.
Ответ: 13
Единица слева к числу 100
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 100 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | 1, L, q2 | 0, L, q1 | 1, L, q1 |
| q2 | λ, S, q2 | — | — |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Прибавляется 2ᵏ, k — число цифр.
Решение
100 = 1100100, семь цифр. Единица слева получает вес 2⁷: 100 + 128 = 228.
Ответ: 228
Единица слева к числу 1000
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 1000 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | 1, L, q2 | 0, L, q1 | 1, L, q1 |
| q2 | λ, S, q2 | — | — |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Десять цифр — плюс 2¹⁰.
Решение
1000 = 1111101000, десять цифр. Единица слева добавляет 2¹⁰ = 1024: 1000 + 1024 = 2024.
Ответ: 2024
Смена старшего разряда
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 50 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, R, q2 | 0, L, q1 | 1, L, q1 |
| q2 | — | — | 0, L, q3 |
| q3 | 1, S, q3 | — | — |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Сначала старшая единица становится нулём.
Решение
50 = 110010, шесть цифр. Машина доходит до левого края, меняет старшую единицу (вес 32) на ноль и пишет единицу левее (вес 64): 50 − 32 + 64 = 82.
Ответ: 82
Инверсия числа 200
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 200 без ведущих нулей, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, S, q1 | 1, L, q1 | 0, L, q1 |
Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.
Введите число.
Подсказка
Инверсия даёт 2ᵏ − 1 − N.
Решение
Машина меняет каждую цифру на противоположную. 200 = 11001000, восемь цифр: 2⁸ − 1 − 200 = 55, запись 00110111.
Ответ: 55
Прибавление единицы к 101111
На ленте исполнителя МТ записано слово 101111, остальные ячейки пустые (λ). Головка — в ближайшей пустой ячейке справа от строки, состояние q0. Программа:
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | 1, S, q1 | 1, S, q1 | 0, L, q1 |
Какое слово окажется на ленте после остановки?
Введите слово — цифры подряд, без пробелов.
Подсказка
Единицы справа становятся нулями, пока не встретится ноль.
Решение
Четыре единицы справа стали нулями, ноль перед ними — единицей: 110000. Это 47 + 1 = 48.
Ответ: 110000